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] <= 100The key idea in #2373 Largest Local Values in a Matrix is to evaluate every possible 3 x 3 submatrix inside the given grid and determine the largest value within each of those regions. Since the result matrix is smaller, each element in the output corresponds to the maximum value found in a local 3 x 3 window of the original matrix.
You can iterate through all valid starting positions of a 3 x 3 window in the matrix. For each position, scan the nine cells inside that window and track the maximum value. This value becomes the corresponding element in the result matrix.
This approach works efficiently because the window size is fixed. Instead of complex data structures, a straightforward traversal of neighboring cells is sufficient. The overall process involves scanning each possible window and computing its maximum value.
The time complexity is O(n²) for an n x n matrix because each cell participates in a constant-sized window check, while the additional space required (excluding the output matrix) remains O(1).
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Traverse each 3x3 submatrix and compute the maximum | O(n^2) | O(1) extra (excluding output matrix) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Use nested loops to run through all possible 3 x 3 windows in the matrix.
For each 3 x 3 window, iterate through the values to get the maximum value within the window.
This approach leverages dynamic programming techniques to break down the problem into overlapping subproblems and solve them using a bottom-up manner. The core idea is to store the results of subproblems to avoid redundant computations, therefore optimizing the solution.
Time Complexity: O(n)
Space Complexity: O(n)
1/* C# code for dynamic programming approach */The C# solution utilizes an array or list to keep track of computed subproblem values, offering a structured, object-oriented way to store and retrieve these precomputed results.
The greedy approach aims to find a solution by making the most favorable choice at every stage, intending to reach an overall optimal solution. This approach might not always work for all types of problems but can provide simpler solutions where applicable.
Time Complexity: O(n)
Space Complexity: O(1)
1Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like this are common in technical interviews because they test matrix traversal and careful indexing. While the exact question may not always appear, similar grid and sliding-window matrix problems are frequently asked in FAANG-style interviews.
The optimal approach is to iterate through every valid 3x3 submatrix in the grid and compute the maximum value within each window. Because the window size is fixed, checking all nine elements is efficient. This leads to an overall time complexity of O(n^2).
Each value in the output represents the maximum value from a 3x3 submatrix of the original grid. Because a 3x3 window cannot start near the matrix borders, the resulting matrix size becomes (n-2) x (n-2).
A simple 2D array traversal is sufficient for this problem. Since each local region is only 3x3, you do not need advanced data structures like heaps or deques. Basic nested loops over the matrix work effectively.
JavaScript enables us to apply a greedy strategy quite efficiently through loops. Given its flexibility with regard to data types, decisions are enacted succinctly.