Leetcode Problem 304. Range Sum Query 2D - Immutable

304. Range Sum Query 2D - Immutable

Leetcode Solutions

Caching Smarter with Cumulative Sum

  1. Initialize a cumulative sum matrix sum with the same dimensions as the input matrix plus one extra row and column (for easier calculations).
  2. Populate the sum matrix by iterating over the input matrix and updating sum[i+1][j+1] to be the sum of matrix[i][j] plus the values from the left and above, minus the value diagonally up-left to avoid double-counting.
  3. Implement sumRegion by applying the inclusion-exclusion principle to obtain the sum of the desired submatrix using the pre-computed sum matrix.
UML Thumbnail

Caching Rows

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...