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 integersans _,_whereans[j]should be1 if the cell in thejth query was illuminated, or0 if the lamp was not.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2020/08/19/illu_1.jpg)

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.
![](https://assets.leetcode.com/uploads/2020/08/19/illu_step1.jpg)
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.
![](https://assets.leetcode.com/uploads/2020/08/19/illu_step2.jpg)

Example 2

1
2

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
Output: [1,1]

Example 3

1
2

Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
Output: [1,1,0]

Constraints

  • 1 <= n <= 10^9
  • 0 <= lamps.length <= 20000
  • 0 <= queries.length <= 20000
  • lamps[i].length == 2
  • 0 <= rowi, coli < n
  • queries[j].length == 2
  • 0 <= rowj, colj < n

Solution

Method 1 – Hash Map Counting and Set for Lamps

Intuition

We need to efficiently check if a cell is illuminated by any lamp in its row, column, or diagonals, and quickly turn off lamps in a 3x3 area after each query. We can use hash maps to count the number of lamps affecting each row, column, and diagonal, and a set to track lamp positions.

Approach

  1. Use hash maps to count the number of lamps in each row, column, diagonal, and anti-diagonal.
  2. Use a set to store the positions of all currently on lamps.
  3. For each query:
    • If the cell’s row, column, diagonal, or anti-diagonal has a lamp, it is illuminated.
    • After answering, turn off any lamp in the 3x3 area centered at the query cell, updating the hash maps and removing from the set.
  4. Return the results for all queries.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        unordered_map<int, int> row, col, diag, anti;
        set<pair<int, int>> s;
        for (auto& l : lamps) {
            int x = l[0], y = l[1];
            if (s.count({x, y})) continue;
            s.insert({x, y});
            row[x]++;
            col[y]++;
            diag[x - y]++;
            anti[x + y]++;
        }
        vector<int> ans;
        vector<pair<int, int>> dirs = {{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
        for (auto& q : queries) {
            int x = q[0], y = q[1];
            ans.push_back(row[x] || col[y] || diag[x - y] || anti[x + y] ? 1 : 0);
            for (auto& d : dirs) {
                int nx = x + d.first, ny = y + d.second;
                if (s.count({nx, ny})) {
                    s.erase({nx, ny});
                    row[nx]--;
                    col[ny]--;
                    diag[nx - ny]--;
                    anti[nx + ny]--;
                }
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

func gridIllumination(n int, lamps [][]int, queries [][]int) []int {
    row, col, diag, anti := map[int]int{}, map[int]int{}, map[int]int{}, map[int]int{}
    s := map[[2]int]bool{}
    for _, l := range lamps {
        x, y := l[0], l[1]
        key := [2]int{x, y}
        if s[key] { continue }
        s[key] = true
        row[x]++
        col[y]++
        diag[x-y]++
        anti[x+y]++
    }
    dirs := [][2]int{{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}}
    ans := make([]int, len(queries))
    for i, q := range queries {
        x, y := q[0], q[1]
        if row[x] > 0 || col[y] > 0 || diag[x-y] > 0 || anti[x+y] > 0 {
            ans[i] = 1
        }
        for _, d := range dirs {
            nx, ny := x+d[0], y+d[1]
            key := [2]int{nx, ny}
            if s[key] {
                s[key] = false
                row[nx]--
                col[ny]--
                diag[nx-ny]--
                anti[nx+ny]--
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Map<Integer, Integer> row = new HashMap<>(), col = new HashMap<>(), diag = new HashMap<>(), anti = new HashMap<>();
        Set<Long> s = new HashSet<>();
        for (int[] l : lamps) {
            int x = l[0], y = l[1];
            long key = ((long)x << 32) | y;
            if (s.contains(key)) continue;
            s.add(key);
            row.put(x, row.getOrDefault(x, 0) + 1);
            col.put(y, col.getOrDefault(y, 0) + 1);
            diag.put(x - y, diag.getOrDefault(x - y, 0) + 1);
            anti.put(x + y, anti.getOrDefault(x + y, 0) + 1);
        }
        int[] ans = new int[queries.length];
        int[][] dirs = {{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0], y = queries[i][1];
            if (row.getOrDefault(x,0) > 0 || col.getOrDefault(y,0) > 0 || diag.getOrDefault(x-y,0) > 0 || anti.getOrDefault(x+y,0) > 0) {
                ans[i] = 1;
            }
            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                long key = ((long)nx << 32) | ny;
                if (s.contains(key)) {
                    s.remove(key);
                    row.put(nx, row.getOrDefault(nx,0)-1);
                    col.put(ny, col.getOrDefault(ny,0)-1);
                    diag.put(nx-ny, diag.getOrDefault(nx-ny,0)-1);
                    anti.put(nx+ny, anti.getOrDefault(nx+ny,0)-1);
                }
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    fun gridIllumination(n: Int, lamps: Array<IntArray>, queries: Array<IntArray>): IntArray {
        val row = mutableMapOf<Int, Int>()
        val col = mutableMapOf<Int, Int>()
        val diag = mutableMapOf<Int, Int>()
        val anti = mutableMapOf<Int, Int>()
        val s = mutableSetOf<Pair<Int, Int>>()
        for (l in lamps) {
            val (x, y) = l
            if (s.contains(x to y)) continue
            s.add(x to y)
            row[x] = row.getOrDefault(x, 0) + 1
            col[y] = col.getOrDefault(y, 0) + 1
            diag[x - y] = diag.getOrDefault(x - y, 0) + 1
            anti[x + y] = anti.getOrDefault(x + y, 0) + 1
        }
        val dirs = listOf(0 to 0, 0 to 1, 0 to -1, 1 to 0, -1 to 0, 1 to 1, 1 to -1, -1 to 1, -1 to -1)
        val ans = IntArray(queries.size)
        for ((i, q) in queries.withIndex()) {
            val (x, y) = q
            if (row.getOrDefault(x,0) > 0 || col.getOrDefault(y,0) > 0 || diag.getOrDefault(x-y,0) > 0 || anti.getOrDefault(x+y,0) > 0) {
                ans[i] = 1
            }
            for ((dx, dy) in dirs) {
                val nx = x + dx
                val ny = y + dy
                if (s.contains(nx to ny)) {
                    s.remove(nx to ny)
                    row[nx] = row.getOrDefault(nx,0)-1
                    col[ny] = col.getOrDefault(ny,0)-1
                    diag[nx-ny] = diag.getOrDefault(nx-ny,0)-1
                    anti[nx+ny] = anti.getOrDefault(nx+ny,0)-1
                }
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def gridIllumination(self, n: int, lamps: list[list[int]], queries: list[list[int]]) -> list[int]:
        from collections import defaultdict
        row = defaultdict(int)
        col = defaultdict(int)
        diag = defaultdict(int)
        anti = defaultdict(int)
        s = set()
        for x, y in lamps:
            if (x, y) in s:
                continue
            s.add((x, y))
            row[x] += 1
            col[y] += 1
            diag[x - y] += 1
            anti[x + y] += 1
        ans = []
        dirs = [(0,0),(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
        for x, y in queries:
            ans.append(1 if row[x] or col[y] or diag[x-y] or anti[x+y] else 0)
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if (nx, ny) in s:
                    s.remove((nx, ny))
                    row[nx] -= 1
                    col[ny] -= 1
                    diag[nx-ny] -= 1
                    anti[nx+ny] -= 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

impl Solution {
    pub fn grid_illumination(n: i32, lamps: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        use std::collections::{HashMap, HashSet};
        let mut row = HashMap::new();
        let mut col = HashMap::new();
        let mut diag = HashMap::new();
        let mut anti = HashMap::new();
        let mut s = HashSet::new();
        for l in lamps.iter() {
            let (x, y) = (l[0], l[1]);
            if !s.insert((x, y)) { continue; }
            *row.entry(x).or_insert(0) += 1;
            *col.entry(y).or_insert(0) += 1;
            *diag.entry(x - y).or_insert(0) += 1;
            *anti.entry(x + y).or_insert(0) += 1;
        }
        let dirs = vec![(0,0),(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)];
        let mut ans = Vec::new();
        for q in queries.iter() {
            let (x, y) = (q[0], q[1]);
            if row.get(&x).unwrap_or(&0) > &0 || col.get(&y).unwrap_or(&0) > &0 || diag.get(&(x-y)).unwrap_or(&0) > &0 || anti.get(&(x+y)).unwrap_or(&0) > &0 {
                ans.push(1);
            } else {
                ans.push(0);
            }
            for (dx, dy) in &dirs {
                let nx = x + dx;
                let ny = y + dy;
                if s.remove(&(nx, ny)) {
                    *row.entry(nx).or_insert(0) -= 1;
                    *col.entry(ny).or_insert(0) -= 1;
                    *diag.entry(nx-ny).or_insert(0) -= 1;
                    *anti.entry(nx+ny).or_insert(0) -= 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    gridIllumination(n: number, lamps: number[][], queries: number[][]): number[] {
        const row = new Map<number, number>(), col = new Map<number, number>(), diag = new Map<number, number>(), anti = new Map<number, number>();
        const s = new Set<string>();
        for (const [x, y] of lamps) {
            const key = `${x},${y}`;
            if (s.has(key)) continue;
            s.add(key);
            row.set(x, (row.get(x) || 0) + 1);
            col.set(y, (col.get(y) || 0) + 1);
            diag.set(x - y, (diag.get(x - y) || 0) + 1);
            anti.set(x + y, (anti.get(x + y) || 0) + 1);
        }
        const dirs = [[0,0],[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]];
        const ans: number[] = [];
        for (const [x, y] of queries) {
            ans.push(row.get(x) || col.get(y) || diag.get(x-y) || anti.get(x+y) ? 1 : 0);
            for (const [dx, dy] of dirs) {
                const nx = x + dx, ny = y + dy, key = `${nx},${ny}`;
                if (s.has(key)) {
                    s.delete(key);
                    row.set(nx, (row.get(nx) || 0) - 1);
                    col.set(ny, (col.get(ny) || 0) - 1);
                    diag.set(nx-ny, (diag.get(nx-ny) || 0) - 1);
                    anti.set(nx+ny, (anti.get(nx+ny) || 0) - 1);
                }
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(L + Q) — Where L is the number of lamps and Q is the number of queries. Each lamp and query is processed in constant time due to hash maps and set operations.
  • 🧺 Space complexity: O(L + Q) — For hash maps and set to store lamp and illumination state.