Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1001.html
1001. Grid Illumination
Level
Hard
Description
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^90 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == queries[i].length == 2
Solution
Use a set to store the positions of the lamps that are on. For a lamp at position (x, y), the corresponding element in the set is x * N + y.
If a lamp is on, then the row, the column and the two diagonals that the lamp is in are illuminated. Use four maps to store the rows, the columns and the diagonals in both directions that are illuminated, with counts maintained.
For each query in queries, obtain the row and the column. If the current position is illuminated in any map, the query result is 1. Otherwise, return 0.
After each query, turn off all lamps in the 3x3 area. It can be seen that if there are lamps to be turned off, then the query’s cell must be illuminated, so only turn of all lamps if the query’s cell is illuminated.
To turn off the lamps, first check whether the lamp is on, which is equivalent to whether the position is in the set. If so, remove the element from the set, and update the four maps, with the corresponding values of the keys decreased by 1. If a value becomes 0, then simply remove the entry from the map.
Finally, return the query result.
-
class Solution { public int[] gridIllumination(int N, int[][] lamps, int[][] queries) { Set<Long> set = new HashSet<Long>(); Map<Integer, Integer> rowMap = new HashMap<Integer, Integer>(); Map<Integer, Integer> columnMap = new HashMap<Integer, Integer>(); Map<Integer, Integer> diagonal1Map = new HashMap<Integer, Integer>(); Map<Integer, Integer> diagonal2Map = new HashMap<Integer, Integer>(); for (int[] lamp : lamps) { int row = lamp[0], column = lamp[1]; long position = (long) row * (long) N + (long) column; set.add(position); int rowCount = rowMap.getOrDefault(row, 0) + 1; rowMap.put(row, rowCount); int columnCount = columnMap.getOrDefault(column, 0) + 1; columnMap.put(column, columnCount); int diagonal1 = row - column; int diagonal1Count = diagonal1Map.getOrDefault(diagonal1, 0) + 1; diagonal1Map.put(diagonal1, diagonal1Count); int diagonal2 = row + column; int diagonal2Count = diagonal2Map.getOrDefault(diagonal2, 0) + 1; diagonal2Map.put(diagonal2, diagonal2Count); } int[][] directions = { {0, 0}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1} }; int queriesLength = queries.length; int[] queriesResult = new int[queriesLength]; for (int i = 0; i < queriesLength; i++) { int[] query = queries[i]; int queryRow = query[0], queryColumn = query[1]; boolean flag = false; if (rowMap.containsKey(queryRow) || columnMap.containsKey(queryColumn)) flag = true; else { int diagonal1 = queryRow - queryColumn, diagonal2 = queryRow + queryColumn; if (diagonal1Map.containsKey(diagonal1) || diagonal2Map.containsKey(diagonal2)) flag = true; } if (flag) { queriesResult[i] = 1; for (int[] direction : directions) { int row = queryRow + direction[0], column = queryColumn + direction[1]; int newDiagonal1 = row - column, newDiagonal2 = row + column; if (row >= 0 && row < N && column >= 0 && column < N) { long position = (long) row * (long) N + (long) column; if (set.remove(position)) { int rowCount = rowMap.get(row) - 1; if (rowCount > 0) rowMap.put(row, rowCount); else rowMap.remove(row); int columnCount = columnMap.get(column) - 1; if (columnCount > 0) columnMap.put(column, columnCount); else columnMap.remove(column); int diagonal1Count = diagonal1Map.get(newDiagonal1) - 1; if (diagonal1Count > 0) diagonal1Map.put(newDiagonal1, diagonal1Count); else diagonal1Map.remove(newDiagonal1); int diagonal2Count = diagonal2Map.get(newDiagonal2) - 1; if (diagonal2Count > 0) diagonal2Map.put(newDiagonal2, diagonal2Count); else diagonal2Map.remove(newDiagonal2); } } } } } return queriesResult; } } -
class Solution: def gridIllumination( self, n: int, lamps: List[List[int]], queries: List[List[int]] ) -> List[int]: points = set() rcnt, ccnt, dgcnt, udgcnt = Counter(), Counter(), Counter(), Counter() for r, c in lamps: if (r, c) not in points: points.add((r, c)) rcnt[r] += 1 ccnt[c] += 1 dgcnt[r - c] += 1 udgcnt[r + c] += 1 ans = [0] * len(queries) for i, q in enumerate(queries): r, c = q if rcnt[r] or ccnt[c] or dgcnt[r - c] or udgcnt[r + c]: ans[i] = 1 for a, b in [ (0, 1), (1, 0), (0, -1), (-1, 0), (0, 0), (1, 1), (-1, 1), (1, -1), (-1, -1), ]: x, y = r + a, c + b if (x, y) in points: points.remove((x, y)) rcnt[x] -= 1 ccnt[y] -= 1 dgcnt[x - y] -= 1 udgcnt[x + y] -= 1 return ans ############ # 1001. Grid Illumination # https://leetcode.com/problems/grid-illumination/ class Solution: def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]: rows, cols, a_diag, d_diag = Counter(), Counter(), Counter(), Counter() pos = set() for x, y in lamps: if (x, y) not in pos: pos.add((x, y)) rows[x] += 1 cols[y] += 1 a_diag[x + y] += 1 d_diag[x - y] += 1 res = [] for x, y in queries: if rows[x] > 0 or cols[y] > 0 or a_diag[x + y] > 0 or d_diag[x - y] > 0: res.append(1) for dx in range(x - 1, x + 2): for dy in range(y - 1, y + 2): if (dx, dy) in pos: pos.remove((dx, dy)) rows[dx] -= 1 cols[dy] -= 1 a_diag[dx + dy] -= 1 d_diag[dx - dy] -= 1 else: res.append(0) return res -
function gridIllumination( n: number, lamps: number[][], queries: number[][], ): number[] { let lights: Set<string> = new Set(); let rows: Map<number, number> = new Map(); // i let cols: Map<number, number> = new Map(); // j let mainDiagonal: Map<number, number> = new Map(); // i - j let subDiagonal: Map<number, number> = new Map(); // i + j for (let [i, j] of lamps) { let key = `${i},${j}`; if (lights.has(key)) continue; lights.add(key); rows.set(i, (rows.get(i) || 0) + 1); cols.set(j, (cols.get(j) || 0) + 1); mainDiagonal.set(i - j, (mainDiagonal.get(i - j) || 0) + 1); subDiagonal.set(i + j, (subDiagonal.get(i + j) || 0) + 1); } let ans: Array<number> = []; let directions = [ [-1, -1], [-1, 0], [-1, 1], [0, -1], [0, 0], [0, 1], [1, -1], [1, 0], [1, 1], ]; for (let [i, j] of queries) { // check const check = lights.has(`${i},${j}`) || rows.get(i) || cols.get(j) || mainDiagonal.get(i - j) || subDiagonal.get(i + j); ans.push(check ? 1 : 0); // close lamp for (let [dx, dy] of directions) { const [x, y] = [i + dx, j + dy]; let key = `${x},${y}`; if (x < 0 || x > n - 1 || y < 0 || y > n - 1 || !lights.has(key)) { continue; } lights.delete(key); rows.set(x, rows.get(x) - 1); cols.set(y, cols.get(y) - 1); mainDiagonal.set(x - y, mainDiagonal.get(x - y) - 1); subDiagonal.set(x + y, subDiagonal.get(x + y) - 1); } } return ans; } -
class Solution { public: vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) { auto f = [&](int i, int j) -> long long { return (long long) i * n + j; }; unordered_set<long long> s; unordered_map<int, int> row, col, diag1, diag2; for (auto& lamp : lamps) { int i = lamp[0], j = lamp[1]; if (!s.count(f(i, j))) { s.insert(f(i, j)); row[i]++; col[j]++; diag1[i - j]++; diag2[i + j]++; } } int m = queries.size(); vector<int> ans(m); for (int k = 0; k < m; ++k) { int i = queries[k][0], j = queries[k][1]; if (row[i] > 0 || col[j] > 0 || diag1[i - j] > 0 || diag2[i + j] > 0) { ans[k] = 1; } for (int x = i - 1; x <= i + 1; ++x) { for (int y = j - 1; y <= j + 1; ++y) { if (x < 0 || x >= n || y < 0 || y >= n || !s.count(f(x, y))) { continue; } s.erase(f(x, y)); row[x]--; col[y]--; diag1[x - y]--; diag2[x + y]--; } } } return ans; } }; -
func gridIllumination(n int, lamps [][]int, queries [][]int) []int { row, col, diag1, diag2 := map[int]int{}, map[int]int{}, map[int]int{}, map[int]int{} type pair struct{ x, y int } s := map[pair]bool{} for _, lamp := range lamps { i, j := lamp[0], lamp[1] p := pair{i, j} if !s[p] { s[p] = true row[i]++ col[j]++ diag1[i-j]++ diag2[i+j]++ } } m := len(queries) ans := make([]int, m) for k, q := range queries { i, j := q[0], q[1] if row[i] > 0 || col[j] > 0 || diag1[i-j] > 0 || diag2[i+j] > 0 { ans[k] = 1 } for x := i - 1; x <= i+1; x++ { for y := j - 1; y <= j+1; y++ { p := pair{x, y} if s[p] { s[p] = false row[x]-- col[y]-- diag1[x-y]-- diag2[x+y]-- } } } } return ans }