Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 2 Dec, 2020

Easy

```
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.
```

```
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â€™.
```

```
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.
```

```
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
```

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.

- 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]**. - 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**.

- 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]**.

- Increment

- Iterate
- Insert
**sum**in the array**answer**.

- Set the variable
- Return the array
**answer**.

The basic idea is to create a matrix **auxiliary** with **N** rows and **M** columns in which **auxiliary[r][c] **will store the sum of the submatrix from **(0 , 0)** to **(r , c)**. Using this idea, we can find the sum of the submatrix for each query in O(1) Space Complexity.

We can find the sum of the submatrix from **(r1 , c1) **to **(r2 , c2)** in the following way given below.

`sum = auxiliary[r2][c2] - auxiliary[r2][c1 - 1] - auxiliary[r1 - 1][c2] + auxiliary[r1- 1][c1 - 1]`

The element auxiliary[r2][c2] stores the sum of the submatrix from (0 , 0) to (r2 , c2), auxiliary[r1 - 1][c2] stores the sum of the submatrix from (0 , 0) to (r1 - 1 , c2), auxiliary[r2][c1 - 1] stores the sum of the submatrix from (0 , 0) to (r2 , c1 - 1), and auxiliary[r1 - 1][c1 - 1] stores the sum of the submatrix from (0 , 0) to (r1 - 1 , c1 - 1).

Our approach will be to create an array **answer** to store the sum of the submatrix for each query.

- First, we will create the Auxiliary matrix. We will iterate the variable
**index**from**1**to**N - 1,**and in each iteration, we will iterate**pos**from**0**to**M - 1**. We will increment**auxiliary[index][pos]**by**ARR[index][pos] + auxiliary[index - 1][pos]**. - We will iterate the variable
**index**from**0**to**N - 1,**and in each iteration, we will iterate**pos**from**1**to**M - 1**. We will increment**auxiliary[index][pos]**by**auxiliary[index][pos - 1].** - We have created the auxiliary matrix, which we will use to find the sum of the submatrix for each query. Now, we will find the sum of the submatrix for each query. We will iterate the variable
**queryNumber**from**0**to**K - 1**, and we will apply conditions to use the formula discussed above to find the sum of the submatrix. We will insert the sum of the submatrix of the current query in the array**answer**.

In the end, we will return the array **answer**.

- Create an array
**answer**of size**K**, which will store the sum of the submatrix for each query. - Create an array
**auxiliary**of size**N**and**columns**of size**M**. We will use this array to find the sum of the submatrix for each query. - Copy the first row of the array
**ARR**into the array**auxiliary**. - Iterate
**index**from**1**to**N - 1**.- Iterate
**pos**from**0**to**M - 1**.- Increment
**auxiliary[index][pos]**by**ARR[index][pos] + auxiliary[index - 1][pos]**.

- Increment

- Iterate
- Iterate
**index**from**0**to**N - 1**.- Iterate
**pos**from**1**to**M - 1**.- Increment
**auxiliary[index][pos]**by**auxiliary[index][pos - 1]**.

- Increment

- Iterate
- Iterate
**queryNumber**from**0**to**K - 1**.- Set the variable
**topRow**as**Queries[queryNumber][0]**,**topColumn**as**Queries[queryNumber][1]**,**bottomRow**as**Queries[queryNumber][2]**,**bottomColumn**as**Queries[queryNumber][3]**. - Set the variable
**sum**as**auxiliary[bottomRow][bottomColumn]**. The variable**sum**stores the sum of the submatrix of the current query. - Check if
**topRow**is more than 0.- Decrement
**sum**by**auxiliary[topRow - 1][bottomColumn]**.

- Decrement
- Check if
**topColumn**is more than 0.- Decrement
**sum**by**auxiliary[bottomRow][topColumn - 1]**.

- Decrement
- Check if
**topRow**and**topColumn**are more than 0.- Increment
**sum**by**auxiliary[topRow-1][topColumn-1]**.

- Increment
- Insert
**sum**in the array**answer**.

- Set the variable
- Return the array
**answer**.

Similar problems

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

King Placement

Moderate

Posted: 22 May, 2022

Ninja and the experiment

Moderate

Posted: 5 Sep, 2022

Search In A Sorted 2D Matrix

Moderate

Posted: 23 Nov, 2022

Spiral Matrix

Easy

Posted: 24 Nov, 2022