Subgrid Sums

Given a rectangular RxC grid of integers, grid, with R > 0 and C > 0, return a new grid with the same dimensions where each cell [r, c] contains the sum of all the elements in the subgrid with [r, c] in the top-left corner and [R - 1, C - 1] in the bottom-right corner.

Example:

  • Input: grid = [[-1, 2, 3], [4, 0, 0], [-2, 0, 9]]
  • Output: [[15, 14, 12], [11, 9, 9], [7, 9, 9]]
1def subgridSums(grid: List[List[int]]) -> List[List[int]]:
2    R, C = len(grid), len(grid[0])
3    dp = [[0] * (C + 1) for _ in range(R + 1)]
4    result = [[0] * C for _ in range(R)]
5    
6    for r in range(R - 1, -1, -1):
7        for c in range(C - 1, -1, -1):
8            dp[r][c] = grid[r][c] + dp[r+1][c] + dp[r][c+1] - dp[r+1][c+1]
9            result[r][c] = dp[r][c]
10            
11    return result
Previous
Subgrid Maximums
Next
Matrix Operations (Rotate & In-place)
-1
2
3
4
0
0
-2
0
9
dp=Array(3)
r=2
c=2
Step 1 / 10
Step 1:
Initialize DP grid with 0s (size R+1 x C+1). Start from bottom-right.
Focus: select @ [8]
r=2c=2