LeetCode 1001: Grid Illumination (Hash Counters + 3×3 Lamp Deactivation)
LeetCode 1001Hash TableSimulationToday we solve LeetCode 1001 - Grid Illumination.
Source: https://leetcode.com/problems/grid-illumination/
English
Problem Summary
On an n x n grid, each lamp illuminates its row, column, main diagonal, and anti-diagonal. For each query cell, return whether it is illuminated, then turn off any lamp in the queried cell and its surrounding 8 neighbors.
Key Insight
Do not scan all lamps per query. Keep four hash counters:
row[x], col[y], diag[x-y], anti[x+y]. If any corresponding counter is positive, the query cell is illuminated.
Also keep an activeLamps set for exact lamp existence, so duplicate lamp inputs are ignored and deletions are O(1).
Algorithm Steps
1) Insert unique lamps into activeLamps and increment 4 counters.
2) For each query (r, c), check illumination via the counters.
3) For each of 9 cells in the 3×3 area centered at (r, c), if there is an active lamp, remove it and decrement counters.
4) Append 1/0 to answer.
Complexity Analysis
Let L be lamp count and Q query count.
Time: O(L + Q) average (each query checks O(1) counters + fixed 9 neighbors).
Space: O(L) for active lamp set and hash counters.
Common Pitfalls
- Forgetting to deduplicate initial lamps (causes over-counting).
- Using an unsafe key encoding that collides.
- Forgetting to update all four counters during lamp removal.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static final int[] DR = {-1,-1,-1,0,0,0,1,1,1};
private static final int[] DC = {-1,0,1,-1,0,1,-1,0,1};
public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
Map<Integer, Integer> row = new HashMap<>();
Map<Integer, Integer> col = new HashMap<>();
Map<Integer, Integer> diag = new HashMap<>();
Map<Integer, Integer> anti = new HashMap<>();
Set<Long> active = new HashSet<>();
for (int[] lamp : lamps) {
int r = lamp[0], c = lamp[1];
long key = (((long) r) << 32) ^ (c & 0xffffffffL);
if (!active.add(key)) continue;
row.put(r, row.getOrDefault(r, 0) + 1);
col.put(c, col.getOrDefault(c, 0) + 1);
diag.put(r - c, diag.getOrDefault(r - c, 0) + 1);
anti.put(r + c, anti.getOrDefault(r + c, 0) + 1);
}
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int r = queries[i][0], c = queries[i][1];
ans[i] = (row.getOrDefault(r, 0) > 0 ||
col.getOrDefault(c, 0) > 0 ||
diag.getOrDefault(r - c, 0) > 0 ||
anti.getOrDefault(r + c, 0) > 0) ? 1 : 0;
for (int k = 0; k < 9; k++) {
int nr = r + DR[k], nc = c + DC[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
long key = (((long) nr) << 32) ^ (nc & 0xffffffffL);
if (!active.remove(key)) continue;
dec(row, nr);
dec(col, nc);
dec(diag, nr - nc);
dec(anti, nr + nc);
}
}
return ans;
}
private void dec(Map<Integer, Integer> map, int key) {
int v = map.get(key);
if (v == 1) map.remove(key);
else map.put(key, v - 1);
}
}func gridIllumination(n int, lamps [][]int, queries [][]int) []int {
row := map[int]int{}
col := map[int]int{}
diag := map[int]int{}
anti := map[int]int{}
active := map[int64]bool{}
key := func(r, c int) int64 { return int64(r)<<32 ^ int64(uint32(c)) }
for _, l := range lamps {
r, c := l[0], l[1]
k := key(r, c)
if active[k] {
continue
}
active[k] = true
row[r]++
col[c]++
diag[r-c]++
anti[r+c]++
}
dr := []int{-1, -1, -1, 0, 0, 0, 1, 1, 1}
dc := []int{-1, 0, 1, -1, 0, 1, -1, 0, 1}
ans := make([]int, len(queries))
dec := func(m map[int]int, k int) {
m[k]--
if m[k] == 0 {
delete(m, k)
}
}
for i, q := range queries {
r, c := q[0], q[1]
if row[r] > 0 || col[c] > 0 || diag[r-c] > 0 || anti[r+c] > 0 {
ans[i] = 1
}
for t := 0; t < 9; t++ {
nr, nc := r+dr[t], c+dc[t]
if nr < 0 || nr >= n || nc < 0 || nc >= n {
continue
}
k := key(nr, nc)
if !active[k] {
continue
}
delete(active, k)
dec(row, nr)
dec(col, nc)
dec(diag, nr-nc)
dec(anti, nr+nc)
}
}
return ans
}class Solution {
public:
vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
unordered_map<int, int> row, col, diag, anti;
unordered_set<long long> active;
auto key = [](int r, int c) -> long long {
return (static_cast<long long>(r) << 32) ^ static_cast<unsigned int>(c);
};
for (auto& l : lamps) {
int r = l[0], c = l[1];
long long k = key(r, c);
if (active.count(k)) continue;
active.insert(k);
row[r]++; col[c]++; diag[r - c]++; anti[r + c]++;
}
vector<int> dr = {-1,-1,-1,0,0,0,1,1,1};
vector<int> dc = {-1,0,1,-1,0,1,-1,0,1};
vector<int> ans;
ans.reserve(queries.size());
auto dec = [](unordered_map<int, int>& m, int k) {
if (--m[k] == 0) m.erase(k);
};
for (auto& q : queries) {
int r = q[0], c = q[1];
bool on = row[r] > 0 || col[c] > 0 || diag[r - c] > 0 || anti[r + c] > 0;
ans.push_back(on ? 1 : 0);
for (int i = 0; i < 9; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
long long k = key(nr, nc);
if (!active.count(k)) continue;
active.erase(k);
dec(row, nr);
dec(col, nc);
dec(diag, nr - nc);
dec(anti, nr + nc);
}
}
return ans;
}
};from collections import Counter
class Solution:
def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
row = Counter()
col = Counter()
diag = Counter()
anti = Counter()
active = set()
for r, c in lamps:
k = (r << 32) ^ c
if k in active:
continue
active.add(k)
row[r] += 1
col[c] += 1
diag[r - c] += 1
anti[r + c] += 1
dirs = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 0), (0, 1),
(1, -1), (1, 0), (1, 1)]
ans = []
for r, c in queries:
ans.append(1 if (row[r] > 0 or col[c] > 0 or diag[r - c] > 0 or anti[r + c] > 0) else 0)
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if not (0 <= nr < n and 0 <= nc < n):
continue
k = (nr << 32) ^ nc
if k not in active:
continue
active.remove(k)
row[nr] -= 1
col[nc] -= 1
diag[nr - nc] -= 1
anti[nr + nc] -= 1
if row[nr] == 0: del row[nr]
if col[nc] == 0: del col[nc]
if diag[nr - nc] == 0: del diag[nr - nc]
if anti[nr + nc] == 0: del anti[nr + nc]
return ans/**
* @param {number} n
* @param {number[][]} lamps
* @param {number[][]} queries
* @return {number[]}
*/
var gridIllumination = function(n, lamps, queries) {
const row = new Map();
const col = new Map();
const diag = new Map();
const anti = new Map();
const active = new Set();
const key = (r, c) => `${r}#${c}`;
const inc = (m, k) => m.set(k, (m.get(k) || 0) + 1);
const dec = (m, k) => {
const v = (m.get(k) || 0) - 1;
if (v <= 0) m.delete(k);
else m.set(k, v);
};
for (const [r, c] of lamps) {
const k = key(r, c);
if (active.has(k)) continue;
active.add(k);
inc(row, r);
inc(col, c);
inc(diag, r - c);
inc(anti, r + c);
}
const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]];
const ans = [];
for (const [r, c] of queries) {
const on = (row.get(r) || 0) > 0 || (col.get(c) || 0) > 0 ||
(diag.get(r - c) || 0) > 0 || (anti.get(r + c) || 0) > 0;
ans.push(on ? 1 : 0);
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
const k = key(nr, nc);
if (!active.has(k)) continue;
active.delete(k);
dec(row, nr);
dec(col, nc);
dec(diag, nr - nc);
dec(anti, nr + nc);
}
}
return ans;
};中文
题目概述
在 n x n 棋盘上，每盏灯会照亮所在行、列、主对角线、副对角线。对每个查询点，先判断是否被照亮，再关闭该点及其周围 8 个格子中的所有灯。
核心思路
不能每次查询都遍历所有灯。维护四个哈希计数：
row[x]、col[y]、diag[x-y]、anti[x+y]。任一计数大于 0，说明该点被照亮。
再配合 activeLamps 集合记录当前仍开启的灯，既能去重初始输入，也能在 3×3 关闭阶段 O(1) 删除。
算法步骤
1）将所有初始灯去重后放入 activeLamps，并更新四类计数。
2）查询 (r, c) 时，通过四个计数 O(1) 判断是否照亮。
3）枚举以 (r, c) 为中心的 3×3 九个位置，若存在灯则关闭，并同步减少四类计数。
4）把每次查询结果 1/0 加入答案。
复杂度分析
设灯数量为 L、查询数量为 Q。
时间复杂度：O(L + Q)（每次查询固定最多处理 9 个邻居）。
空间复杂度：O(L)。
常见坑点
- 初始灯不去重会导致计数偏大。
- 坐标编码方式不当可能造成 key 冲突。
- 关灯时漏更新某一类计数，会让后续查询结果错误。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static final int[] DR = {-1,-1,-1,0,0,0,1,1,1};
private static final int[] DC = {-1,0,1,-1,0,1,-1,0,1};
public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
Map<Integer, Integer> row = new HashMap<>();
Map<Integer, Integer> col = new HashMap<>();
Map<Integer, Integer> diag = new HashMap<>();
Map<Integer, Integer> anti = new HashMap<>();
Set<Long> active = new HashSet<>();
for (int[] lamp : lamps) {
int r = lamp[0], c = lamp[1];
long key = (((long) r) << 32) ^ (c & 0xffffffffL);
if (!active.add(key)) continue;
row.put(r, row.getOrDefault(r, 0) + 1);
col.put(c, col.getOrDefault(c, 0) + 1);
diag.put(r - c, diag.getOrDefault(r - c, 0) + 1);
anti.put(r + c, anti.getOrDefault(r + c, 0) + 1);
}
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int r = queries[i][0], c = queries[i][1];
ans[i] = (row.getOrDefault(r, 0) > 0 ||
col.getOrDefault(c, 0) > 0 ||
diag.getOrDefault(r - c, 0) > 0 ||
anti.getOrDefault(r + c, 0) > 0) ? 1 : 0;
for (int k = 0; k < 9; k++) {
int nr = r + DR[k], nc = c + DC[k];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
long key = (((long) nr) << 32) ^ (nc & 0xffffffffL);
if (!active.remove(key)) continue;
dec(row, nr);
dec(col, nc);
dec(diag, nr - nc);
dec(anti, nr + nc);
}
}
return ans;
}
private void dec(Map<Integer, Integer> map, int key) {
int v = map.get(key);
if (v == 1) map.remove(key);
else map.put(key, v - 1);
}
}func gridIllumination(n int, lamps [][]int, queries [][]int) []int {
row := map[int]int{}
col := map[int]int{}
diag := map[int]int{}
anti := map[int]int{}
active := map[int64]bool{}
key := func(r, c int) int64 { return int64(r)<<32 ^ int64(uint32(c)) }
for _, l := range lamps {
r, c := l[0], l[1]
k := key(r, c)
if active[k] {
continue
}
active[k] = true
row[r]++
col[c]++
diag[r-c]++
anti[r+c]++
}
dr := []int{-1, -1, -1, 0, 0, 0, 1, 1, 1}
dc := []int{-1, 0, 1, -1, 0, 1, -1, 0, 1}
ans := make([]int, len(queries))
dec := func(m map[int]int, k int) {
m[k]--
if m[k] == 0 {
delete(m, k)
}
}
for i, q := range queries {
r, c := q[0], q[1]
if row[r] > 0 || col[c] > 0 || diag[r-c] > 0 || anti[r+c] > 0 {
ans[i] = 1
}
for t := 0; t < 9; t++ {
nr, nc := r+dr[t], c+dc[t]
if nr < 0 || nr >= n || nc < 0 || nc >= n {
continue
}
k := key(nr, nc)
if !active[k] {
continue
}
delete(active, k)
dec(row, nr)
dec(col, nc)
dec(diag, nr-nc)
dec(anti, nr+nc)
}
}
return ans
}class Solution {
public:
vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
unordered_map<int, int> row, col, diag, anti;
unordered_set<long long> active;
auto key = [](int r, int c) -> long long {
return (static_cast<long long>(r) << 32) ^ static_cast<unsigned int>(c);
};
for (auto& l : lamps) {
int r = l[0], c = l[1];
long long k = key(r, c);
if (active.count(k)) continue;
active.insert(k);
row[r]++; col[c]++; diag[r - c]++; anti[r + c]++;
}
vector<int> dr = {-1,-1,-1,0,0,0,1,1,1};
vector<int> dc = {-1,0,1,-1,0,1,-1,0,1};
vector<int> ans;
ans.reserve(queries.size());
auto dec = [](unordered_map<int, int>& m, int k) {
if (--m[k] == 0) m.erase(k);
};
for (auto& q : queries) {
int r = q[0], c = q[1];
bool on = row[r] > 0 || col[c] > 0 || diag[r - c] > 0 || anti[r + c] > 0;
ans.push_back(on ? 1 : 0);
for (int i = 0; i < 9; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
long long k = key(nr, nc);
if (!active.count(k)) continue;
active.erase(k);
dec(row, nr);
dec(col, nc);
dec(diag, nr - nc);
dec(anti, nr + nc);
}
}
return ans;
}
};from collections import Counter
class Solution:
def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
row = Counter()
col = Counter()
diag = Counter()
anti = Counter()
active = set()
for r, c in lamps:
k = (r << 32) ^ c
if k in active:
continue
active.add(k)
row[r] += 1
col[c] += 1
diag[r - c] += 1
anti[r + c] += 1
dirs = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 0), (0, 1),
(1, -1), (1, 0), (1, 1)]
ans = []
for r, c in queries:
ans.append(1 if (row[r] > 0 or col[c] > 0 or diag[r - c] > 0 or anti[r + c] > 0) else 0)
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if not (0 <= nr < n and 0 <= nc < n):
continue
k = (nr << 32) ^ nc
if k not in active:
continue
active.remove(k)
row[nr] -= 1
col[nc] -= 1
diag[nr - nc] -= 1
anti[nr + nc] -= 1
if row[nr] == 0: del row[nr]
if col[nc] == 0: del col[nc]
if diag[nr - nc] == 0: del diag[nr - nc]
if anti[nr + nc] == 0: del anti[nr + nc]
return ans/**
* @param {number} n
* @param {number[][]} lamps
* @param {number[][]} queries
* @return {number[]}
*/
var gridIllumination = function(n, lamps, queries) {
const row = new Map();
const col = new Map();
const diag = new Map();
const anti = new Map();
const active = new Set();
const key = (r, c) => `${r}#${c}`;
const inc = (m, k) => m.set(k, (m.get(k) || 0) + 1);
const dec = (m, k) => {
const v = (m.get(k) || 0) - 1;
if (v <= 0) m.delete(k);
else m.set(k, v);
};
for (const [r, c] of lamps) {
const k = key(r, c);
if (active.has(k)) continue;
active.add(k);
inc(row, r);
inc(col, c);
inc(diag, r - c);
inc(anti, r + c);
}
const dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,0],[0,1],[1,-1],[1,0],[1,1]];
const ans = [];
for (const [r, c] of queries) {
const on = (row.get(r) || 0) > 0 || (col.get(c) || 0) > 0 ||
(diag.get(r - c) || 0) > 0 || (anti.get(r + c) || 0) > 0;
ans.push(on ? 1 : 0);
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
const k = key(nr, nc);
if (!active.has(k)) continue;
active.delete(k);
dec(row, nr);
dec(col, nc);
dec(diag, nr - nc);
dec(anti, nr + nc);
}
}
return ans;
};
Comments