Sub Query Sum

Easy
0/40
Average time to solve is 10m
17 upvotes
Asked in companies
LinkedInMicrosoftBajaj Electricals Ltd

Problem statement

You have given a 2-dimensional array ‘ARR’ with ‘N’ rows and ‘M’ columns. The queries are given in a 2-dimensional array ‘Queries’ of size ‘K’, in which Queries[i] contains four integers denoting the left top and right bottom indices of the submatrix whose sum we need to find. Your task is to find the sum of the submatrix for each query given in the array ‘Queries’.

For example:

Consider ARR = [[1 , 2 , 3] , [3 , 4 , 1] , [2 , 1 , 2]] and Queries = [[0 , 0 , 1 , 2]], the submatrix with the left top index (0 , 0) and right bottom index (1 , 2) is  
                      [[1 , 2 , 3] , 
                       [3 , 4 , 1]]. 
The sum of the submatrix is 14. Hence, the answer is 14 in this case.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer, 'T,’ denoting the number of test cases.

The first line of each test case contains three space-separated integers, 'N', M’, and ‘K’, denoting the number of rows and the number of columns in the array 'ARR', and the number of rows in the array 'Queries' respectively.

The Next 'N' lines of each test case contain 'M' space-separated integers denoting the elements of the array 'ARR'.

The Next 'K' lines of each test case contain four space-separated integers denoting the elements of the array ‘Queries’.
Output Format: 
For each test case, print ‘K’ space-separated integers - the sum of the submatrix for each query.

Print the output of each test case in a separate line.
Constraints : 
 1 <= N <= 10 ^ 3     
 1 <= M <= 10 ^ 3
 1 <= K <= 10 ^ 3
 1 <= ARR[i][j] <= 10 ^ 6
 0 <= Queries[i][0] , Queries[i][2] < N
 0 <= Queries[i][1] , Queries[i][3] < M 

 Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of rows and the number of columns in the array ‘ARR’ respectively, ’K’ denotes the number of rows in the array ‘Queries’, 'ARR[i][j]' denotes the ’j-th’ element of  'i-th' row of the array 'ARR' and 'Queries[i]' contains four integers denoting the left top and right bottom indices of the submatrix.  

Time Limit: 1sec
Sample Input 1 :
2
2 2 1
4 2 
1 3 
0 0 1 0
3 3 2
2 1 2
3 2 6 
1 4 5
1 1 2 2
0 1 0 2
Sample Output 1 :
5
17 3
Explanation of sample input 1:
For the first test case, 
The submatrix with the left top index (0 , 0) and right bottom index (1 , 0) is  
                          [[4] , 
                           [1]]. 
The sum of the submatrix is 5. Hence, the answer is 5 in this case.

For the second test case,
The submatrix with the left top index (1 ,1) and right bottom index (2 , 2) is  
                          [[2 , 6] , 
                           [4 , 5]]. 
The sum of the submatrix is 17. Hence, the answer is 17 in this case.

 The submatrix with the left top index (0 , 1) and right bottom index (0 , 2) is  
                          [[1 , 2]].  
The sum of the submatrix is 3. Hence, the answer is 3 in this case.
Sample Input 2 :
2
2 2 2
5 6 
7 5 
0 0 0 0
0 0 1 1
3 3 2
3 4 3
4 3 4 
1 1 1
0 0 0 2
0 0 2 1
Sample Output 2 :
5 23
10 16
Hint

Traverse through the submatrix to find the sum of the submatrix for each query.

Approaches (2)
Brute Force

A simple method is to traverse through the submatrix, and we will find the sum of the submatrix for each query.
 

Our approach will be to create an array answer to store the sum of the submatrix for each query. We will iterate queryNumber from 0 to K - 1, and we will maintain a variable sum to store the sum of the submatrix of the current query.

  1. We iterate index from Queries[queryNumber][0] to Queries[queryNumber][2]. In each iteration, we will iterate pos from Queries[queryNumber][1] to Queries[queryNumber][3]. The element ARR[index][pos] is present in the submatrix. So, we will increment sum by ARR[index][pos].
  2. The variable sum stores the sum of the submatrix, and we will insert the variable sum in the array answer. 
     

In the end, we will return the array answer.
 

Algorithm:

 

  • Create an array answer of size K, which will store the sum of the submatrix for each query.
  • Iterate queryNumber from 0 to K - 1.
    • Set the variable sum as 0. The variable sum stores the sum of the submatrix of the current query.
    • Iterate index from Queries[queryNumber][0] to Queries[queryNumber][2].
      • Iterate pos from Queries[queryNumber][1] to Queries[queryNumber][2].
        • Increment sum by ARR[index][pos].
    • Insert sum in the array answer.
  • Return the array answer.
Time Complexity

O(N * M * K), where N and M denote the number of rows and columns in the array ARR and K denote the number of rows in the array Queries.
 

In the worst case, we are doing K iteration, and in each iteration, it takes O(N * M) to find the sum of the submatrix. Hence, the overall Time Complexity  = O(K) * (N * M) =  O(N * M * K).

Space Complexity

O(K), where K denotes the number of rows in the array Queries.
 

The Space Complexity O(K) is used to create an array to store the sum of the submatrix for each query. The overall Space Complexity is O(K).

Code Solution
(100% EXP penalty)
Sub Query Sum
Full screen
Console