2373. Largest Local Values in a Matrix - Explanation

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

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