LeetCode 2373 - Largest Local Values in a Matrix

LeetCode Problem 2373

Difficulty: 🟢 Easy
Topics: Array, Matrix

Solution

Problem Understanding

The problem gives us an n x n square matrix called grid, where each cell contains an integer value. Our task is to construct a new matrix called maxLocal, whose dimensions are (n - 2) x (n - 2).

For every valid position in the output matrix, we examine a contiguous 3 x 3 submatrix in grid. The center of this 3 x 3 window corresponds to row i + 1 and column j + 1, where (i, j) is the position in maxLocal. We must determine the largest value inside that 3 x 3 region and place it into maxLocal[i][j].

In simpler terms, imagine sliding a 3 x 3 window across the matrix from left to right and top to bottom. For every possible position of that window, we record the maximum number inside it.

For example, if the matrix is 4 x 4, there are only 2 x 2 valid 3 x 3 windows because the window cannot extend outside the boundaries. This explains why the result matrix always has dimensions (n - 2) x (n - 2).

The constraints tell us several important things:

• 3 <= n <= 100, meaning the matrix is relatively small.
• Every value is between 1 and 100.
• The matrix is always square.

Since n is at most 100, even solutions with nested loops are completely acceptable. We do not need highly advanced optimizations.

There are several important edge cases to consider. The smallest valid matrix size is 3 x 3, which means there is exactly one possible window and the output becomes a 1 x 1 matrix. Another important case is when all numbers are identical, since every output cell should have the same value. We also need to handle situations where the maximum value lies on the edge or corner of the 3 x 3 window, ensuring we inspect every cell in the region rather than only the center.

Approaches

Brute Force Approach

The most straightforward solution is to iterate over every possible 3 x 3 submatrix and explicitly examine all nine elements inside it.

For each valid top-left corner (row, col) of a 3 x 3 window, we scan the entire 3 x 3 area, compute the maximum value, and place it into the output matrix.

This approach is correct because every output cell corresponds exactly to one contiguous 3 x 3 region, and by checking every element inside that region we guarantee that the largest value is found.

The drawback is that we repeatedly inspect overlapping regions. Neighboring 3 x 3 windows share many cells, so some values are revisited multiple times. However, because the matrix size is small, this repeated work is not problematic.

Optimal Approach

The key observation is that the problem constraints are small enough that directly scanning each 3 x 3 window is already efficient.

Instead of attempting complicated preprocessing or sliding-window maximum optimizations, we simply iterate over every valid center position and compute the maximum of the surrounding 3 x 3 block.

Since each block contains exactly 9 cells, the work per window is constant. The number of windows is (n - 2)^2, so the total runtime remains efficient.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² × 9)	O((n - 2)²)	Explicitly scans all 9 cells in every 3 x 3 window
Optimal	O(n²)	O((n - 2)²)	Same practical strategy, since each window size is constant

Although both descriptions look similar, the important distinction is that the so-called brute force runtime simplifies to O(n²) because the 3 x 3 size is fixed and constant.

Algorithm Walkthrough

1. Determine the size of the input matrix n.
2. Create an empty result matrix with dimensions (n - 2) x (n - 2). This matrix will store the largest values for each 3 x 3 region.
3. Iterate through every valid top-left position of a 3 x 3 submatrix. Since a 3 x 3 window must stay within bounds, the row index ranges from 0 to n - 3, and the column index follows the same range.
4. For each position (row, col), initialize a variable to track the current maximum value.
5. Use two nested loops to examine all 9 cells inside the 3 x 3 region:

• Rows range from row to row + 2
• Columns range from col to col + 2

6. Update the maximum whenever a larger number is found.
7. Store the computed maximum into result[row][col].
8. After processing every valid window, return the completed result matrix.

Why it works

The algorithm works because every valid output position corresponds to exactly one contiguous 3 x 3 submatrix in the original grid. By exhaustively checking all nine cells inside each submatrix, we guarantee that the recorded value is the true maximum. Since every valid window is processed exactly once, every output cell is computed correctly.

Python Solution

from typing import List

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)

        result = [[0] * (n - 2) for _ in range(n - 2)]

        for row in range(n - 2):
            for col in range(n - 2):
                local_max = 0

                for r in range(row, row + 3):
                    for c in range(col, col + 3):
                        local_max = max(local_max, grid[r][c])

                result[row][col] = local_max

        return result

The implementation begins by determining the matrix size n. Since the output dimensions are always (n - 2) x (n - 2), we initialize the result matrix with zeros of the correct size.

The outer two loops iterate over every possible top-left position of a 3 x 3 window. For each window, local_max tracks the largest value encountered.

The inner nested loops scan exactly nine cells, covering the complete 3 x 3 region. During this scan, we repeatedly update local_max using Python's built-in max() function.

After inspecting the entire region, we place the computed maximum into the corresponding output position. Once every window has been processed, the final matrix is returned.

Go Solution

func largestLocal(grid [][]int) [][]int {
	n := len(grid)

	result := make([][]int, n-2)
	for i := range result {
		result[i] = make([]int, n-2)
	}

	for row := 0; row < n-2; row++ {
		for col := 0; col < n-2; col++ {
			localMax := 0

			for r := row; r < row+3; r++ {
				for c := col; c < col+3; c++ {
					if grid[r][c] > localMax {
						localMax = grid[r][c]
					}
				}
			}

			result[row][col] = localMax
		}
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version. The primary difference is memory allocation. In Go, we explicitly allocate the two-dimensional result slice using make().

Instead of using a built-in max() function, Go compares values manually with an if statement. Integer overflow is not a concern because the maximum grid value is only 100. Since the input constraints guarantee at least a 3 x 3 matrix, we do not need additional boundary validation.

Worked Examples

Example 1

Input

grid = [
  [9,9,8,1],
  [5,6,2,6],
  [8,2,6,4],
  [6,2,2,2]
]

Since n = 4, the output matrix size is 2 x 2.

Window 1, top-left at (0,0)

Submatrix:

9 9 8
5 6 2
8 2 6

Maximum value = 9

Result so far:

[
  [9, 0],
  [0, 0]
]

Window 2, top-left at (0,1)

Submatrix:

9 8 1
6 2 6
2 6 4

Maximum value = 9

Result so far:

[
  [9, 9],
  [0, 0]
]

Window 3, top-left at (1,0)

Submatrix:

5 6 2
8 2 6
6 2 2

Maximum value = 8

Result so far:

[
  [9, 9],
  [8, 0]
]

Window 4, top-left at (1,1)

Submatrix:

6 2 6
2 6 4
2 2 2

Maximum value = 6

Final result:

[
  [9, 9],
  [8, 6]
]

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]
]

Since n = 5, the output matrix size is 3 x 3.

The central 2 appears in every valid 3 x 3 region.

Window Position	Maximum
(0,0)	2
(0,1)	2
(0,2)	2
(1,0)	2
(1,1)	2
(1,2)	2
(2,0)	2
(2,1)	2
(2,2)	2

Final result:

[
  [2, 2, 2],
  [2, 2, 2],
  [2, 2, 2]
]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	We process (n - 2)² windows, each checking exactly 9 cells
Space	O((n - 2)²)	The output matrix stores one value per valid window

Although the algorithm contains four nested loops, the innermost work is bounded by a constant factor because every window always contains exactly 9 cells. Therefore, the runtime simplifies to O(n²) rather than O(n⁴).

Test Cases

solution = Solution()

# Example 1
assert solution.largestLocal([
    [9, 9, 8, 1],
    [5, 6, 2, 6],
    [8, 2, 6, 4],
    [6, 2, 2, 2]
]) == [[9, 9], [8, 6]]  # Standard example

# Example 2
assert solution.largestLocal([
    [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]
]) == [[2, 2, 2], [2, 2, 2], [2, 2, 2]]  # Central maximum

# Minimum valid matrix size
assert solution.largestLocal([
    [3, 7, 1],
    [2, 9, 4],
    [5, 6, 8]
]) == [[9]]  # Single 3x3 window

# All identical values
assert solution.largestLocal([
    [5, 5, 5],
    [5, 5, 5],
    [5, 5, 5]
]) == [[5]]  # Uniform values

# Maximum located in corner
assert solution.largestLocal([
    [100, 1, 1],
    [1, 1, 1],
    [1, 1, 1]
]) == [[100]]  # Corner maximum

# Larger matrix with varying values
assert solution.largestLocal([
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16]
]) == [[11, 12], [15, 16]]  # Increasing values

Test	Why
Example 1	Validates standard overlapping windows
Example 2	Verifies repeated maximum across all windows
Minimum 3 x 3 matrix	Confirms smallest valid input works
Uniform matrix	Ensures identical values are handled correctly
Corner maximum	Verifies edge positions are included in search
Increasing matrix	Tests overlapping windows with changing maxima

Edge Cases

Minimum Matrix Size, n = 3

The smallest valid input contains exactly one 3 x 3 region. This can be a source of off-by-one errors if loop boundaries are incorrect. Our implementation handles this naturally because n - 2 = 1, so the result matrix becomes 1 x 1, and exactly one window is processed.

Maximum Appears on the Border of the Window

A common mistake is accidentally ignoring boundary cells and focusing only on the center or interior. Since the problem asks for the largest value anywhere in the 3 x 3 region, maxima can appear in corners or edges. Our nested loops explicitly scan all nine positions, ensuring no cell is skipped.

Repeated or Identical Values

If all numbers are identical, every output entry should match that repeated value. Some implementations may incorrectly reset state between windows or mishandle comparisons. Because we recompute the maximum independently for every window, repeated values are processed correctly.

Highly Overlapping Windows

Neighboring 3 x 3 windows share many cells, which can sometimes lead to indexing mistakes when moving the window. Our implementation avoids this issue by independently iterating through each valid top-left coordinate and explicitly scanning the surrounding 3 x 3 region each time.