2373. Largest Local Values in a Matrix - Explanation

Problem Link



Prerequisites

Before attempting this problem, you should be comfortable with:

  • 2D Arrays (Matrices) - Understanding how to traverse and access elements in a grid
  • Nested Loops - Iterating over both rows and columns, plus sub-regions within the matrix
  • Finding Maximum Values - Tracking the maximum element within a sliding window region

1. Iteration

Intuition

For each position in the output matrix, we need to find the maximum value in the corresponding 3x3 region of the input grid. The output matrix is (n-2) x (n-2) since we cannot center a 3x3 window on the edges. We simply iterate over all valid starting positions and scan the 3x3 window to find the maximum.

Algorithm

  1. Create an output matrix of size (n-2) x (n-2).
  2. For each position (i, j) in the output matrix:
    • Scan the 3x3 region starting at (i, j) in the input grid.
    • Find the maximum value among all 9 cells.
    • Store this maximum at position (i, j) in the output.
  3. Return the output matrix.
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):
                for r in range(i, i + 3):
                    for c in range(j, j + 3):
                        res[i][j] = max(res[i][j], grid[r][c])

        return res

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity:
    • O(1)O(1) extra space.
    • O(n2)O(n ^ 2) for the output array.

2. Generalized Approach (Sparse Table)

Intuition

While the simple iteration works well for a fixed 3x3 window, a Sparse Table allows us to answer any rectangular range maximum query in O(1) time after O(n^2 log^2 n) preprocessing. This is overkill for this specific problem but demonstrates a generalized technique useful when the window size varies or when we need to answer many range queries efficiently.

Algorithm

  1. Build a 2D Sparse Table during preprocessing:
    • sparseTable[r][c][i][j] stores the maximum in the submatrix starting at (r, c) with dimensions (2^i) x (2^j).
    • Build iteratively: first handle single rows/columns, then combine four quadrants for larger regions.
  2. For each query (x1, y1, x2, y2):
    • Compute the appropriate power-of-two dimensions that cover the range.
    • Combine up to four overlapping submatrices to get the maximum.
  3. Apply queries for each (n-k+1) x (n-k+1) output position with window size k=3.
class SparseTable:
    def __init__(self, grid: List[List[int]]):
        self.n = len(grid)
        self.LOG = [0] * (self.n + 1)
        for i in range(2, self.n + 1):
            self.LOG[i] = self.LOG[i // 2] + 1

        self.sparse_table = [[[[0] * (self.LOG[self.n] + 1) for _ in range(self.LOG[self.n] + 1)] for _ in range(self.n)] for _ in range(self.n)]

        for r in range(self.n):
            for c in range(self.n):
                self.sparse_table[r][c][0][0] = grid[r][c]

        for i in range(self.LOG[self.n] + 1):
            for j in range(self.LOG[self.n] + 1):
                for r in range(self.n - (1 << i) + 1):
                    for c in range(self.n - (1 << j) + 1):
                        if i == 0 and j == 0:
                            self.sparse_table[r][c][i][j] = grid[r][c]
                        elif i == 0:
                            self.sparse_table[r][c][i][j] = max(
                                self.sparse_table[r][c][i][j - 1],
                                self.sparse_table[r][c + (1 << (j - 1))][i][j - 1],
                            )
                        elif j == 0:
                            self.sparse_table[r][c][i][j] = max(
                                self.sparse_table[r][c][i - 1][j],
                                self.sparse_table[r + (1 << (i - 1))][c][i - 1][j],
                            )
                        else:
                            self.sparse_table[r][c][i][j] = max(
                                self.sparse_table[r][c][i - 1][j - 1],
                                self.sparse_table[r + (1 << (i - 1))][c][i - 1][j - 1],
                                self.sparse_table[r][c + (1 << (j - 1))][i - 1][j - 1],
                                self.sparse_table[r + (1 << (i - 1))][c + (1 << (j - 1))][i - 1][j - 1],
                            )

    def query(self, x1: int, y1: int, x2: int, y2: int) -> int:
        lx, ly = self.LOG[x2 - x1 + 1], self.LOG[y2 - y1 + 1]
        return max(
            self.sparse_table[x1][y1][lx][ly],
            self.sparse_table[x2 - (1 << lx) + 1][y1][lx][ly],
            self.sparse_table[x1][y2 - (1 << ly) + 1][lx][ly],
            self.sparse_table[x2 - (1 << lx) + 1][y2 - (1 << ly) + 1][lx][ly],
        )


class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        N, k = len(grid), 3
        sparse_table = SparseTable(grid)
        res = [[0] * (N - k + 1) for _ in range(N - k + 1)]

        for i in range(N - k + 1):
            for j in range(N - k + 1):
                res[i][j] = sparse_table.query(i, j, i + k - 1, j + k - 1)

        return res

Time & Space Complexity

  • Time complexity: O(n2log⁡2n)O(n ^ 2 \log ^ 2 n)
  • Space complexity:
    • O(n2log⁡2n)O(n ^ 2 \log ^ 2 n) extra space.
    • O((n−k)2)O((n - k) ^ 2) for the output matrix.

Where nn is the size of the given square grid and kk is the fixed size of the submatrix window.

Common Pitfalls

Incorrect Output Matrix Dimensions

For an n x n input grid with a 3 x 3 window, the output matrix should be (n-2) x (n-2), not n x n or (n-1) x (n-1). This is because the 3x3 window cannot be centered on edge cells. Miscalculating the output dimensions leads to array index out of bounds errors or incorrect results.

Off-by-One Errors in Window Boundaries

When iterating over the 3x3 window starting at position (i, j), the window spans rows i to i+2 and columns j to j+2 (inclusive). A common mistake is using i+3 or j+3 as the upper bound in exclusive loop conditions but then accessing indices incorrectly, or confusing whether loop bounds should be inclusive or exclusive.