On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.
Initially, some number of lamps are on. lamps[i] tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).
For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.
After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x, y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)
Return an array of answers. Each value answer[i] should be equal to the answer of the i-th query queries[i].
Example 1:
Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation:
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit. After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on. Now the query at [1,0] returns 0, because the cell is no longer lit.
Note:
1 <= N <= 10^9
0 <= lamps.length <= 20000
0 <= queries.length <= 20000
lamps[i].length == queries[i].length == 2
class Solution {
// Solution is O(N) Time & Space Complexity
Map<Integer, Integer> xMap, yMap, d1, d2;
// 4 map for 4 lines & 1 extra set for lamp positions
// Consider lines:
// 1) x=i (Storing value of x)
// 2) y=j (Storing value of y)
// 3) y=mx+c (d1 -> m=tan(45deg)=1) -> (y-x)=j-i (storing value of y-x)
// 4) y=mx+c (d2 -> m=tan(-45deg)=-1) -> (y+x)=j+i (storing value of y+x)
public int[] gridIllumination(int N, int[][] lamps, int[][] queries) {
xMap = new HashMap<>();
yMap = new HashMap<>();
d1 = new HashMap<>();
d2 = new HashMap<>();
Set<String> set = new HashSet<>();
for (int[] lamp : lamps) {
xMap.put(lamp[0], xMap.getOrDefault(lamp[0], 0) + 1);
yMap.put(lamp[1], yMap.getOrDefault(lamp[1], 0) + 1);
d1.put(lamp[1] - lamp[0], d1.getOrDefault(lamp[1] - lamp[1], 0) + 1);
d2.put(lamp[1] + lamp[0], d2.getOrDefault(lamp[1] + lamp[0], 0) + 1);
String key = Integer.toString(lamp[0]) + " " + Integer.toString(lamp[1]);
set.add(key);
}
int[][] dirs = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 } };
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int xCoord = queries[i][0], yCoord = queries[i][1];
if (xMap.containsKey(xCoord) || yMap.containsKey(yCoord) || d1.containsKey(yCoord - xCoord)
|| d2.containsKey(yCoord + xCoord)) {
ans[i] = 1;
String center = Integer.toString(xCoord) + " " + Integer.toString(yCoord);
if (set.contains(center)) {
set.remove(center);
removeLighting(xCoord, yCoord);
}
for (int[] dir : dirs) {
int newX = xCoord + dir[0], newY = yCoord + dir[1];
if (newX >= 0 && newX < N && newY >= 0 && newY < N) {
String lamp = Integer.toString(newX) + " " + Integer.toString(newY);
if (set.contains(lamp)) {
set.remove(lamp);
removeLighting(newX, newY);
}
}
}
} else
ans[i] = 0;
}
return ans;
}
public void removeLighting(int x, int y) {
xMap.put(x, xMap.get(x) - 1);
if (xMap.get(x) == 0)
xMap.remove(x);
yMap.put(y, yMap.get(y) - 1);
if (yMap.get(y) == 0)
yMap.remove(y);
d1.put(y - x, d1.get(y - x) - 1);
if (d1.get(y - x) == 0)
d1.remove(y - x);
d2.put(y + x, d2.get(y + x) - 1);
if (d2.get(y + x) == 0)
d2.remove(y + x);
}
}