LeetCode-Range Sum Query 2D

Datetime:2016-08-23 01:20:24          Topic: LeetCode           Share

Given a 2D matrix matrix , find the sum of the elements inside the rectangle defined by its upper left corner ( row 1, col 1) and lower right corner ( row 2, col 2).

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 row 1 ≤ row 2 and col 1 ≤ col 2.

Solution:

 1 public class NumMatrix {
 2     int[][] sums;
 3     int rows, cols;
 4 
 5     public NumMatrix(int[][] matrix) {
 6         if (matrix.length==0 || matrix[0].length==0) return;
 7         
 8         rows = matrix.length;
 9         cols = matrix[0].length;
10         sums = new int[rows][cols];
11         
12         for (int i=0;i<rows;i++){
13             int sum = 0;
14             for (int j=0;j<cols;j++){
15                 int sumLastRow = (i==0) ? 0 : sums[i-1][j];
16                 sum += matrix[i][j];
17                 sums[i][j] = sum + sumLastRow;
18             }
19         }
20         
21     }
22 
23     public int sumRegion(int row1, int col1, int row2, int col2) {
24         if (rows==0 || cols==0) return 0;
25         
26         return getSum(row2,col2) - getSum(row2,col1-1) - getSum(row1-1,col2) + getSum(row1-1,col1-1);
27     }
28     
29     public int getSum(int row1, int col1){
30         if (row1<0 || col1<0 || row1>=rows || col1>=cols) return 0;
31         
32         return sums[row1][col1];
33     }
34 }
35 
36 
37 // Your NumMatrix object will be instantiated and called as such:
38 // NumMatrix numMatrix = new NumMatrix(matrix);
39 // numMatrix.sumRegion(0, 1, 2, 3);
40 // numMatrix.sumRegion(1, 2, 3, 4);




About List