💬 Discord
Sign In
NeetCode #892LC-2373EasyMath & Geometry
← Back to All Problems

#892 · #2373 · Largest Local Values in a Matrix(矩阵中的局部最大值)

📌 Problem Statement & Constraints

Given an n x n integer matrix grid, return an (n - 2) x (n - 2) matrix where each entry is the maximum value in the corresponding 3x3 submatrix of grid. Constraints: 3 <= n <= 100, 1 <= grid[i][j] <= 100.

💡 Core Algorithmic Approaches

  1. The output is (n - 2) x (n - 2), one entry per valid top-left corner of a 3x3 window.
  2. For output cell (i, j), the window spans rows i..i+2 and columns j..j+2.
  3. Take the maximum over those nine cells; there are exactly nine comparisons per output entry.
  4. The total work is therefore O(n^2), which is optimal at these bounds.

💻 Benchmark Python3 Implementation

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        res = [[0] * (n - 2) for _ in range(n - 2)]
        for i in range(n - 2):
            for j in range(n - 2):
                best = 0
                for di in range(3):
                    for dj in range(3):
                        best = max(best, grid[i + di][j + dj])
                res[i][j] = best
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2): a constant nine cells are examined per output entry.
💾 Space Complexity
O((n - 2)^2): the output matrix.

⚠️ Interview Pitfalls & Follow-ups

  • Allocating an n x n output: the result is (n - 2) x (n - 2).
  • Off-by-one in the window range: i must run over 0 .. n - 3, otherwise the last row or column of windows is missed.
  • Excluding the top-left cell from the maximum: it is part of the window and must be included.
  • Reusing a running maximum across columns: overlapping windows share cells, but a shared maximum would carry values from outside the current window.