Matrix Range Query

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
3 upvotes
Asked in companies
AppleAmazon

Problem statement

You are given an 'N * M' matrix 'GRID'. You are also given 'Q' queries. Your task is to find the sum of the rectangular submatrix defined by the upper left corner and lower right corner for each query.

All indexes are 0 based.

Example:

'GRID' = [ [1, 2, 3],
           [4, 5, 6],
           [7, 8, 9] ]

'Q' = 1, left corner = (1, 1), right corner = (2, 2)
submatrix = [ [5, 6],
            [8, 9] ]   

Answer = 28
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test case follows.

The first line of each test case contains three space-separated integers ‘N’, ‘M’, ‘Q’ number of rows and number of columns in 'GRID' and number of queries. 

Then ‘N’ lines follow. Each of the lines contains ‘M’ space-separated integers denoting the elements of the matrix 'GRID'.

Then ‘Q’ lines follow. Each of the lines contains four space-separated integers ‘X1’, ‘Y1’, ‘X2’, ‘Y2’ where (‘X1’, ‘Y1’) is an upper left corner. (‘X2’, ‘Y2’) is the lower right corner.
Output Format: 
For each test case, return the array that contains sum of elements in the submatrix defined by the upper left and lower right corner for each query.
Note: 
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 5
1 <= N, M <= 10^3
-10^4 <= GRID[i][j] <= 10^4

Time Limit: 1 sec
Sample Input 1:
2
1 4 3
7 5 3 2 
0 0 0 1
0 0 0 2
0 0 0 3
2 2 1
1 1 
1 1
0 0 1 1
Sample Output 1:
12
15 
17
4
Explanation of Sample Input 1:
For the first test case, the first query submatrix is [[7, 5]]
For second query submatrix is [[7,5, 3]]
For third query submatrix is [[7, 5, 3, 2]]

For the second test case, first query submatrix is [[1, 1], [1, 1]]
Sample Input 2:
2
2 2 2
-1 1
1 -1
0 1 1 1
1 0 1 1
1 1 1
0
0 0 0 0
Sample Output 2:
0
0
0
Hint

For each query calculate the sum by brute force.

Approaches (2)
Brute force

We will iterate over the subgrid and calculate the sum of all elements in this subgrid of each query. 

The algorithm will be-

  1. For each query
    1. ‘SUM’ = 0
    2. For ‘ROW’ in ‘X1’ to ‘X2’
      1. For ‘COLUMN’ in ‘Y1’ to ‘Y2’
        1. ‘SUM += grid[ROW][COLUMN]'
    3. Print (SUM)
Time Complexity

O(Q*N*M)  where ‘N’, ‘M’, ‘Q’ are the number of rows, number of columns and number of queries respectively.

 

For each query, we will iterate over the subgrid defined by the top left corner and lower right corner.

Space Complexity

O(1),

 

As constant space is used.

Code Solution
(100% EXP penalty)
Matrix Range Query
Full screen
Console