Problem Description

You have an n x n integer matrix called grid. Your task is to create a new matrix called maxLocal with dimensions (n - 2) x (n - 2).

For each position [i][j] in the maxLocal matrix, you need to find the maximum value from a 3 x 3 submatrix in the original grid. This 3 x 3 submatrix is centered at position [i + 1][j + 1] in the original grid.

To break this down:

• Each element maxLocal[i][j] corresponds to a 3 x 3 window in the original grid
• This window starts at position [i][i] and extends to position [i+2][j+2] in the grid
• You need to find the largest value among all 9 elements in this window
• This process is repeated for all possible 3 x 3 windows that fit completely within the original grid

For example, if you have a 5 x 5 grid, your result will be a 3 x 3 matrix where:

• maxLocal[0][0] = maximum value in the top-left 3 x 3 submatrix of grid (rows 0-2, columns 0-2)
• maxLocal[0][1] = maximum value in the 3 x 3 submatrix of grid (rows 0-2, columns 1-3)
• And so on for all positions

The function should return this newly generated maxLocal matrix containing all the local maximum values.

Intuition

The problem asks us to slide a 3 x 3 window across the entire grid and capture the maximum value from each window position. This is essentially a sliding window problem in 2D.

The key insight is understanding the relationship between indices in the result matrix and the original grid. If we want to fill position [i][j] in our result matrix, we need to look at a 3 x 3 region in the original grid starting from position [i][j].

Why does the result matrix have dimensions (n - 2) x (n - 2)? Because a 3 x 3 window needs at least 3 rows and 3 columns to fit. When we place this window at the top-left corner, it covers positions [0][0] to [2][2]. When we slide it to the rightmost valid position, it covers columns from n-3 to n-1. This gives us n - 2 possible horizontal positions. The same logic applies vertically.

The straightforward approach is to:

1. Create a result matrix of size (n - 2) x (n - 2)
2. For each position [i][j] in the result matrix, examine the corresponding 3 x 3 region in the original grid
3. Find the maximum value among those 9 elements
4. Store this maximum in result[i][j]

Since we need to check every element in each 3 x 3 submatrix, we use nested loops: the outer loops iterate through valid starting positions (i, j), and the inner loops scan through the 9 elements from [i][j] to [i+2][j+2] to find the maximum.

Solution Approach

The implementation follows a direct simulation approach using nested loops to process each possible 3 x 3 window.

First, we determine the size of the input grid: n = len(grid). Since each 3 x 3 window produces one element in the result, and we can have (n - 2) windows both horizontally and vertically, we initialize our result matrix:

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

Next, we iterate through each valid starting position for a 3 x 3 window. The outer loops run from 0 to n - 3 (inclusive), which is written as range(n - 2):

for i in range(n - 2):
    for j in range(n - 2):

For each position [i][j] in the result matrix, we need to find the maximum value in the corresponding 3 x 3 submatrix of the original grid. This submatrix spans:

• Rows from i to i + 2 (inclusive)
• Columns from j to j + 2 (inclusive)

The solution uses a generator expression with nested loops to find the maximum:

ans[i][j] = max(
    grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3)
)

This generator expression iterates through all 9 positions in the 3 x 3 window:

• x takes values i, i + 1, i + 2
• y takes values j, j + 1, j + 2

The max() function then returns the largest value among these 9 elements, which we store in ans[i][j].

Finally, after processing all possible windows, we return the completed result matrix ans.

The time complexity is O(n²) since we visit each position in the result matrix once, and for each position, we examine a constant number (9) of elements. The space complexity is O((n-2)²) for storing the result matrix.

Example Walkthrough

Let's walk through a concrete example with a 4x4 grid to understand how the solution works.

Input grid:

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

Since n = 4, our result matrix will be (4-2) x (4-2) = 2x2.

Step 1: Process position [0][0] in result matrix

We examine the 3x3 window starting at grid[0][0]:

[9, 9, 8]
[5, 6, 2]  
[8, 2, 6]

The maximum value among these 9 elements is 9. So ans[0][0] = 9

Step 2: Process position [0][1] in result matrix

We slide the window one column to the right, examining grid positions starting at [0][1]:

[9, 8, 1]
[6, 2, 6]
[2, 6, 4]

The maximum value among these 9 elements is 9. So ans[0][1] = 9

Step 3: Process position [1][0] in result matrix

We move the window down one row from the original position, examining grid positions starting at [1][0]:

[5, 6, 2]
[8, 2, 6]
[6, 2, 2]

The maximum value among these 9 elements is 8. So ans[1][0] = 8

Step 4: Process position [1][1] in result matrix

Finally, we examine the bottom-right 3x3 window starting at grid[1][1]:

[6, 2, 6]
[2, 6, 4]
[2, 2, 2]

The maximum value among these 9 elements is 6. So ans[1][1] = 6

Final result:

maxLocal = [[9, 9],
            [8, 6]]

The code achieves this by using nested loops where i and j range from 0 to 1 (n-2=2), and for each position, the inner generator expression examines all 9 elements in the corresponding 3x3 window to find the maximum value.

Solution Implementation

Time and Space Complexity

Time Complexity: O((n-2)² × 9) which simplifies to O(n²)

The code uses two nested loops that iterate from 0 to n-2, creating (n-2) × (n-2) iterations. For each iteration, it finds the maximum value in a 3×3 subgrid, which requires examining exactly 9 elements. Therefore, the total number of operations is (n-2) × (n-2) × 9. Since 9 is a constant and (n-2)² is asymptotically equivalent to n², the time complexity is O(n²).

Space Complexity: O((n-2)²) which simplifies to O(n²)

The algorithm creates a new 2D array ans with dimensions (n-2) × (n-2) to store the results. This requires (n-2)² space. The generator expression max(grid[x][y] for x in range(i, i + 3) for y in range(j, j + 3)) uses O(1) additional space as it doesn't create a list but iterates through values. Therefore, the overall space complexity is O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Confusion Between Result and Original Grid

One of the most common mistakes is confusing the indexing relationship between the result matrix and the original grid. Developers often mistakenly think that result[i][j] corresponds to a 3x3 window centered at grid[i][j], but it actually corresponds to a window starting at grid[i][j].

Incorrect approach:

# Wrong: Trying to center the window at (i+1, j+1)
for i in range(1, n-1):
    for j in range(1, n-1):
        result[i-1][j-1] = max(
            grid[x][y] 
            for x in range(i-1, i+2) 
            for y in range(j-1, j+2)
        )

Correct approach:

# Right: Window starts at (i, j)
for i in range(n - 2):
    for j in range(n - 2):
        result[i][j] = max(
            grid[x][y] 
            for x in range(i, i + 3) 
            for y in range(j, j + 3)
        )

2. Incorrect Result Matrix Dimensions

Another pitfall is creating the result matrix with wrong dimensions, such as n x n instead of (n-2) x (n-2).

Incorrect:

result = [[0] * n for _ in range(n)]  # Wrong size

Correct:

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

3. Off-by-One Errors in Loop Ranges

Developers might use incorrect loop boundaries, leading to either missing windows or index out of bounds errors.

Incorrect:

# Wrong: This would try to access grid[n-1][n-1] to grid[n+1][n+1]
for i in range(n - 1):  
    for j in range(n - 1):
        # This would cause index out of bounds

Correct:

for i in range(n - 2):  # Ensures the 3x3 window fits within bounds
    for j in range(n - 2):

4. Inefficient Maximum Finding

While not incorrect, manually iterating through all 9 elements can be verbose and error-prone:

Less efficient/more error-prone:

max_val = grid[i][j]
for di in range(3):
    for dj in range(3):
        max_val = max(max_val, grid[i + di][j + dj])
result[i][j] = max_val

Better approach (as shown in solution):

result[i][j] = max(
    grid[x][y] 
    for x in range(i, i + 3) 
    for y in range(j, j + 3)
)

5. Edge Case Handling

Forgetting to handle edge cases like when n < 3, which would result in an empty or invalid result matrix.

Solution: Add validation at the beginning:

if n < 3:
    return []  # No valid 3x3 windows possible