Given a 2d Array arr[][], the task is to check if the sum of the subarrays is in increasing order or not. If yes return “true” otherwise return “false”.
Examples:
Input: arr[][] = {{1, 2}, {2, 4}, {4, 5}, {6, 4}};
Output: true
Explanation: 1st subarray sum is 1 + 2 = 3.
2nd subarray sum is 2 + 4 = 6.
3rd subarray sum is 4 + 5 = 9.
4th subarray sum is 6 + 4 = 10.
Because, 3 < 6 < 9 < 10 therefore, sum of subarrays is in increasing order, and that’s why
output is true.Input: arr[][] = {{6, 2}, {3, 9}, {5, 6}, {7, 1}};
Output: false
Approach: To solve the problem follow the below idea:
We can do this by looping through each subarray, calculating its sum, and comparing it with the sum of the previous subarray.
- If the sum of the current subarray is less than or equal to the sum of the previous subarray, we return false.
- If all subarrays have an increasing sum, we return true.
Follow the steps to solve the problem:
- Define a function “checkIncreasingSum” that takes a 2D vector “arr” as input and returns a boolean value.
- Initialize a variable “prevSum” to 0.
- Loop through each subarray in “arr”:
- Initialize a variable “curSum” to 0.
- Loop through each element in the current subarray and add it to “curSum”.
- If “curSum” is less than or equal to “prevSum”, return “false”.
- Set “prevSum” to “curSum”.
- If all subarrays have an increasing sum, return “true”.
Below is the implementation of the above approach:
C++
// C++ code to implement above approach#include <iostream>#include <vector>using namespace std;// Function to check if the sum of each// subarray is in increasing orderbool checkIncreasingSum(vector<vector<int> >& arr){ int prevSum = 0; // Initializing the previous sum to 0 for (int i = 0; i < arr.size(); i++) { // Loop through each subarray int curSum = 0; // Initializing the current // sum to 0 for (int j = 0; j < arr[i].size(); j++) { // Loop through each element // in the subarray curSum += arr[i][j]; // Adding the current element // to the current sum } if (curSum <= prevSum) { // If the current sum is less // than or equal to the // previous sum, return false return false; } prevSum = curSum; // Update the previous sum to be // the current sum } return true; // If all subarrays have an increasing // sum, return true}// Driver's codeint main(){ vector<vector<int> > arr = { { 1, 2 }, { 2, 4 }, { 4, 5 }, { 6, 4 } }; // Initializing a 2D vector // with some values bool res = checkIncreasingSum(arr); // Calling the checkIncreasingSum // function on the input vector if (res) { cout << "true"; // If the returned value is true, // print "true" } else { cout << "false"; // If the returned value is false, // print "false" } return 0;} |
Java
// Java code to implement the approachimport java.util.ArrayList;public class Main { public static boolean checkIncreasingSum(ArrayList<ArrayList<Integer> > arr) { int prevSum = 0; // Initializing the previous sum to 0 for (int i = 0; i < arr.size(); i++) { // Loop through each subarray int curSum = 0; // Initializing the current sum to 0 for (int j = 0; j < arr.get(i).size(); j++) { // Loop through each element in the subarray curSum += arr.get(i).get(j); // Adding the current element to the current // sum } if (curSum <= prevSum) { // If the current sum is less than or equal // to the previous sum, return false return false; } prevSum = curSum; // Update the previous sum to be the current sum } return true; // If all subarrays have an increasing sum, return // true } // Driver's code public static void main(String[] args) { ArrayList<ArrayList<Integer> > arr = new ArrayList<>(); arr.add(new ArrayList<Integer>() { { add(1); add(2); } }); arr.add(new ArrayList<Integer>() { { add(2); add(4); } }); arr.add(new ArrayList<Integer>() { { add(4); add(5); } }); arr.add(new ArrayList<Integer>() { { add(6); add(4); } }); boolean res = checkIncreasingSum(arr); if (res) { System.out.println("true"); } else { System.out.println("false"); } }} |
Python3
# Function to check if the sum of each# subarray is in increasing orderdef checkIncreasingSum(arr): prevSum = 0 # Initializing the previous sum to 0 for i in range(len(arr)): # Loop through each subarray curSum = 0 # Initializing the current sum to 0 for j in range(len(arr[i])): # Loop through each element in the subarray curSum += arr[i][j] # Adding the current element to the current sum if curSum <= prevSum: # If the current sum is less # than or equal to the previous sum, return false return False prevSum = curSum # Update the previous sum to be # the current sum return True # If all subarrays have an increasing # sum, return true# Driver's codearr = [[1, 2], [2, 4], [4, 5], [6, 4]]# Initializing a 2D list with some valuesres = checkIncreasingSum(arr)# Calling the checkIncreasingSum# function on the input listif res: print("true") # If the returned value is true, print "true"else: print("false") # If the returned value is false, print "false" |
C#
// C# code to implement the approachusing System;using System.Collections.Generic;class MainClass { public static bool CheckIncreasingSum(List<List<int> > arr) { int prevSum = 0; foreach(List<int> subarr in arr) { int curSum = 0; foreach(int num in subarr) { curSum += num; } if (curSum <= prevSum) { return false; } prevSum = curSum; } return true; } // Driver's code public static void Main() { List<List<int> > arr = new List<List<int> >{ new List<int>{ 1, 2 }, new List<int>{ 2, 4 }, new List<int>{ 4, 5 }, new List<int>{ 6, 4 } }; bool res = CheckIncreasingSum(arr); if (res) { Console.WriteLine("true"); } else { Console.WriteLine("false"); } }} |
Javascript
function checkIncreasingSum(arr) { let prevSum = 0; // Initializing the previous sum to 0 for (let i = 0; i < arr.length; i++) { // Loop through each subarray let curSum = 0; // Initializing the current sum to 0 for (let j = 0; j < arr[i].length; j++) { // Loop through each element in the subarray curSum += arr[i][j]; // Adding the current element to the current sum } if (curSum <= prevSum) { // If the current sum is less than or equal to the previous sum, return false return false; } prevSum = curSum; // Update the previous sum to be the current sum } return true; // If all subarrays have an increasing sum, return true}let arr = [[1, 2], [2, 4], [4, 5], [6, 4]];let res = checkIncreasingSum(arr);if (res) { console.log("true");} else { console.log("false");} |
Output
true
Time complexity: O(N*M), where N is the number of subarrays and M is the number of elements in each subarray. This is because we loop through each subarray and each element in the subarray once.
Auxiliary Space: O(1) because we only use a constant amount of extra space to store the previous sum and the current sum. The space used by the input arr is not counted because it is part of the input.
2) Here is another approach for above problem:
In the above approach it uses nested loop which increases time and space complexity but in this approach, we can use single loop which will decrease the time complexity.
The approach includes following steps:
- We first initialize the variable to the sum of the first subarray.
- Then, we loop through the rest of the subarrays and calculate the sum of each subarray using the “sum” function.
- If the sum of the current subarray is less than or equal to the sum of the previous subarray, we return False. Otherwise, we update the “prevSum” variable to the current sum and continue looping.
- If we have looped through all subarrays without finding any that violate the increasing sum property, we return True.
C++
#include <iostream>#include <numeric> // include the <numeric> header for the accumulate function#include <vector>using namespace std;bool checkIncreasingSum(vector<vector<int>> arr) { int n = arr.size(); // get the number of subarrays in "arr" int prevSum = accumulate(arr[0].begin(), arr[0].end(), 0); // initialize "prevSum" to the sum of the first subarray for (int i = 1; i < n; i++) { // loop through the rest of the subarrays int curSum = accumulate(arr[i].begin(), arr[i].end(), 0); // calculate the sum of the current subarray if (curSum <= prevSum) { // if the current sum is less than or equal to the previous sum, return false; // return false (the sums are not increasing) } prevSum = curSum; // update "prevSum" to the current sum } return true; // if we have looped through all subarrays without finding any violations, return true}int main() { vector<vector<int>> arr = {{1, 2}, {2, 4}, {4, 5}, {6, 4}}; bool res = checkIncreasingSum(arr); // Calling the checkIncreasingSum // function on the input list if (res) { cout << "true" << endl; // If the returned value is true, print "true" } else { cout << "false" << endl; // If the returned value is false, print "false" } return 0;}// This code is contributed by rudra1807raj |
Java
import java.util.ArrayList;import java.util.List;public class Main { // Function to check if the sums of subarrays in a list of lists are increasing public static boolean checkIncreasingSum(List<List<Integer>> arr) { int n = arr.size(); // Get the number of subarrays in "arr" int prevSum = sumList(arr.get(0)); // Initialize "prevSum" to the sum of the first subarray for (int i = 1; i < n; i++) { // Loop through the rest of the subarrays int curSum = sumList(arr.get(i)); // Calculate the sum of the current subarray if (curSum <= prevSum) { // If the current sum is less than or equal to the previous sum, return false; // return false (the sums are not increasing) } prevSum = curSum; // Update "prevSum" to the current sum } return true; // If we have looped through all subarrays without finding any violations, return true } // Helper function to calculate the sum of a list of integers public static int sumList(List<Integer> list) { int sum = 0; for (int num : list) { sum += num; } return sum; } public static void main(String[] args) { List<List<Integer>> arr = new ArrayList<>(); arr.add(new ArrayList<>(List.of(1, 2))); arr.add(new ArrayList<>(List.of(2, 4))); arr.add(new ArrayList<>(List.of(4, 5))); arr.add(new ArrayList<>(List.of(6, 4))); boolean res = checkIncreasingSum(arr); // Calling the checkIncreasingSum function on the input list if (res) { System.out.println("true"); // If the returned value is true, print "true" } else { System.out.println("false"); // If the returned value is false, print "false" } }} |
Python3
def checkIncreasingSum(arr): n = len(arr) # get the number of subarrays in "arr" prevSum = sum(arr[0]) # initialize "prevSum" to the sum of the first subarray for i in range(1, n): # loop through the rest of the subarrays curSum = sum(arr[i]) # calculate the sum of the current subarray if curSum <= prevSum: # if the current sum is less than or equal to the previous sum, return False # return False (the sums are not increasing) prevSum = curSum # update "prevSum" to the current sum return True # if we have looped through all subarrays without finding any violations, return True arr = [[1, 2], [2, 4], [4, 5], [6, 4]]res = checkIncreasingSum(arr) # Calling the checkIncreasingSum# function on the input listif res: print("true") # If the returned value is true, print "true"else: print("false") # If the returned value is false, print "false" #This code is contributed by Siddharth Aher |
C#
using System;using System.Collections.Generic;using System.Linq;class Program{ static bool CheckIncreasingSum(List<List<int>> arr) { int n = arr.Count; // get the number of subarrays in "arr" int prevSum = arr[0].Sum(); // initialize "prevSum" to the sum of the first subarray for (int i = 1; i < n; i++) // loop through the rest of the subarrays { int curSum = arr[i].Sum(); // calculate the sum of the current subarray if (curSum <= prevSum) // if the current sum is less than or equal to the previous sum, { return false; // return false (the sums are not increasing) } prevSum = curSum; // update "prevSum" to the current sum } return true; // if we have looped through all subarrays without finding any violations, return true } static void Main() { List<List<int>> arr = new List<List<int>> { new List<int> {1, 2}, new List<int> {2, 4}, new List<int> {4, 5}, new List<int> {6, 4} }; bool res = CheckIncreasingSum(arr); // Calling the CheckIncreasingSum function on the input list if (res) { Console.WriteLine("true"); // If the returned value is true, print "true" } else { Console.WriteLine("false"); // If the returned value is false, print "false" } }}// This code is contributed by rudra1807raj |
Javascript
function checkIncreasingSum(arr) { let n = arr.length; // get the number of subarrays in "arr" let prevSum = arr[0].reduce((a, b) => a + b); // initialize "prevSum" to the sum of the first subarray for (let i = 1; i < n; i++) { // loop through the rest of the subarrays let curSum = arr[i].reduce((a, b) => a + b); // calculate the sum of the current subarray if (curSum <= prevSum) { // if the current sum is less than or equal to the previous sum, return false; // return False (the sums are not increasing) } prevSum = curSum; // update "prevSum" to the current sum } return true; // if we have looped through all subarrays without finding any violations, return True}let arr = [[1, 2], [2, 4], [4, 5], [6, 4]];let res = checkIncreasingSum(arr);// Calling the checkIncreasingSum// function on the input listif (res) { console.log("true"); // If the returned value is true, print "true"} else { console.log("false"); // If the returned value is false, print "false"} |
Output
true
Time Complexity: The time complexity of the “checkIncreasingSum” function using the single loop approach is O(n), where n is the number of subarrays in the input “arr”. This is because we are iterating over each subarray once and performing a constant amount of work for each subarray.
Auxiliary Space: The auxiliary space complexity of the above code is O(1), because the code only uses a constant amount of additional memory space to store the variables used within the function.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
