Largest Local Values In A Matrix

Back to problems

Leetcode

Medium

Arrays

Matrices

Largest Local Values In A Matrix

Compute the maximum value inside every 3×3 submatrix of a square grid.

Acceptance 0%

Start Practice

Problem Statement

Given an $n \times n$ integer matrix grid, consider every contiguous $3 \times 3$ submatrix.

For each such submatrix, find the largest value inside it. Return a new matrix containing these maxima, where the value at position (i, j) corresponds to the maximum value in the 3 × 3 block whose top-left corner is (i, j).

The resulting matrix will have size $(n - 2) \times (n - 2)$ .

Solve this by examining all valid 3×3 neighborhoods and producing their local maximums.

Input Format

grid is an $n \times n$ integer matrix
n >= 3
Each output cell corresponds to one contiguous 3 × 3 submatrix of grid

Output Format

Return a matrix of size $(n - 2) \times (n - 2)$
ans[i][j] is the maximum element in grid[i..i+2][j..j+2]

Constraints

$3 \le n \le 100$
Elements may be any integers that fit in a standard 32-bit signed integer
Time complexity around $O(n^2)$ is expected

Examples

Sample cases returned by the problem API.

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 top-left 3×3 block has maximum 9. The top-right block also has maximum 9. The bottom-left block has maximum 8, and the bottom-right block has maximum 6.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress