# Grid Illumination
**Difficulty:** HARD
[External](https://leetcode.com/problems/grid-illumination)
Canonical: https://scaleengineer.com/dsa/problems/grid-illumination
**Data structures:** Array, Hash Table
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox)
---
## 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:**

![](https://assets.glich.co/dsa/grid-illumination/image0.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.glich.co/dsa/grid-illumination/image1.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.glich.co/dsa/grid-illumination/image2.jpg)

**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 <= 109`
* `0 <= lamps.length <= 20000`
* `0 <= queries.length <= 20000`
* `lamps[i].length == 2`
* `0 <= rowi, coli < n`
* `queries[j].length == 2`
* `0 <= rowj, colj < n`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. It maintains a set of all currently active lamps. For each query, it checks for illumination by iterating through every single active lamp to see if it lights up the query cell. After the check, it finds and removes any lamps in the 3x3 vicinity of the query cell.
**Time:** O(L + Q * L), where L is the number of lamps and Q is the number of queries. Initialization takes O(L). Each of the Q queries requires iterating through up to L lamps for the illumination check, leading to a total time of O(Q * L). · **Space:** O(L), where L is the number of lamps. The space is used to store the coordinates of the active lamps in a `HashSet`.
**Pros:** Simple to understand and implement as it directly models the problem statement.; Uses a reasonable amount of space, proportional only to the number of lamps.
**Cons:** The time complexity is very high due to the nested loop structure (iterating through all lamps for each query), making it too slow for the given constraints.; It will likely result in a 'Time Limit Exceeded' error on platforms like LeetCode.
### Explanation
In this brute-force method, we use a `HashSet` to keep track of the coordinates of all lamps that are currently on. To efficiently store and look up 2D coordinates `(r, c)` in the set, we encode them into a single `long` value. A common way to do this is by using the formula `key = (long)r * n + c`, where `n` is the grid size. This guarantees a unique key for each cell.

First, we initialize the simulation by populating the `HashSet` with all the lamps from the input `lamps` array.

Then, for each query `(qr, qc)`, we perform two main steps:
1.  **Illumination Check:** We determine if the cell `(qr, qc)` is illuminated. This is done by iterating through every lamp currently in our `HashSet`. For each active lamp `(lr, lc)`, we check if it shares a row, column, or diagonal with the query cell. If we find even one such lamp, we know the cell is illuminated, record a `1` as the answer for this query, and we can stop searching.
2.  **Turn Off Lamps:** After answering the query, we must turn off lamps. We examine the 3x3 square of cells centered at the query location `(qr, qc)`. For each of these nine cells, we check if it corresponds to an active lamp by looking up its encoded coordinate in our `HashSet`. If a lamp exists at that location, we remove it from the set.

This process is repeated for all queries, and the collected answers are returned.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Set<Long> lampSet = new HashSet<>();
        for (int[] lamp : lamps) {
            long r = lamp[0];
            long c = lamp[1];
            // The key must be large enough to avoid collisions.
            // (long)r * n + c works since r, c < n.
            lampSet.add(r * n + c);
        }

        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 r = queries[i][0];
            int c = queries[i][1];

            boolean isIlluminated = false;
            // Check illumination by iterating through all lamps
            for (long lampCode : lampSet) {
                long lr = lampCode / n;
                long lc = lampCode % n;
                if (lr == r || lc == c || lr - lc == (long)r - c || lr + lc == (long)r + c) {
                    isIlluminated = true;
                    break;
                }
            }
            ans[i] = isIlluminated ? 1 : 0;

            // Turn off lamps in the 3x3 vicinity
            for (int[] dir : dirs) {
                long nr = r + dir[0];
                long nc = c + dir[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
                    lampSet.remove(nr * n + nc);
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Create a `HashSet<Long>` called `lampSet` to store active lamp coordinates, encoded as a single `long` value (e.g., `(long)r * n + c`) for uniqueness and efficiency.
- Populate `lampSet` by iterating through the input `lamps` array.
- For each query `(r, c)` in the `queries` array:
  - Initialize a flag `isIlluminated` to `false`.
  - Iterate through every single lamp coordinate stored in `lampSet`.
  - For each lamp at `(lr, lc)`, check if it illuminates the query cell `(r, c)`. A lamp illuminates the cell if `lr == r` (same row), `lc == c` (same column), `lr - lc == r - c` (same main diagonal), or `lr + lc == r + c` (same anti-diagonal).
  - If an illuminating lamp is found, set `isIlluminated` to `true` and break the inner loop.
  - Record the result (1 for `true`, 0 for `false`).
  - After checking illumination, iterate through the 3x3 grid of cells centered at `(r, c)`. For each neighbor cell `(nr, nc)` (including the center), check if its encoded coordinate exists in `lampSet`. If it does, remove it to simulate turning the lamp off.
- Return the array of collected results.

## Optimized Approach with Hash Maps
This approach avoids the costly iteration over all lamps for each query. Instead of checking lamps one by one, we pre-process the lamp locations to count how many lamps illuminate each row, column, and diagonal. This allows for an O(1) illumination check. We use four hash maps to maintain these counts, along with a hash set to track the exact lamp locations.
**Time:** O(L + Q), where L is the number of lamps and Q is the number of queries. Initialization takes O(L) to process all lamps. Each of the Q queries takes O(1) average time, as it involves a constant number of hash map/set operations (one check for illumination and 9 checks/updates for turning off lamps). · **Space:** O(L), where L is the number of unique lamps. The `HashSet` and the four `HashMap`s will each store at most L entries. In total, the space is proportional to L.
**Pros:** Highly efficient, with an average time complexity that is linear in the number of lamps and queries.; Scales well for the given constraints, easily passing large test cases.; The core logic for checking illumination is an elegant O(1) operation.
**Cons:** Uses more memory than the brute-force approach due to the four hash maps in addition to the lamp set.; The implementation is slightly more complex due to the need to manage counts across multiple data structures.
### Explanation
The key insight for an efficient solution is that a cell `(r, c)` is illuminated if and only if there's at least one active lamp on its row `r`, its column `c`, its main diagonal (where all cells have the same `r-c` value), or its anti-diagonal (where all cells have the same `r+c` value).

This allows us to abstract away from individual lamps and instead focus on which lines are illuminated. We use four `HashMap<Integer, Integer>`s to maintain these counts:
- `rowCounts`: Maps a row index to the number of lamps in that row.
- `colCounts`: Maps a column index to the number of lamps in that column.
- `diag1Counts`: Maps a main diagonal identifier (`r-c`) to the number of lamps on it.
- `diag2Counts`: Maps an anti-diagonal identifier (`r+c`) to the number of lamps on it.

We also still need a `HashSet<Long>` to keep track of the exact locations of active lamps, which is necessary for turning them off correctly.

**Initialization:** We iterate through the `lamps` array. For each unique lamp at `(r, c)`, we add its encoded coordinate to the `HashSet` and increment the counts in all four `HashMaps`.

**Query Processing:** For each query `(r, c)`:
1.  **Illumination Check:** We simply check if `rowCounts.get(r) > 0` or `colCounts.get(c) > 0` or `diag1Counts.get(r-c) > 0` or `diag2Counts.get(r+c) > 0`. This is an `O(1)` operation on average.
2.  **Turn Off Lamps:** We iterate through the 9 cells in the 3x3 square centered at `(r, c)`. For each cell `(nr, nc)` in this square, we check if it's an active lamp using our `HashSet`. If it is, we "turn it off" by removing it from the `HashSet` and decrementing the corresponding counts in all four `HashMaps`.

This approach dramatically improves the time complexity by making the illumination check, the most frequent operation, extremely fast.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Map<Integer, Integer> rowCounts = new HashMap<>();
        Map<Integer, Integer> colCounts = new HashMap<>();
        Map<Integer, Integer> diag1Counts = new HashMap<>(); // r - c
        Map<Integer, Integer> diag2Counts = new HashMap<>(); // r + c
        Set<Long> lampSet = new HashSet<>();

        for (int[] lamp : lamps) {
            int r = lamp[0];
            int c = lamp[1];
            long lampCode = (long)r * n + c;
            if (lampSet.contains(lampCode)) {
                continue; // Skip duplicate lamps
            }
            lampSet.add(lampCode);
            rowCounts.put(r, rowCounts.getOrDefault(r, 0) + 1);
            colCounts.put(c, colCounts.getOrDefault(c, 0) + 1);
            diag1Counts.put(r - c, diag1Counts.getOrDefault(r - c, 0) + 1);
            diag2Counts.put(r + c, diag2Counts.getOrDefault(r + c, 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 r = queries[i][0];
            int c = queries[i][1];

            // Check illumination
            if (rowCounts.getOrDefault(r, 0) > 0 ||
                colCounts.getOrDefault(c, 0) > 0 ||
                diag1Counts.getOrDefault(r - c, 0) > 0 ||
                diag2Counts.getOrDefault(r + c, 0) > 0) {
                ans[i] = 1;
            } else {
                ans[i] = 0;
            }

            // Turn off lamps
            for (int[] dir : dirs) {
                int nr = r + dir[0];
                int nc = c + dir[1];
                long lampCode = (long)nr * n + nc;

                if (nr >= 0 && nr < n && nc >= 0 && nc < n && lampSet.contains(lampCode)) {
                    lampSet.remove(lampCode);
                    rowCounts.put(nr, rowCounts.get(nr) - 1);
                    colCounts.put(nc, colCounts.get(nc) - 1);
                    diag1Counts.put(nr - nc, diag1Counts.get(nr - nc) - 1);
                    diag2Counts.put(nr + c, diag2Counts.get(nr + c) - 1);
                }
            }
        }
        return ans;
    }
}
```
### Algorithm
- Initialize four `HashMap`s: `rowCounts`, `colCounts`, `diag1Counts`, and `diag2Counts` to store the number of lamps on each line.
- Initialize a `HashSet<Long>` called `lampSet` to store the coordinates of unique, active lamps.
- Iterate through the input `lamps` array. For each unique lamp `(r, c)`:
  - Add its encoded coordinate `(long)r * n + c` to `lampSet`.
  - Increment the count for row `r` in `rowCounts`.
  - Increment the count for column `c` in `colCounts`.
  - Increment the count for the main diagonal `r-c` in `diag1Counts`.
  - Increment the count for the anti-diagonal `r+c` in `diag2Counts`.
- For each query `(r, c)`:
  - Check if the cell is illuminated by checking if the count for its corresponding row, column, or either diagonal in the maps is greater than 0. If any count is positive, the cell is illuminated.
  - Store the result (1 or 0).
  - Iterate through the 3x3 grid around `(r, c)`. If a cell `(nr, nc)` contains an active lamp (check `lampSet`), remove it from the set and decrement the counts in all four `HashMap`s for that lamp's position.

# Solutions
### Java

```java
class Solution { private int n ; public int [] gridIllumination ( int n , int [][] lamps , int [][] queries ) { this . n = n ; Set < Long > s = new HashSet <>(); Map < Integer , Integer > row = new HashMap <>(); Map < Integer , Integer > col = new HashMap <>(); Map < Integer , Integer > diag1 = new HashMap <>(); Map < Integer , Integer > diag2 = new HashMap <>(); for ( var lamp : lamps ) { int i = lamp [ 0 ], j = lamp [ 1 ]; if ( s . add ( f ( i , j ))) { merge ( row , i , 1 ); merge ( col , j , 1 ); merge ( diag1 , i - j , 1 ); merge ( diag2 , i + j , 1 ); } } int m = queries . length ; int [] ans = new int [ m ]; for ( int k = 0 ; k < m ; ++ k ) { int i = queries [ k ][ 0 ], j = queries [ k ][ 1 ]; if ( exist ( row , i ) || exist ( col , j ) || exist ( diag1 , i - j ) || exist ( diag2 , i + j )) { 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 . contains ( f ( x , y ))) { continue ; } s . remove ( f ( x , y )); merge ( row , x , - 1 ); merge ( col , y , - 1 ); merge ( diag1 , x - y , - 1 ); merge ( diag2 , x + y , - 1 ); } } } return ans ; } private void merge ( Map < Integer , Integer > cnt , int x , int d ) { if ( cnt . merge ( x , d , Integer: : sum ) == 0 ) { cnt . remove ( x ); } } private boolean exist ( Map < Integer , Integer > cnt , int x ) { return cnt . getOrDefault ( x , 0 ) > 0 ; } private long f ( long i , long j ) { return i * n + j ; } }
```

### CPP

```cpp
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 ; } };
```

### Python

```python
class Solution : def gridIllumination ( self , n : int , lamps : List [ List [ int ]], queries : List [ List [ int ]] ) -> List [ int ]: s = {( i , j ) for i , j in lamps } row , col , diag1 , diag2 = Counter (), Counter (), Counter (), Counter () for i , j in s : row [ i ] += 1 col [ j ] += 1 diag1 [ i - j ] += 1 diag2 [ i + j ] += 1 ans = [ 0 ] * len ( queries ) for k , ( i , j ) in enumerate ( queries ): if row [ i ] or col [ j ] or diag1 [ i - j ] or diag2 [ i + j ]: ans [ k ] = 1 for x in range ( i - 1 , i + 2 ): for y in range ( j - 1 , j + 2 ): if ( x , y ) in s : s . remove (( x , y )) row [ x ] -= 1 col [ y ] -= 1 diag1 [ x - y ] -= 1 diag2 [ x + y ] -= 1 return ans
```