#2373

Easy

LeetCode Problem Workspace

Largest Local Values in a Matrix

Find the largest value in every 3x3 submatrix of an n x n integer matrix efficiently using nested loops.

Problem Statement

Given an n x n integer matrix grid, generate a new matrix maxLocal of size (n - 2) x (n - 2). Each element of maxLocal should represent the maximum value within a contiguous 3 x 3 window in grid.

Return the maxLocal matrix after examining every possible 3 x 3 submatrix in grid. Ensure proper handling of all indices, as this pattern tests your ability to iterate correctly over matrix windows.

Examples

Example 1

Input: grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]

Output: [[9,9],[8,6]]

The diagram above shows the original matrix and the generated matrix. Notice that each value in the generated matrix corresponds to the largest value of a contiguous 3 x 3 matrix in grid.

Example 2

Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]

Output: [[2,2,2],[2,2,2],[2,2,2]]

Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.

Constraints

n == grid.length == grid[i].length
3 <= n <= 100
1 <= grid[i][j] <= 100

Solution Approach

Brute-force Nested Loops

Iterate over each possible top-left corner of a 3x3 submatrix using two nested loops. For each window, check all 9 elements to find the maximum. Append this maximum to the corresponding position in the result matrix.

Boundary-aware Indexing

Ensure loops stop at n-2 to avoid out-of-bounds errors. This pattern fails if you attempt to access indices beyond the grid size. Careful attention to loop limits guarantees correctness.

Matrix Construction

After computing each local maximum, store it in a new (n-2) x (n-2) matrix. This ensures the output matrix accurately represents largest local values, directly aligning with the problem's requirement.

Complexity Analysis

Metric	Value
Time	O(N \cdot N)
Space	O(N \cdot N)

Time complexity is O(n^2) because each element in the (n-2)x(n-2) output matrix requires checking 3x3 elements. Space complexity is O(n^2) for storing the result matrix of size (n-2)x(n-2).

What Interviewers Usually Probe

Check if candidate correctly identifies the 3x3 window pattern and iterates over all valid starting indices.
Observe whether candidate handles edge cases with the smallest possible matrix size, n=3.
Listen for explanations of how nested loops avoid out-of-bounds errors and maintain O(n^2) performance.

Common Pitfalls or Variants

Common pitfalls

Incorrectly iterating past n-2 causing index out-of-bounds errors.
Forgetting to initialize the local maximum properly within each 3x3 window.
Confusing row and column indices while populating the result matrix.

Follow-up variants

Find the minimum value in every 3x3 submatrix instead of the maximum.
Compute local sums or averages for each 3x3 window rather than maximums.
Extend the pattern to rectangular k x k submatrices for variable k.

FAQ

What is the main pattern in Largest Local Values in a Matrix?

The core pattern is scanning every 3x3 submatrix in a square matrix and finding its maximum, which requires careful nested loop iteration.

Can I solve this problem without nested loops?

For this size-constrained problem, nested loops are the simplest and clearest approach, although advanced sliding window techniques can optimize larger matrices.

What should I watch for to avoid mistakes?

Always ensure loops stop at n-2 to prevent out-of-bounds errors and correctly map each local maximum to the output matrix.

How does the output matrix size relate to the input?

If the input is n x n, the output matrix is (n-2) x (n-2) because each local 3x3 window contributes one maximum.

Is this problem considered easy or hard?

It is classified as Easy, focusing on array and matrix manipulation with nested loops, rather than complex algorithms.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#2392 build a matrix with conditions #2352 equal row and column pairs #2397 maximum rows covered by columns