Question Link

https://leetcode.com/problems/range-sum-query-2d-immutable/

Question Description

Given a 2D matrix matrix, and compute the range sum of row and columns
image.png
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]

Simulation

Solution 1: Brutal

Use two array for traversing.

Solution 2：DP + Prefix Sum

Use DP to compute below array
dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c]
6a0ce8cdb110362f54256a349f97b9f.png
Calculate the sum based on below formula
image.png
image.png
image.png
image.png
Sum(ABCD)=Sum(OD)−Sum(OB)−Sum(OC)+Sum(OA)

Implementation

Solution 1: Brutal Force

  1. class NumMatrix {
  2.     int [][] matrix;
  3.     public NumMatrix(int[][] matrix) {
  4.         this.matrix = matrix;
  5.     }
  7.     public int sumRegion(int row1, int col1, int row2, int col2) {
  8.         int sum = 0;
  9.         for (int i=row1;i<=row2;i++) {
  10.             for (int j=col1;j<=col2;j++) {
  11.                 sum+=matrix[i][j];
  12.             }
  13.         }
  14.         return sum;
  15.     }
  16. }

Solution 2: DP + Prefix Sum

  1. public class NumMatrix {
  2.     private int[][] dp;
  3.     public NumMatrix(int[][] matrix) {
  4.         if (matrix.length == 0 || matrix[0].length == 0) return;
  5.         dp = new int[matrix.length + 1][matrix[0].length + 1];
  6.         for (int r = 0; r < matrix.length; r++) {
  7.             for (int c = 0; c < matrix[0].length; c++) {
  8.                 dp[r + 1][c + 1] = dp[r + 1][c] + dp[r][c + 1] + matrix[r][c] - dp[r][c];
  9.             }
  10.         }
  11.     }
  12.     public int sumRegion(int row1, int col1, int row2, int col2) {
  13.         return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
  14.     }
  15. }