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.

Range Sum of a 2D matrix

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

Code

Swift

class NumMatrix {
var dp : [[Int]]
init(_ matrix: [[Int]]) {
let r = matrix.count , c = matrix[0].count
dp = Array(repeating: Array(repeating:0,count:c + 1), count:r + 1)
for i in 1r {
for j in 1c{
dp[i][j] += matrix[i 1][j 1] + dp[i 1][j] + dp[i][j 1] dp[i 1][j 1]
}
}
}
func sumRegion(_ row1: Int, _ col1: Int, _ row2: Int, _ col2: Int) -> Int {
return dp[row2 + 1][col2 + 1] dp[row1][col2 + 1] dp[row2 + 1][col1] + dp[row1][col1]
}
}
view raw range_sum_2D.swift hosted with ❤ by GitHub

Python

class NumMatrix:
def __init__(self, M: List[List[int]]):
ylen, xlen = len(M) + 1, len(M[0]) + 1
self.dp = [[0] * xlen for _ in range(ylen)]
for i in range(1, ylen):
for j in range(1, xlen):
self.dp[i][j] = M[i1][j1] + self.dp[i1][j] + self.dp[i][j1] self.dp[i1][j1]
def sumRegion(self, R1: int, C1: int, R2: int, C2: int) -> int:
return self.dp[R2+1][C2+1] self.dp[R2+1][C1] self.dp[R1][C2+1] + self.dp[R1][C1]
view raw range_sum_2D.py hosted with ❤ by GitHub

Java

class NumMatrix {
long[][] dp;
public NumMatrix(int[][] M) {
int ylen = M.length + 1, xlen = M[0].length + 1;
dp = new long[ylen][xlen];
for (int i = 1; i < ylen; i++)
for (int j = 1; j < xlen; j++)
dp[i][j] = M[i1][j1] + dp[i1][j] + dp[i][j1] dp[i1][j1];
}
public int sumRegion(int R1, int C1, int R2, int C2) {
return (int)(dp[R2+1][C2+1] dp[R2+1][C1] dp[R1][C2+1] + dp[R1][C1]);
}
}
view raw range_sum_2D.java hosted with ❤ by GitHub

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

Links

Prefix Sum | GeeksForGeeks

Dynamic Programming

Range Sum Query 1D | Leetcode

Leave a Reply

Your email address will not be published. Required fields are marked *