Watch 10 video solutions for Largest Local Values in a Matrix, a easy level problem involving Array, Matrix. This walkthrough by NeetCodeIO has 11,074 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an n x n integer matrix grid.
Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:
maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1.In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.
Return the generated matrix.
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]] Explanation: 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]] Explanation: Notice that the 2 is contained within every contiguous 3 x 3 matrix in grid.
Constraints:
n == grid.length == grid[i].length3 <= n <= 1001 <= grid[i][j] <= 100Problem Overview: Given an n x n integer grid, compute a new matrix where each cell contains the maximum value inside the corresponding 3 x 3 submatrix of the original grid. The resulting matrix has size (n-2) x (n-2) because each result cell represents the largest element in a local window.
Approach 1: Greedy 3x3 Window Scan (O(n²) time, O(1) space)
The direct approach iterates over every possible 3 x 3 window in the grid. For each top-left position (i, j), scan the nine elements from grid[i..i+2][j..j+2] and track the maximum value. Store that value in the output matrix at position (i, j). Since each window checks exactly nine elements, the constant factor is small and the overall complexity becomes O(n²). This works well because the problem size is limited and no extra data structures are required.
The key idea is that each local region is independent. You simply iterate through the matrix using nested loops and compute the maximum within each small window. This approach relies only on basic iteration over an array and works naturally for problems involving fixed-size neighborhoods in a matrix.
Approach 2: Dynamic Programming / Precomputed Maximums (O(n²) time, O(n²) space)
Another strategy reduces repeated comparisons by precomputing maximum values. First compute horizontal maximums for every group of three consecutive elements in each row. Store these in an auxiliary matrix. Then compute vertical maximums across three consecutive rows using the intermediate results. Each step reuses previously computed maximums, avoiding repeated scans of the same cells.
This dynamic programming style approach transforms the problem into two passes: row preprocessing and column aggregation. The time complexity remains O(n²), but the number of repeated comparisons drops because each element contributes to multiple windows through cached results. The tradeoff is additional O(n²) memory for intermediate storage.
Recommended for interviews: The greedy window scan is what most interviewers expect. It is simple, readable, and clearly demonstrates how to iterate through a matrix while evaluating local neighborhoods. The dynamic programming version shows optimization thinking, but the brute window scan already achieves optimal asymptotic complexity for this problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy 3x3 Window Scan | O(n²) | O(1) | Best general solution. Simple nested loops scanning each 3x3 region. |
| Dynamic Programming (Precomputed Maximums) | O(n²) | O(n²) | Useful when reducing repeated comparisons or demonstrating preprocessing techniques. |