Largest Local Values in a Matrix
Asked at OpenAI
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| OpenAI | EASY | View all OpenAI questions → |
How to Think About It
Brute force: for each cell in the output matrix, iterate over the 3x3 window and find the max.
This brute force is already O(n^2) since each 3x3 window has constant 9 cells.
No further optimization needed — the brute force IS optimal for this problem.
Simply use nested loops: outer two for output position, inner two for the 3x3 scan.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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 resultFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.