Grid Illumination

Hard

#0955Time: 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`.1 company

Data structures

Array Hash Table

Companies

Dropbox

Prompt

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] = [row_i, col_i] indicates that the lamp at grid[row_i][col_i] 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] = [row_j, col_j]. For the j^th query, determine whether grid[row_j][col_j] is illuminated or not. After answering the j^th query, turn off the lamp at grid[row_j][col_j] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[row_j][col_j].

Return an array of integers ans, where ans[j] should be 1 if the cell in the j^th query was illuminated, or 0 if the lamp was not.

Example 1:

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.

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.

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 <= 10⁹
0 <= lamps.length <= 20000
0 <= queries.length <= 20000
lamps[i].length == 2
0 <= row_i, col_i < n
queries[j].length == 2
0 <= row_j, col_j < n

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

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.
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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {6        Set<Long> lampSet = new HashSet<>();7        for (int[] lamp : lamps) {8            long r = lamp[0];9            long c = lamp[1];10            // The key must be large enough to avoid collisions.11            // (long)r * n + c works since r, c < n.12            lampSet.add(r * n + c);13        }14 15        int[] ans = new int[queries.length];16        int[][] dirs = {{0,0}, {0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};17 18        for (int i = 0; i < queries.length; i++) {19            int r = queries[i][0];20            int c = queries[i][1];21 22            boolean isIlluminated = false;23            // Check illumination by iterating through all lamps24            for (long lampCode : lampSet) {25                long lr = lampCode / n;26                long lc = lampCode % n;27                if (lr == r || lc == c || lr - lc == (long)r - c || lr + lc == (long)r + c) {28                    isIlluminated = true;29                    break;30                }31            }32            ans[i] = isIlluminated ? 1 : 0;33 34            // Turn off lamps in the 3x3 vicinity35            for (int[] dir : dirs) {36                long nr = r + dir[0];37                long nc = c + dir[1];38                if (nr >= 0 && nr < n && nc >= 0 && nc < n) {39                    lampSet.remove(nr * n + nc);40                }41            }42        }43        return ans;44    }45}

Complexity

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`.

Trade-offs

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.

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.

Algorithm

Initialize four HashMaps: 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 HashMaps for that lamp's position.

Walkthrough

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):

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.
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.

1import java.util.HashMap;2import java.util.HashSet;3import java.util.Map;4import java.util.Set;5 6class Solution {7    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {8        Map<Integer, Integer> rowCounts = new HashMap<>();9        Map<Integer, Integer> colCounts = new HashMap<>();10        Map<Integer, Integer> diag1Counts = new HashMap<>(); // r - c11        Map<Integer, Integer> diag2Counts = new HashMap<>(); // r + c12        Set<Long> lampSet = new HashSet<>();13 14        for (int[] lamp : lamps) {15            int r = lamp[0];16            int c = lamp[1];17            long lampCode = (long)r * n + c;18            if (lampSet.contains(lampCode)) {19                continue; // Skip duplicate lamps20            }21            lampSet.add(lampCode);22            rowCounts.put(r, rowCounts.getOrDefault(r, 0) + 1);23            colCounts.put(c, colCounts.getOrDefault(c, 0) + 1);24            diag1Counts.put(r - c, diag1Counts.getOrDefault(r - c, 0) + 1);25            diag2Counts.put(r + c, diag2Counts.getOrDefault(r + c, 0) + 1);26        }27 28        int[] ans = new int[queries.length];29        int[][] dirs = {{0,0}, {0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}};30 31        for (int i = 0; i < queries.length; i++) {32            int r = queries[i][0];33            int c = queries[i][1];34 35            // Check illumination36            if (rowCounts.getOrDefault(r, 0) > 0 ||37                colCounts.getOrDefault(c, 0) > 0 ||38                diag1Counts.getOrDefault(r - c, 0) > 0 ||39                diag2Counts.getOrDefault(r + c, 0) > 0) {40                ans[i] = 1;41            } else {42                ans[i] = 0;43            }44 45            // Turn off lamps46            for (int[] dir : dirs) {47                int nr = r + dir[0];48                int nc = c + dir[1];49                long lampCode = (long)nr * n + nc;50 51                if (nr >= 0 && nr < n && nc >= 0 && nc < n && lampSet.contains(lampCode)) {52                    lampSet.remove(lampCode);53                    rowCounts.put(nr, rowCounts.get(nr) - 1);54                    colCounts.put(nc, colCounts.get(nc) - 1);55                    diag1Counts.put(nr - nc, diag1Counts.get(nr - nc) - 1);56                    diag2Counts.put(nr + c, diag2Counts.get(nr + c) - 1);57                }58            }59        }60        return ans;61    }62}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class 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 ; } }

1class 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 ; } };

1class 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem