Grid Illumination
Hard
You are given a 2D grid of size n x n where each cell of this grid has a lamp that is initially turned off. You want to write an algorithm to determine if a cell is illuminated by any of the lamps.
You are given a 2D array of lamp positions lamps, where lamps[i] = [row<sub>i</sub>, col<sub>i</sub>] indicates that the lamp at grid[row<sub>i</sub>][col<sub>i</sub>] is turned on. Even if the same lamp is listed more than once, it is turned on.
When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal.
You are also given another 2D array queries, where queries[j] = [row<sub>j</sub>, col<sub>j</sub>]. For the j<sup>th</sup> query, determine whether grid[row<sub>j</sub>][col<sub>j</sub>] is illuminated or not. After answering the j<sup>th</sup> query, turn off the lamp at grid[row<sub>j</sub>][col<sub>j</sub>] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[row<sub>j</sub>][col<sub>j</sub>].
Return an array of integers ans, where ans[j] should be 1 if the cell in the j<sup>th</sup> query was illuminated, or 0 if the lamp was not.
Example:
n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
In this example, the grid is 5x5. Lamps are turned on at [0,0] and [4,4]. The first query is for cell [1,1]. Since the lamp at [0,0] illuminates it diagonally, the answer is 1. After turning off lamps near [1,1], the second query for [1,0] is not illuminated, so the answer is 0.
Could you please provide an efficient algorithm to solve this problem, considering that n can be very large (up to 109) and the number of lamps and queries can be up to 20,000?
Solution
Naive Solution
A brute-force approach would involve simulating the grid and lamp states directly. For each query, we iterate through the lamps to check if the queried cell is illuminated. After answering the query, we iterate through the 9 cells (the queried cell and its 8 neighbors) and turn off any lamps present in those cells.
Code (Python):
def gridIllumination_naive(n, lamps, queries):
grid = [[0] * n for _ in range(n)]
lamps_set = set()
for r, c in lamps:
if (r, c) not in lamps_set:
lamps_set.add((r, c))
# "Turn on" the lamp (mark its position)
def is_illuminated(r, c):
for lamp_r, lamp_c in lamps_set:
if lamp_r == r or lamp_c == c or abs(lamp_r - r) == abs(lamp_c - c):
return 1
return 0
def turn_off_lamps(r, c):
for i in range(max(0, r - 1), min(n, r + 2)):
for j in range(max(0, c - 1), min(n, c + 2)):
if (i, j) in lamps_set:
lamps_set.remove((i, j))
ans = []
for r, c in queries:
ans.append(is_illuminated(r, c))
turn_off_lamps(r, c)
return ans
Time Complexity: O(m * q), where m is the number of lamps and q is the number of queries. For each query, we iterate through all the lamps to check if the cell is illuminated.
Space Complexity: O(m), where m is the number of lamps, to store the lamp positions.
Optimal Solution
To optimize, we can use hash maps to store the number of lamps in each row, column, and diagonal. This avoids iterating through all lamps for each query.
Algorithm:
- Initialization: Use four hash maps to store the counts of lamps in each row, column, main diagonal (row - col), and anti-diagonal (row + col). Also, maintain a set to store the exact coordinates of the lamps to facilitate turning them off.
- Lamp Illumination: For each lamp, increment the corresponding counts in the row, column, main diagonal, and anti-diagonal hash maps. Add the lamp coordinates to the set.
- Query Processing: For each query:
- Check if the queried cell is illuminated by checking the counts in the corresponding row, column, main diagonal, and anti-diagonal hash maps. If any of these counts are greater than 0, the cell is illuminated.
- Turn off the lamp at the queried cell and its 8 adjacent cells. Decrement the counts in the corresponding hash maps if a lamp is present and remove the lamp from the set.
- Return: Return the array of illumination results.
Code (Python):
def gridIllumination(n, lamps, queries):
row_counts = {}
col_counts = {}
diag1_counts = {}
diag2_counts = {}
lamps_set = set()
for r, c in lamps:
if (r, c) not in lamps_set:
lamps_set.add((r, c))
row_counts[r] = row_counts.get(r, 0) + 1
col_counts[c] = col_counts.get(c, 0) + 1
diag1_counts[r - c] = diag1_counts.get(r - c, 0) + 1
diag2_counts[r + c] = diag2_counts.get(r + c, 0) + 1
def turn_off_lamps(r, c):
for i in range(max(0, r - 1), min(n, r + 2)):
for j in range(max(0, c - 1), min(n, c + 2)):
if (i, j) in lamps_set:
lamps_set.remove((i, j))
row_counts[i] -= 1
col_counts[j] -= 1
diag1_counts[i - j] -= 1
diag2_counts[i + j] -= 1
ans = []
for r, c in queries:
if row_counts.get(r, 0) > 0 or col_counts.get(c, 0) > 0 or \
diag1_counts.get(r - c, 0) > 0 or diag2_counts.get(r + c, 0) > 0:
ans.append(1)
else:
ans.append(0)
turn_off_lamps(r, c)
return ans
Time Complexity: O(m + q), where m is the number of lamps and q is the number of queries. We iterate through the lamps once to initialize the hash maps and then iterate through the queries once. Turning off lamps takes constant time because the inner loops iterate a maximum of 9 times.
Space Complexity: O(m), where m is the number of lamps, to store the lamp positions and counts in the hash maps.
Edge Cases
- Duplicate Lamps: The problem states that even if a lamp is listed more than once, it is turned on. The solution handles this by using a
setto store lamp coordinates, ensuring that each lamp is only counted once. - Lamps Near the Edge: The
turn_off_lampsfunction handles lamps near the edges of the grid by usingmax(0, r - 1)andmin(n, r + 2)to ensure that the indices are within the valid range. - No Lamps: If there are no lamps, all queries should return 0.
- Large n: The value of
ncan be as large as 109, but this does not affect the space complexity because the space used depends on the number of lamps, not the size of the grid.
