Subgrid Sums

01 · Question

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]]

02 · Solution

Reference solution

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

Subgrid Maximums

Matrix Operations (Rotate & In-place)