Problem of The Day: Largest Local Values in a Matrix

Problem Statement

Intuition

Initially, I’ll iterate through the grid to identify each 3x3 subgrid, aiming to find the maximum value within each.

Approach

My plan is to traverse the grid and for each position, extract the corresponding 3x3 subgrid, and then find the maximum value within that subgrid. I’ll use a helper function getMaxLocal to accomplish this.

Complexity

• Time complexity: O(n^2)

• Space complexity: O(n^2)

Code

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        res = [[0] * (n - 2) for _ in range(n - 2)]

        def getMaxLocal(mat, r, c):
            max_val = 0
            for row in range(r, r + 3):
                for col in range(c, c + 3):
                    max_val = max(mat[row][col], max_val)
            return max_val

        for i in range(n - 2):
            for j in range(n - 2):
                res[i][j] = getMaxLocal(grid, i, j)

        return res