Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

304. Range Sum Query 2D - Immutable

Time: $O(mn)$

Space: $O(mn)$

			


class NumMatrix {
 public:
  NumMatrix(vector<vector<int>>& matrix) {
    if (matrix.empty())
      return;

    const int m = matrix.size();
    const int n = matrix[0].size();
    // prefix[i][j] := sum of matrix[0..i)[0..j)
    prefix.resize(m + 1, vector<int>(n + 1));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        prefix[i + 1][j + 1] =
            matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
  }

  int sumRegion(int row1, int col1, int row2, int col2) {
    return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1] -
           prefix[row2 + 1][col1] + prefix[row1][col1];
  }

 private:
  vector<vector<int>> prefix;
};




			


class NumMatrix {
  public NumMatrix(int[][] matrix) {
    if (matrix.length == 0)
      return;

    final int m = matrix.length;
    final int n = matrix[0].length;
    // prefix[i][j] := sum of matrix[0..i)[0..j)
    prefix = new int[m + 1][n + 1];

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j)
        prefix[i + 1][j + 1] = matrix[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
  }

  public int sumRegion(int row1, int col1, int row2, int col2) {
    return prefix[row2 + 1][col2 + 1] - prefix[row1][col2 + 1]
         - prefix[row2 + 1][col1] + prefix[row1][col1];
  }

  private int[][] prefix;
}




			


class NumMatrix:
  def __init__(self, matrix: List[List[int]]):
    if not matrix:
      return

    m = len(matrix)
    n = len(matrix[0])
    # prefix[i][j] := sum of matrix[0..i)[0..j)
    self.prefix = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m):
      for j in range(n):
        self.prefix[i + 1][j + 1] = \
            matrix[i][j] + self.prefix[i][j + 1] + \
            self.prefix[i + 1][j] - self.prefix[i][j]

  def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
    return self.prefix[row2 + 1][col2 + 1] - self.prefix[row1][col2 + 1] - \
        self.prefix[row2 + 1][col1] + self.prefix[row1][col1]