Largest Local Values in a Matrix
Easy · Arrays & Hashing · Explanation and code example
Generalized Approach (Sparse Table)
How it works
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.
Steps
- 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.
- 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.
- Apply queries for each
(n-k+1) x (n-k+1)output position with window sizek=3.
Complexity
- Time complexity:
O(n ^ 2 log ^ 2 n) - Space complexity:
O(n ^ 2 log ^ 2 n)extra space.O((n - k) ^ 2)for the output matrix.
Where
nis the size of the given square grid andkis the fixed size of the submatrix window.
Things to watch for
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.
Python code example
from typing import List
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
C++ code example
class SparseTable {
public:
vector<vector<vector<vector<int>>>> sparseTable;
vector<int> log;
int n;
SparseTable(vector<vector<int>>& grid) {
n = grid.size();
log.resize(n + 1, 0);
for (int i = 2; i <= n; i++) {
log[i] = log[i / 2] + 1;
}
int maxLog = log[n];
sparseTable.resize(n, vector<vector<vector<int>>>(n, vector<vector<int>>(maxLog + 1, vector<int>(maxLog + 1))));
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
sparseTable[r][c][0][0] = grid[r][c];
}
}
for (int i = 0; i <= maxLog; i++) {
for (int j = 0; j <= maxLog; j++) {
for (int r = 0; r + (1 << i) <= n; r++) {
for (int c = 0; c + (1 << j) <= n; c++) {
if (i == 0 && j == 0) continue;
if (i == 0) {
sparseTable[r][c][i][j] = max(
sparseTable[r][c][i][j - 1],
sparseTable[r][c + (1 << (j - 1))][i][j - 1]
);
} else if (j == 0) {
sparseTable[r][c][i][j] = max(
sparseTable[r][c][i - 1][j],
sparseTable[r + (1 << (i - 1))][c][i - 1][j]
);
} else {
sparseTable[r][c][i][j] = max(
max(sparseTable[r][c][i - 1][j - 1], sparseTable[r + (1 << (i - 1))][c][i - 1][j - 1]),
max(sparseTable[r][c + (1 << (j - 1))][i - 1][j - 1],
sparseTable[r + (1 << (i - 1))][c + (1 << (j - 1))][i - 1][j - 1])
);
}
}
}
}
}
}
int query(int x1, int y1, int x2, int y2) {
int lx = log[x2 - x1 + 1];
int ly = log[y2 - y1 + 1];
return max(
max(sparseTable[x1][y1][lx][ly], sparseTable[x2 - (1 << lx) + 1][y1][lx][ly]),
max(sparseTable[x1][y2 - (1 << ly) + 1][lx][ly],
sparseTable[x2 - (1 << lx) + 1][y2 - (1 << ly) + 1][lx][ly])
);
}
};
class Solution {
public:
vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
int n = grid.size(), k = 3;
SparseTable st(grid);
vector<vector<int>> res(n - k + 1, vector<int>(n - k + 1));
for (int i = 0; i <= n - k; i++) {
for (int j = 0; j <= n - k; j++) {
res[i][j] = st.query(i, j, i + k - 1, j + k - 1);
}
}
return res;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.