# Range Sum Query 2D – Immutable (Leetcode 304)

Difficulty: Medium Link: Day 12: May Leetcode Challenge

## Problem Description

Given a 2D matrix `matrix`, handle multiple queries of the following type:

1. Calculate the sum of the elements of `matrix` inside the rectangle defined by its upper left corner `(row1, col1)` and lower right corner `(row2, col2)`.

Implement the NumMatrix class:

• `NumMatrix(int[][] matrix)` Initializes the object with the integer matrix `matrix`.
• `int sumRegion(int row1, int col1, int row2, int col2)` Returns the sum of the elements of `matrix` inside the rectangle defined by its upper left corner `(row1, col1)` and lower right corner `(row2, col2)`.

Example 1:

``````Input
["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]
Output
[null, 8, 11, 12]
Explanation NumMatrix numMatrix = new NumMatrix([[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]]); numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle) numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle) numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)
``````

## Constraints:

• `m == matrix.length`
• `n == matrix[i].length`
• `1 <= m, n <= 200`
• `-105 <= matrix[i][j] <= 105`
• `0 <= row1 <= row2 < m`
• `0 <= col1 <= col2 < n`
• At most `104` calls will be made to `sumRegion`.

## Solution

We can using brute force compute the sum by using a nested loop however it would be very computation expensive as the number of queries are every high. Using a nested loop would bound the operations by O(N2) and if 104 calls are made then total time computations would be (105)2 which would result in TLE(time limit exceeded) error. Can we do any pre-computation to save our time?

## Dynamic Programming

We can take the idea from Range sum query in 1D using prefix sums and extend our solution to 2D space. Using Dynamic Programming, we can build a prefix sum (dp) iteratively. Dp[i][j] would represent the sum of elements forming a rectangle from (0,0) to (i , j). We can compute the DP cells using the neighbour rows (top, left, diagonal top-left).

we can use a dynamic programming (DP) approach to build a prefix sum matrix (dp) from M iteratively, where dp[i][j] will represent the sum of the rectangle (0,0)->(i,j). The area of the rectangle formed by (row1, col1) and (row2, col2) can be computed from the sub rectangles in the region as follows:

• `matrix[row][col]` : The cell in original matrix at `(row, col)`.
• `dp[row - 1][col]` : The sum of region starting at `(0, 0)` and ending at cell `(row - 1, col)`.
• `dp[row][col - 1]` : The sum of region starting at `(0, 0)` and ending at cell `(row, col - 1)`.
• `-dp[row-1][col-1]` : The sum of region ending at `(row-1, col-1)` is added twice due to above to terms. So we subtract it once. Thus, `sums[row][col]` will store the sum of region ending at `(row, col)` and starting at origin.

We will also extra padding of a 1 extra row and column to avoid any bound checks. The first row and first column would always be zero and this help to handle in cases of empty sub-rectanges.

While returning the answer to range sum query, all we need to do is find the sum of rectangle bounded by row + 1, col + 1, and subtract the top (dp[row1, col2]) and left(dp[row2, col1]) rectangles and adding common region subtracted twice (bounded by dp[row1,col1]).

## Complexity Analysis

We are iterating the 2D matrix for calculating the DP array. Hence it will be O(MN) time and space for initialisation. However, it would be O(1) for every sumRegion call.

Time = O(MN) // Initialisation O(1) // Sum Region query

Space = O(MN) // DP array