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.