EasyArrayMatrixUpdated Sep 2026

2373. Largest Local Values in a Matrix

Asked at OpenAI

Difficulty

Easy

Time

O(n^2)

Space

O(n^2)

Pattern

Array

Companies

1

Problem

You are given a square matrix grid of size n x n. Your job is to build a new, smaller matrix called maxLocal.

The new matrix has size (n - 2) x (n - 2). Each cell maxLocal[i][j] holds the largest value found in the 3 x 3 block of grid whose top-left corner is at row i, column j. In other words, that block covers rows i to i+2 and columns j to j+2.

So you slide a 3 x 3 window over every possible position in grid, and write down the maximum of the nine numbers inside it. Return the resulting matrix.

One 3x3 window becomes one output cell

grid012301239981562682646222The first window covers rows 0-2 and cols 0-2; its maxis 9maxLocal01019986The 2 x 2 answer: one max per window position
Each output cell is the maximum of a 3 x 3 block of the input, and the window slides one step at a time.

Constraints

  • ●n == grid.length == grid[i].length
  • ●3 <= n <= 100
  • ●1 <= grid[i][j] <= 100

Examples

Example 1
Inputgrid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
Output[[9,9],[8,6]]
WhyThe output is 2 x 2. For (0,0) the 3x3 block is rows 0-2, cols 0-2, and its largest value is 9. For (0,1) the block shifts one column right and the max is still 9. For (1,0) the block shifts one row down and the max is 8. For (1,1) the max is 6.
Example 2
Inputgrid = [[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]]
WhyThe value 2 sits in the middle of the 5 x 5 grid. Every 3 x 3 window in a 5 x 5 grid must cover the center cell, so every window contains that 2 and its max is 2.

Asked At

1 companies
CompanyDifficulty
OpenAIEasyView all OpenAI questions →

How to Think About It

1

Brute force: for each cell in the output matrix, iterate over the 3x3 window and find the max.

2

This brute force is already O(n^2) since each 3x3 window has constant 9 cells.

3

No further optimization needed — the brute force IS optimal for this problem.

4

Simply use nested loops: outer two for output position, inner two for the 3x3 scan.

5

Be careful with index bounds: output is (n-2) x (n-2) and the window starts at (i, j) in the original grid.

Optimal Approach

For each position (i, j) in the (n-2) x (n-2) output matrix, scan the 3x3 submatrix in the original grid starting at (i, j) and record the maximum value. The brute force approach of checking all 9 cells per position runs in O(n^2) total time, which is optimal since every output cell must be computed.

Slide the window and scan 9 cells

for i in 0..n-3for j in 0..n-3scan rows i..i+2, cols j..j+2write max to result[i][j]Four nested loops, but the two inner ones always runexactly 9 timesresult01019986Every output cell is filled exactly onceresult[i][j] = max(grid[r][c])for r in i..i+2, c in j..j+29 cells per output cell → O(n^2) total
Two loops pick the window, two inner loops scan it, and the biggest value found is written to the output.
ComplexityTime O(n^2)Space O(n^2)There are (n-2)^2 output cells and each one scans a fixed 9 cells, so the work grows with the number of cells; the output matrix itself takes O(n^2) space.

What Trips People Up in Real Interviews

1

Clarify the indexing: output[i][j] corresponds to the 3x3 window starting at grid[i][j].

2

Edge case: grid is less than 3x3 — the result would be empty (0x0), but constraints guarantee n >= 3.

3

This is a straightforward problem — use it to warm up and demonstrate clean code.

4

Discuss whether a dynamic programming approach (max of overlapping windows) would help — it does not here.

5

Keep the code simple and readable; interviewers appreciate clarity on easy problems.

Solution Code

O(n^2) time
def largestLocal(grid):
    n = len(grid)
    result = [[0] * (n - 2) for _ in range(n - 2)]
    for i in range(n - 2):
        for j in range(n - 2):
            max_val = 0
            for r in range(i, i + 3):
                for c in range(j, j + 3):
                    max_val = max(max_val, grid[r][c])
            result[i][j] = max_val
    return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Largest Local Values in a Matrix problem?

Given an n x n integer matrix grid, generate an (n-2) x (n-2) matrix maxLocal where maxLocal[i][j] equals the maximum value in the 3x3 submatrix centered at (i+1, j+1) of the original grid. That is, maxLocal[i][j] is the max of all values in grid from row i to i+2 and column j to j+2.

How do you solve Largest Local Values in a Matrix?

The optimal approach runs in O(n^2) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Largest Local Values in a Matrix?

Largest Local Values in a Matrix is asked at OpenAI. It is a easy difficulty problem.

What are common mistakes on Largest Local Values in a Matrix?
  • Clarify the indexing: output[i][j] corresponds to the 3x3 window starting at grid[i][j].
  • Edge case: grid is less than 3x3 — the result would be empty (0x0), but constraints guarantee n >= 3.
  • This is a straightforward problem — use it to warm up and demonstrate clean code.
  • Discuss whether a dynamic programming approach (max of overlapping windows) would help — it does not here.
  • Keep the code simple and readable; interviewers appreciate clarity on easy problems.