Problem
There is a 2D grid of size n x n where each cell of this grid has a lamp that is initially turned off.
You are given a 2D array of lamp positions lamps, where lamps[i] = [rowi, coli] indicates that the lamp at grid[rowi][coli] 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] = [rowj, colj]. For the jth query, determine whether grid[rowj][colj] is illuminated or not. After answering the jth query, turn off the lamp at grid[rowj][colj] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[rowj][colj].
Return **an array of integers *ans,* where ans[j] should be 1 if the cell in the jth query was illuminated, or 0 if the lamp was not.**
Example 1:
Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: We have the initial grid with all lamps turned off. In the above picture we see the grid after turning on the lamp at grid[0][0] then turning on the lamp at grid[4][4].
The 0th query asks if the lamp at grid[1][1] is illuminated or not (the blue square). It is illuminated, so set ans[0] = 1. Then, we turn off all lamps in the red square.
The 1st query asks if the lamp at grid[1][0] is illuminated or not (the blue square). It is not illuminated, so set ans[1] = 0. Then, we turn off all lamps in the red rectangle.
Example 2:
Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
Output: [1,1]
Example 3:
Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
Output: [1,1,0]
Constraints:
1 <= n <= 10^90 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == 20 <= rowi, coli < nqueries[j].length == 20 <= rowj, colj < n
Solution
class Solution {
public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
HashMap<Integer, Integer> row = new HashMap<>();
HashMap<Integer, Integer> col = new HashMap<>();
HashMap<Integer, Integer> d1 = new HashMap<>();
HashMap<Integer, Integer> d2 = new HashMap<>();
HashMap<Integer, Integer> cellno = new HashMap<>();
for (int[] lamp : lamps) {
int row1 = lamp[0];
int col1 = lamp[1];
row.put(row1, row.getOrDefault(row1, 0) + 1);
col.put(col1, col.getOrDefault(col1, 0) + 1);
d1.put((row1 + col1), d1.getOrDefault((row1 + col1), 0) + 1);
d2.put((row1 - col1), d2.getOrDefault((row1 - col1), 0) + 1);
int cell = row1 * n + col1;
cellno.put(cell, cellno.getOrDefault(cell, 0) + 1);
}
int[][] dir = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int row1 = queries[i][0];
int col1 = queries[i][1];
int cell = row1 * n + col1;
ans[i] =
(row.containsKey(row1)
|| col.containsKey(col1)
|| d1.containsKey(row1 + col1)
|| d2.containsKey(row1 - col1)
|| cellno.containsKey(cell))
? 1
: 0;
if (cellno.containsKey(cell)) {
int val = cellno.get(cell);
cellno.remove(cell);
if (row.containsKey(row1)) {
int rowval = row.get(row1);
rowval -= val;
if (rowval == 0) {
row.remove(row1);
} else {
row.put(row1, rowval);
}
}
if (col.containsKey(col1)) {
int colval = col.get(col1);
colval -= val;
if (colval == 0) {
col.remove(col1);
} else {
col.put(col1, colval);
}
}
if (d1.containsKey(row1 + col1)) {
int d1val = d1.get(row1 + col1);
d1val -= val;
if (d1val == 0) {
d1.remove(row1 + col1);
} else {
row.put((row1 + col1), d1val);
}
}
if (d2.containsKey(row1 - col1)) {
int d2val = d2.get(row1 - col1);
d2val -= val;
if (d2val == 0) {
d2.remove(row1 - col1);
} else {
d2.put((row1 - col1), d2val);
}
}
}
for (int[] ints : dir) {
int rowdash = row1 + ints[0];
int coldash = col1 + ints[1];
int cellno1 = rowdash * n + coldash;
if (cellno.containsKey(cellno1)) {
int val = cellno.get(cellno1);
cellno.remove(cellno1);
if (row.containsKey(rowdash)) {
int rowval = row.get(rowdash);
rowval -= val;
if (rowval == 0) {
row.remove(rowdash);
} else {
row.put(rowdash, rowval);
}
}
if (col.containsKey(coldash)) {
int colval = col.get(coldash);
colval -= val;
if (colval == 0) {
col.remove(coldash);
} else {
col.put(coldash, colval);
}
}
if (d1.containsKey(rowdash + coldash)) {
int d1val = d1.get(rowdash + coldash);
d1val -= val;
if (d1val == 0) {
d1.remove(rowdash + coldash);
} else {
row.put((rowdash + coldash), d1val);
}
}
if (d2.containsKey(rowdash - coldash)) {
int d2val = d2.get(rowdash - coldash);
d2val -= val;
if (d2val == 0) {
d2.remove(rowdash - coldash);
} else {
d2.put((rowdash - coldash), d2val);
}
}
}
}
}
return ans;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).