Largest Local Values in a Matrix

Difficulty: Easy | Acceptance: 87.70% | Paid: No Topics: Array, Matrix

You are given an n x n integer matrix grid.

Generate an integer matrix maxLocal of size (n - 2) x (n - 2) such that:

maxLocal[i][j] is equal to the largest value of the 3 x 3 matrix in grid centered around row i + 1 and column j + 1. In other words, we want to find the largest value in every contiguous 3 x 3 matrix in grid.

Return the generated matrix.

• Examples
• Constraints
• Direct Simulation
• Pre-computed Row Maxes

Examples

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 diagram above shows the original matrix and the generated matrix. Notice that the value of the generated matrix is the maximum value of the contiguous 3 x 3 matrix in the original matrix.

Example 2:

Input: grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1],[1,1,1,1,1]]
Output: [[1,1,1],[1,1,1],[1,1,1]]
Explanation: The original matrix and the generated matrix are the same because all values in the original matrix are 1.

Constraints

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

Direct Simulation

Intuition Since the grid size is small (n <= 100), we can simply iterate through every possible 3x3 submatrix. For each submatrix, we scan all 9 elements to find the maximum value and place it in the corresponding position in the result matrix.

Steps

• Initialize a result matrix of size (n-2) x (n-2).
• Iterate through the grid with row index i from 0 to n-3 and column index j from 0 to n-3. These indices represent the top-left corner of the 3x3 submatrix.
• For each (i, j), iterate through the 3 rows and 3 columns (offsets 0, 1, 2) to find the maximum value.
• Store the maximum value in the result matrix at position [i][j].
• Return the result matrix.

from typing import List

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        res = [[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(3):
                    for c in range(3):
                        max_val = max(max_val, grid[i + r][j + c])
                res[i][j] = max_val
        return res

Complexity

• Time: O(n²) - We iterate through (n-2)² positions, and for each, we check 9 elements. 9 is a constant, so it is O(n²).
• Space: O(n²) - To store the result matrix.
• Notes: This is the most straightforward approach and is efficient enough given the constraints.

Pre-computed Row Maxes

Intuition We can optimize the inner loop by pre-processing the grid. First, we calculate the maximum value for every horizontal window of size 3 in each row. Then, we calculate the maximum value for every vertical window of size 3 in the resulting matrix. This reduces the number of comparisons per cell from 9 to roughly 6 (3 for row max + 3 for col max), though the asymptotic complexity remains the same.

Steps

• Create a matrix rowMax of size n x (n-2).
• Iterate through each row i. For each column j from 0 to n-3, calculate max(grid[i][j], grid[i][j+1], grid[i][j+2]) and store it in rowMax[i][j].
• Create the result matrix of size (n-2) x (n-2).
• Iterate through each column j in rowMax. For each row i from 0 to n-3, calculate max(rowMax[i][j], rowMax[i+1][j], rowMax[i+2][j]) and store it in the result matrix.
• Return the result matrix.

from typing import List

class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        row_max = [[0] * (n - 2) for _ in range(n)]
        for i in range(n):
            for j in range(n - 2):
                row_max[i][j] = max(grid[i][j], grid[i][j+1], grid[i][j+2])
        
        res = [[0] * (n - 2) for _ in range(n - 2)]
        for j in range(n - 2):
            for i in range(n - 2):
                res[i][j] = max(row_max[i][j], row_max[i+1][j], row_max[i+2][j])
        return res

Complexity

• Time: O(n²) - We iterate through the grid a constant number of times.
• Space: O(n²) - We use an auxiliary matrix rowMax of size n x (n-2).
• Notes: This approach trades a bit of extra space for a potential reduction in constant-time operations, which can be beneficial for very large matrices.