Skip to main content
Talentd

Largest Local Values in a Matrix - Solution & Explanation

EasyArrayMatrix9 min readAsked at: Meta, Google, Bloomberg +1
Practice this problem

Problem Statement

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].length
  • 3 <= n <= 100
  • 1 <= 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.

In the C solution, we initialize an array to store the results of subproblems. We iterate through possible states and fill this array based on previous computations, adhering to the defined recurrence relation relevant for the problem.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Try this approach in the editor →

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.

In the C implementation, we iterate through each element, making what seems to be the optimal choice without revisiting previous choices. The greedy selection criteria are based on current state conditions.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n)
Space Complexity: O(n)

Greedy Approach

Time Complexity: O(n)
Space Complexity: O(1)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy 3x3 Window ScanO(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.

Video Solution

Largest Local Values in a Matrix - Leetcode 2373 - Python • NeetCodeIO • 11,420 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Largest Local Values in a Matrix with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays