Leetcode 1001. Grid Illumination
Problem Explanation
This problem presents a N x N
grid in which each cell contains a lamp. The lamps may initially be on or off and their state is represented as a parameter. Each lamp can illuminate its x-axis, y-axis, and both diagonals, like a queen in a chess game.
We are also given a list of queries. Each query provides the coordinates of a cell and we need to determine whether the cell is illuminated by some lamp. If the cell (x, y) is illuminated, the answer to the query is 1 otherwise 0.
However, after each query, not only the lamp in the queried cell (if present) but all lamps that are directly or diagonally adjacent to the cell are turned off.
The output is an array containing the results (answers) to all queries.
Solution Explanation
This problem can be solved efficiently using the data structures unordered_map
and unordered_set
in C++. We use unordered_map
to keep track of the number of illuminated lamps in each row, column, and both diagonals, and unordered_set
to keep track of the coordinates of the lamps that are still on after each query.
In the beginning, all the lamps are turned on, so we update our unordered_map
and unordered_set
accordingly. Now for each query, we check if the cell at the query coordinates is illuminated, which can happen only if at least one lamp in the same row, column, or diagonal is turned on. If it is illuminated, we add 1 to our answer vector.
After checking, we turn off the lamps at and around the query coordinates if they are on, and again update our unordered_map
and set
correspondingly. If the cell is not illuminated, we add 0 to our answer vector.
An example
Suppose we have a 5x5 grid N=5
, initial lamp positions lamps=[[0,0],[4,4]]
, and queries queries=[[1,1],[1,0]]
1 2 3# After turning on the lamps at [0,0] and [4,4], the grid looks like this: 4 5 1 1 1 1 1 6 1 1 0 0 1 7 1 0 1 0 1 8 1 0 0 1 1 9 1 1 1 1 1 10 11# After the first query [1,1], lamps at [0,0] and [1,1] and adjacent to [1,1] are turned off. Now the grid looks like this: 12 0 0 0 1 1 13 0 0 0 0 1 14 0 0 0 0 1 15 0 0 0 1 1 16 1 1 1 1 1 17 18# After the second query at [1,0], the cell at [1,0] and its adjacent cells don't have any lamps, so the grid remains the same. The cell [1,0] is not illuminated, so we return 0. 19 20# Hence, the output is [1,0]
C++ Solution
1
2c++
3 class Solution {
4 public:
5 vector<int> gridIllumination(int n, vector<vector<int>>& lamps,
6 vector<vector<int>>& queries) {
7 vector<int> ans;
8 unordered_map<int, int> rows, cols, diag1, diag2;
9 unordered_set<pair<int, int>, pairHash> lampsSet;
10
11
12 for (vector<int>& lamp : lamps) {
13 int i = lamp[0];
14 int j = lamp[1];
15 if (lampsSet.insert({i, j}).second) {
16 ++rows[i];
17 ++cols[j];
18 ++diag1[i + j];
19 ++diag2[i - j];
20 }
21 }
22
23 for (const vector<int>& query : queries) {
24 int i = query[0];
25 int j = query[1];
26 if (rows[i] || cols[j] || diag1[i + j] || diag2[i - j]) {
27 ans.push_back(1);
28 for (int y = max(0, i - 1); y < min(n, i + 2); ++y)
29 for (int x = max(0, j - 1); x < min(n, j + 2); ++x)
30 if (lampsSet.erase({y, x})) {
31 --rows[y];
32 --cols[x];
33 --diag1[y + x];
34 --diag2[y - x];
35 }
36 } else {
37 ans.push_back(0);
38 }
39 }
40
41 return ans;
42 }
43
44 private:
45 struct pairHash {
46 size_t operator()(const pair<int, int>& p) const {
47 return p.first ^ p.second;
48 }
49 };
50};
Here, the struct pairHash
is used to create a hash function for pair<int, int>
, which is not provided in C++ STL.
Note: There are no direct equivalents of unordered_map
and unordered_set
in Python, Java, JavaScript, and C#. I'll use dictionaries in Python and Maps in Java and JavaScript to achieve similar functionality. The syntax and data structures used will be a little different in different languages, but the basic concept remains the same.# Python Solution
1 2python 3class Solution: 4 def gridIllumination(self, n: int, lamps: list[list[int]], queries: list[list[int]]) -> list[int]: 5 lampsSet = {(i, j) for i, j in lamps} 6 rows, cols, diag1, diag2 = [defaultdict(int) for _ in range(4)] 7 8 for i, j in lampsSet: 9 rows[i] += 1 10 cols[j] += 1 11 diag1[i+j] += 1 12 diag2[i-j] += 1 13 14 ans = [] 15 for qi, qj in queries: 16 if rows[qi] or cols[qj] or diag1[qi+qj] or diag2[qi-qj]: 17 ans.append(1) 18 for i, j in product(range(qi-1, qi+2), range(qj-1, qj+2)): 19 if (i, j) in lampsSet: 20 lampsSet.remove((i, j)) 21 rows[i] -= 1 22 cols[j] -= 1 23 diag1[i+j] -= 1 24 diag2[i-j] -= 1 25 else: 26 ans.append(0) 27 return ans
This solution is implemented in Python 3. The initial tuple is created using the set
data type. The defaultdict
type from collections
has been used to keep track of the count of active lamps in each row, column, and both diagonals, similar to what we did using unordered_map
in the C++ solution. The product
function from the itertools
module has been used to iterate over all the cells adjacent to each query cell.
JavaScript Solution
1
2javascript
3class Illumination {
4 constructor(n, lamps) {
5 this.n = n;
6 this.lampsSet = new Map();
7 this.rows = new Map();
8 this.cols = new Map();
9 this.diag1 = new Map();
10 this.diag2 = new Map();
11 for (let lamp of lamps) {
12 let i = lamp[0], j = lamp[1];
13 this.lampsSet.set(JSON.stringify([i,j]), true);
14 this.rows.set(i, (this.rows.get(i)||0) + 1);
15 this.cols.set(j, (this.cols.get(j)||0) + 1);
16 this.diag1.set(i + j, (this.diag1.get(i + j)||0) + 1);
17 this.diag2.set(i - j, (this.diag2.get(i - j)||0) + 1);
18 }
19 }
20
21 query(coord) {
22 let ans = [];
23 let i = coord[0], j = coord[1];
24 if (this.rows.get(i) || this.cols.get(j) || this.diag1.get(i+j) || this.diag2.get(i-j)) {
25 ans.push(1);
26 for(let y = Math.max(0, i - 1); y < Math.min(this.n, i + 2); y++) {
27 for(let x = Math.max(0, j - 1); x < Math.min(this.n, j + 2); x++) {
28 if (this.lampsSet.delete(JSON.stringify([y,x]))) {
29 this.rows.set(y, (this.rows.get(y)||0) - 1);
30 this.cols.set(x, (this.cols.get(x)||0) - 1);
31 this.diag1.set(y + x, (this.diag1.get(y + x)||0) - 1);
32 this.diag2.set(y - x, (this.diag2.get(y - x)||0) - 1);
33 }
34 }
35 }
36 } else {
37 ans.push(0);
38 }
39 return ans;
40 }
41}
In this JavaScript solution, JavaScript's Map
data structure is used to implement the functionality of unordered_map
and unordered_set
. The set
and get
methods are used to set values and get values from the map. The Math.max
and Math.min
functions are used to make sure that the query cell's adjacent cells are not out of the grid's bounds.
Java Solution
1
2java
3class Solution {
4 public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
5 Map<Integer, Integer> rows = new HashMap<>(), cols = new HashMap<>(),
6 diag1 = new HashMap<>(), diag2 = new HashMap<>();
7 Set<Pair<Integer,Integer>> lampsSet = new HashSet<>();
8
9 for(int[] lamp: lamps) {
10 int i = lamp[0], j = lamp[1];
11 rows.put(i, rows.getOrDefault(i, 0) + 1);
12 cols.put(j, cols.getOrDefault(j, 0) + 1);
13 diag1.put(i + j, diag1.getOrDefault(i + j, 0) + 1);
14 diag2.put(i - j, diag2.getOrDefault(i - j, 0) + 1);
15 lampsSet.add(new Pair<>(i,j));
16 }
17
18 int[] res = new int[queries.length];
19 for(int idx = 0; idx < queries.length; idx++) {
20 int[] query = queries[idx];
21 int i = query[0], j = query[1];
22 if (rows.getOrDefault(i, 0) > 0 || cols.getOrDefault(j, 0) > 0 ||
23 diag1.getOrDefault(i + j, 0) > 0 || diag2.getOrDefault(i - j, 0) > 0) {
24 res[idx] = 1;
25 for(int y = Math.max(0, i-1); y < Math.min(n, i+2); y++) {
26 for(int x = Math.max(0, j-1); x < Math.min(n, j+2); x++) {
27 if(lampsSet.remove(new Pair<>(y,x))) {
28 rows.put(y, rows.get(y) - 1);
29 cols.put(x, cols.get(x) - 1);
30 diag1.put(y + x, diag1.get(y + x) - 1);
31 diag2.put(y - x, diag2.get(y - x) - 1);
32 }
33 }
34 }
35 }else{
36 res[idx] = 0;
37 }
38 }
39 return res;
40 }
41}
In this Java solution, Map
and Set
from Java's collection framework, and Pair
from javafx.util are used to track the lamps and their illuminations. The getOrDefault
method is used to fetch a count from the map and gives a default value if the key is not present in the map. The remove
method is used to remove the lamp from the set after a query. The Math.max
and Math.min
functions are used to ensure all the query cell's adjacent cells are not out of the grid's bounds.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.