1043. Grid Illumination
My accepted Python solution to LeetCode problem 1043, Grid Illumination, running in 187ms.
- Difficulty: Hard
- Python
- Runtime 187ms
- Memory 37.4MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 187ms, memory 37.4MB, accepted 2026-01-01.
class Solution:
def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
from collections import defaultdict
# Track counts for rows, cols, diagonals
rows = defaultdict(int)
cols = defaultdict(int)
diag1 = defaultdict(int) # r - c
diag2 = defaultdict(int) # r + c
# Set of active lamps
active = set()
for r, c in lamps:
if (r, c) not in active:
active.add((r, c))
rows[r] += 1
cols[c] += 1
diag1[r - c] += 1
diag2[r + c] += 1
result = []
for qr, qc in queries:
# Check if illuminated
if rows[qr] > 0 or cols[qc] > 0 or diag1[qr - qc] > 0 or diag2[qr + qc] > 0:
result.append(1)
else:
result.append(0)
# Turn off adjacent lamps (including the cell itself)
for dr in [-1, 0, 1]:
for dc in [-1, 0, 1]:
nr, nc = qr + dr, qc + dc
if (nr, nc) in active:
active.remove((nr, nc))
rows[nr] -= 1
cols[nc] -= 1
diag1[nr - nc] -= 1
diag2[nr + nc] -= 1
return result