You are given an n x n grid, some of whose cells contain lamps. Each lamp illuminates its entire row, column, and both diagonals (top-left to bottom-right, and top-right to bottom-left). You are also given a list of queries, where each query is a cell (row, col). For each query, you must determine whether the queried cell is illuminated by any lamp at that moment.
After checking illumination for a query, you must turn off any lamp that is in the cell queried or in any of its 8 adjacent cells (including diagonals). A lamp that is turned off no longer illuminates any cells for subsequent queries.
Return a list of integers, where each element is 1 if the corresponding query cell is illuminated, or 0 otherwise.
Constraints:
1 <= n <= 10^90 <= lamps.length <= 200000 <= queries.length <= 200000 <= row, col < nThe brute-force approach would be, for each query, to check all lamps and see if any lamp illuminates the query cell. However, with up to 20,000 lamps and 20,000 queries, and a grid size up to 109, this is too slow.
Instead, we need a way to quickly determine if any lamp is illuminating a given cell. Since a lamp illuminates its row, column, and both diagonals, we can keep track of how many lamps are currently illuminating each row, column, and diagonal, using hash maps. For each query, we can check these maps in constant time.
After each query, we need to turn off any lamp in the 3x3 area centered on the query cell. We must update our hash maps accordingly, ensuring that lamps are only removed once.
The main challenge is efficiently updating and querying the illumination status, while handling lamp removals correctly.
row_counts)col_counts)diag_counts, where row - col is constant)anti_diag_counts, where row + col is constant)(r, c):
row_counts[r], col_counts[c], diag_counts[r-c], or anti_diag_counts[r+c] is greater than zero. If any is, the cell is illuminated.
(r, c), check each cell. If there is a lamp at that cell, remove it from the set and decrement the counts in all four hash maps.
Input:
n = 5
lamps = [[0,0],[4,4]]
queries = [[1,1],[1,0]]
Step 1: Initialization
- Active lamps: {(0,0), (4,4)}
- row_counts: {0:1, 4:1}
- col_counts: {0:1, 4:1}
- diag_counts: {0:1, 0:1} (0-0=0, 4-4=0) => {0:2}
- anti_diag_counts: {0:1, 8:1} (0+0=0, 4+4=8)
Step 2: First Query (1,1)
- Is row_counts[1] > 0? No.
- Is col_counts[1] > 0? No.
- Is diag_counts[0] > 0? Yes (2).
- So, cell is illuminated. Output 1.
- Now, turn off any lamp in the 3x3 area centered at (1,1): check (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2). Only (0,0) is a lamp.
- Remove (0,0) from active lamps, decrement counts:
row_counts[0]: 0, col_counts[0]: 0, diag_counts[0]: 1, anti_diag_counts[0]: 0
Step 3: Second Query (1,0)
- Is row_counts[1] > 0? No.
- Is col_counts[0] > 0? No.
- Is diag_counts[1-0=1] > 0? No.
- Is anti_diag_counts[1+0=1] > 0? No.
- So, cell is not illuminated. Output 0.
- Turn off lamps in the 3x3 area centered at (1,0): (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1), (2,-1), (2,0), (2,1). Only (0,0) has already been removed, so nothing changes.
Final Output: [1, 0]
Brute-force Approach:
- For each query, check all lamps: O(Q * L), where Q is the number of queries and L is the number of lamps. This is too slow for large inputs.
Optimized Approach:
- Initialization: O(L), for processing all lamps.
- For each query:
The Grid Illumination problem is efficiently solved by using hash maps to keep track of how many lamps illuminate each row, column, and diagonal. By using a set to store lamp positions, we can efficiently remove lamps and update our counts. This approach allows us to answer each query in constant time and handle lamp removals efficiently, making the solution scalable to the large input sizes specified by the problem.
from collections import defaultdict
class Solution:
def gridIllumination(self, n, lamps, queries):
row = defaultdict(int)
col = defaultdict(int)
diag = defaultdict(int)
anti_diag = defaultdict(int)
lamp_set = set()
# Add unique lamps and count
for x, y in lamps:
if (x, y) in lamp_set:
continue
lamp_set.add((x, y))
row[x] += 1
col[y] += 1
diag[x - y] += 1
anti_diag[x + y] += 1
res = []
for x, y in queries:
if row[x] or col[y] or diag[x - y] or anti_diag[x + y]:
res.append(1)
else:
res.append(0)
# Turn off lamps in 3x3 area
for dx in [-1, 0, 1]:
for dy in [-1, 0, 1]:
nx, ny = x + dx, y + dy
if (nx, ny) in lamp_set:
lamp_set.remove((nx, ny))
row[nx] -= 1
col[ny] -= 1
diag[nx - ny] -= 1
anti_diag[nx + ny] -= 1
return res
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
class Solution {
public:
vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
unordered_map<int, int> row, col, diag, anti_diag;
unordered_set<long long> lamp_set;
for (auto &lamp : lamps) {
int x = lamp[0], y = lamp[1];
long long key = ((long long)x << 32) | y;
if (lamp_set.count(key)) continue;
lamp_set.insert(key);
row[x]++;
col[y]++;
diag[x - y]++;
anti_diag[x + y]++;
}
vector<int> res;
vector<pair<int, int>> dirs = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,0}, {0,1}, {1,-1}, {1,0}, {1,1}};
for (auto &q : queries) {
int x = q[0], y = q[1];
if (row[x] || col[y] || diag[x - y] || anti_diag[x + y]) {
res.push_back(1);
} else {
res.push_back(0);
}
// Turn off lamps in 3x3 area
for (auto &d : dirs) {
int nx = x + d.first, ny = y + d.second;
long long key = ((long long)nx << 32) | ny;
if (lamp_set.count(key)) {
lamp_set.erase(key);
row[nx]--;
col[ny]--;
diag[nx - ny]--;
anti_diag[nx + ny]--;
}
}
}
return res;
}
};
import java.util.*;
class Solution {
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> antiDiag = new HashMap<>();
Set<Long> lampSet = new HashSet<>();
for (int[] lamp : lamps) {
int x = lamp[0], y = lamp[1];
long key = ((long)x << 32) | y;
if (lampSet.contains(key)) continue;
lampSet.add(key);
row.put(x, row.getOrDefault(x, 0) + 1);
col.put(y, col.getOrDefault(y, 0) + 1);
diag.put(x - y, diag.getOrDefault(x - y, 0) + 1);
antiDiag.put(x + y, antiDiag.getOrDefault(x + y, 0) + 1);
}
int[] res = new int[queries.length];
int[][] dirs = {{-1,-1}, {-1,0}, {-1,1}, {0,-1}, {0,0}, {0,1}, {1,-1}, {1,0}, {1,1}};
for (int i = 0; i < queries.length; i++) {
int x = queries[i][0], y = queries[i][1];
if (row.getOrDefault(x, 0) > 0 ||
col.getOrDefault(y, 0) > 0 ||
diag.getOrDefault(x - y, 0) > 0 ||
antiDiag.getOrDefault(x + y, 0) > 0) {
res[i] = 1;
} else {
res[i] = 0;
}
for (int[] d : dirs) {
int nx = x + d[0], ny = y + d[1];
long key = ((long)nx << 32) | ny;
if (lampSet.contains(key)) {
lampSet.remove(key);
row.put(nx, row.get(nx) - 1);
col.put(ny, col.get(ny) - 1);
diag.put(nx - ny, diag.get(nx - ny) - 1);
antiDiag.put(nx + ny, antiDiag.get(nx + ny) - 1);
}
}
}
return res;
}
}
var gridIllumination = function(n, lamps, queries) {
const row = new Map(), col = new Map(), diag = new Map(), antiDiag = new Map();
const lampSet = new Set();
for (const [x, y] of lamps) {
const key = x + ',' + y;
if (lampSet.has(key)) continue;
lampSet.add(key);
row.set(x, (row.get(x) || 0) + 1);
col.set(y, (col.get(y) || 0) + 1);
diag.set(x - y, (diag.get(x - y) || 0) + 1);
antiDiag.set(x + y, (antiDiag.get(x + y) || 0) + 1);
}
const res = [];
const dirs = [[-1,-1], [-1,0], [-1,1], [0,-1], [0,0], [0,1], [1,-1], [1,0], [1,1]];
for (const [x, y] of queries) {
if ((row.get(x) || 0) > 0 ||
(col.get(y) || 0) > 0 ||
(diag.get(x - y) || 0) > 0 ||
(antiDiag.get(x + y) || 0) > 0) {
res.push(1);
} else {
res.push(0);
}
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
const key = nx + ',' + ny;
if (lampSet.has(key)) {
lampSet.delete(key);
row.set(nx, row.get(nx) - 1);
col.set(ny, col.get(ny) - 1);
diag.set(nx - ny, diag.get(nx - ny) - 1);
antiDiag.set(nx + ny, antiDiag.get(nx + ny) - 1);
}
}
}
return res;
};