Largest Local Values in a Matrix - Solution & Explanation

Problem 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.