Largest Local Values in a Matrix solution and explanation
Google
9 more videos on this problem
Largest Local Values in a Matrix - Leetcode 2373 - PythonNeetCodeIO · 7:37 · 11K views
Largest Local Values in a Matrix | Easy | Leetcode 2373 | codestorywithMIKcodestorywithMIK · 13:00 · 6K views
2373. Largest Local Values in a Matrix | Leetcode Weekly Contest 306 | LeetCode 2373Bro Coders · 4:02 · 6K views
Leetcode 2373 Largest Local Values in a Matrix| Easy Peasy Matrix | Coding Decoded SDE SheetCoding Decoded · 4:49 · 4K views
Largest Local Values in a Matrix Leetcode 2373 Coding interview questionInterview Ready · 12:47 · 1K views
Leetcode 2373: Largest Local Values in a MatrixAlgorithms Casts · 5:37 · 1K views
2373. Largest Local Values in a Matrix (Leetcode Easy)Programming Live with Larry · 6:43 · 1K views
Largest Local Values in a Matrix (LeetCode 2373)CodeWithARB · 18:54 · 584 views
LeetCode 2373 : Largest Local Values in a Matrix | Solution in JAVAAmit Manjarly · 10:31 · 395 views
2373. Largest Local Values in a MatrixComprehensive Code · 7:23 · 151 views
The problem
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 the3 x 3matrix ingridcentered around rowi + 1and columnj + 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] <= 100
Approach overview
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.
Approach 1: Dynamic Programming Approach
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.
''' Python code for dynamic programming approach '''/* Java code for dynamic programming approach *//* C++ code for dynamic programming approach */// JavaScript code for dynamic programming approach/* C code for dynamic programming approach *//* C# code for dynamic programming approach */In Python, we use a list to accumulate results from the smallest subproblems to bigger ones. Python's dynamic typing and simplified syntax make handling lists easier.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 2: Greedy Approach
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.
''' Python code for greedy approach '''/* Java code for greedy approach *//* C++ code for greedy approach*/// JavaScript code for greedy approach/* C code for greedy approach *//* C# code for greedy approach */Python's inherent capabilities allow concise expression of greedy algorithms, where decision points are processed sequentially within a loop structure.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 3: Default Approach
function largestLocal(grid: number[][]): number[][] {
const n = grid.length;
const res = Array.from({ length: n - 2 }, () => new Array(n - 2).fill(0));
for (let i = 0; i < n - 2; i++) {
for (let j = 0; j < n - 2; j++) {
let max = 0;
for (let k = i; k < i + 3; k++) {
for (let z = j; z < j + 3; z++) {
max = Math.max(max, grid[k][z]);
}
}
res[i][j] = max;
}
}
return res;
}func largestLocal(grid [][]int) [][]int {
n := len(grid)
ans := make([][]int, n-2)
for i := range ans {
ans[i] = make([]int, n-2)
for j := 0; j < n-2; j++ {
for x := i; x <= i+2; x++ {
for y := j; y <= j+2; y++ {
ans[i][j] = max(ans[i][j], grid[x][y])
}
}
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n) |
| Greedy Approach | Time Complexity: O(n) |
| Default Approach | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Largest Local Values in a Matrix easy or hard?
Largest Local Values in a Matrix is categorized as an Easy problem. It focuses on basic matrix traversal and understanding fixed-size submatrix windows, making it a common warm-up problem for practicing array and grid manipulation.
Largest Local Values in a Matrix Python/Java solution
In Python or Java, the solution typically uses two nested loops to iterate through all valid 3x3 windows. Inside each iteration, another small loop checks the nine elements to compute the maximum. This keeps the implementation concise while maintaining O(n²) complexity.
How to solve Largest Local Values in a Matrix in O(n²)?
Iterate through the matrix and treat each cell (i, j) as the top-left corner of a 3x3 window. Scan the nine values from grid[i..i+2][j..j+2], compute their maximum, and place it into the output matrix. Because each window requires constant work, the full algorithm runs in O(n²).
What is the best approach for Largest Local Values in a Matrix?
The best approach scans every possible 3x3 window and computes the maximum element inside it. This greedy method runs in O(n²) time and O(1) extra space because each window contains only nine elements. The logic is straightforward and is typically the expected solution in coding interviews.
Is Largest Local Values in a Matrix asked at Google/Amazon/Meta?
Matrix traversal and local window problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may vary, similar questions involving sliding windows or neighborhood maximums in grids are common practice problems.
What data structure is used in Largest Local Values in a Matrix?
The problem primarily uses a 2D array (matrix). The algorithm relies on nested iteration over the matrix and constant-time comparisons to track the maximum value inside each 3x3 region.
What is the time complexity of Largest Local Values in a Matrix?
The optimal solution runs in O(n²) time where n is the grid dimension. You iterate through each valid top-left position of a 3x3 window and inspect nine elements. Since 9 is constant, the complexity scales with the number of windows in the matrix.