LC2373. Largest Local Values In a Matrix

Approach 1: Optimal

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        subgrid = [[0 for _ in range(n - 2)] for _ in range(n - 2)]
 
        for i in range(n - 2):
            for j in range(n - 2):  
                for r in range(i, i + 3):
                    for c in range(j, j + 3):
                        subgrid[i][j] = max(
                            subgrid[i][j],
                            grid[r][c]
                        )
        
        return subgrid

Complexity

Time: $O(n^2)$
Space: $O(n^2)$

Notes

Can optimize a bit better by unrolling the inner grid loop and inlining the cell references.

Other Languages