304. Range Sum Query 2D - Immutable #

Problem #

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
  [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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Problem Summary #

Given a 2D matrix, calculate the sum of the elements within a sub-rectangle whose upper-left corner is (row1, col1) and lower-right corner is (row2, col2).

Solution Ideas #

• This problem is an advanced version of the prefix sum for a one-dimensional array. Define f(x,y) as the sum of the elements inside the rectangle with upper-left corner (0,0) and lower-right corner (x,y). \[ f(i,j) = \sum_{x=0}^{i}\sum_{y=0}^{j} Matrix[x][y]\]

  \[ \begin{aligned} f(i,j) &= \sum_{x=0}^{i-1}\sum_{y=0}^{j-1} Matrix[x][y] + \sum_{x=0}^{i-1} Matrix[x][j] + \sum_{y=0}^{j-1} Matrix[i][y] + Matrix[i][j]\\ &= (\sum_{x=0}^{i-1}\sum_{y=0}^{j-1} Matrix[x][y] + \sum_{x=0}^{i-1} Matrix[x][j]) + (\sum_{x=0}^{i-1}\sum_{y=0}^{j-1} Matrix[x][y] + \sum_{y=0}^{j-1} Matrix[i][y]) - \sum_{x=0}^{i-1}\sum_{y=0}^{j-1} Matrix[x][y] + Matrix[i][j]\\ &= \sum_{x=0}^{i-1}\sum_{y=0}^{j} Matrix[x][y] + \sum_{x=0}^{i}\sum_{y=0}^{j-1} Matrix[x][y] - \sum_{x=0}^{i-1}\sum_{y=0}^{j-1} Matrix[x][y] + Matrix[i][j]\\ &= f(i-1,j) + f(i,j-1) - f(i-1,j-1) + Matrix[i][j] \end{aligned} \]

• Thus we get the recurrence relation: f(i, j) = f(i-1, j) + f(i, j-1) - f(i-1, j-1) + matrix[i][j]. To make the code easier to write, create a new m+1 * n+1 matrix, so there is no need to handle row = 0 and col = 0 separately. The derived formula above is also easy to understand if drawn as a diagram:

  

  In the left figure, the large rectangle consists of the pink rectangle + the green rectangle - the overlapping part of the pink and green rectangles + the yellow part. This corresponds to the recurrence formula derived above. The left figure shows the case where the rectangle’s upper-left corner is (0,0). The more general case is the right figure, where the upper-left corner is any coordinate, and the formula remains unchanged.

• Time complexity: initialization O(mn), query O(1). Space complexity O(mn)

Code #

package leetcode

type NumMatrix struct {
	cumsum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	if len(matrix) == 0 {
		return NumMatrix{nil}
	}
	cumsum := make([][]int, len(matrix)+1)
	cumsum[0] = make([]int, len(matrix[0])+1)
	for i := range matrix {
		cumsum[i+1] = make([]int, len(matrix[i])+1)
		for j := range matrix[i] {
			cumsum[i+1][j+1] = matrix[i][j] + cumsum[i][j+1] + cumsum[i+1][j] - cumsum[i][j]
		}
	}
	return NumMatrix{cumsum}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
	cumsum := this.cumsum
	return cumsum[row2+1][col2+1] - cumsum[row1][col2+1] - cumsum[row2+1][col1] + cumsum[row1][col1]
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */