Subgrid Maximums

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 maximum 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, 5, 3], [4, -1, 0], [2, 0, 2]]
Output: [[5, 5, 3], [4, 2, 2], [2, 2, 2]]

02 · Solution

Reference solution

1def subgridMaximums(grid: List[List[int]]) -> List[List[int]]:
2    R, C = len(grid), len(grid[0])
3    dp = [[0] * C for _ in range(R)]
4    
5    for r in range(R - 1, -1, -1):
6        for c in range(C - 1, -1, -1):
7            val = grid[r][c]
8            right = dp[r][c+1] if c + 1 < C else float('-inf')
9            down = dp[r+1][c] if r + 1 < R else float('-inf')
10            dp[r][c] = max(val, right, down)
11            
12    return dp

Valid Sudoku

Subgrid Sums