Grid Illumination - Solution & Explanation
Problem Statement
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:
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 <= 1090 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == 20 <= rowi, coli < nqueries[j].length == 20 <= rowj, colj < n
Approach Overview
Problem Overview: You are given an n x n grid with lamps placed at certain coordinates. A lamp illuminates its entire row, column, and both diagonals. For each query cell, determine whether it is illuminated. After answering the query, turn off any lamp located in the queried cell or its 8 neighboring cells.
Approach 1: Hash Maps for Row, Column, and Diagonal Tracking (O(L + Q) time, O(L) space)
The key insight is that you never need to simulate the entire grid. Illumination depends only on whether at least one lamp exists in the same row, column, or diagonal. Maintain four hash maps: rowCount, colCount, diagCount (r - c), and antiDiagCount (r + c). Also keep a hash set of active lamp coordinates to avoid duplicates. When processing a query (r, c), check these maps with constant-time lookups to determine if the cell is illuminated. After answering, iterate over the 3x3 neighborhood around the query and deactivate any lamps found, updating the counters. This approach relies heavily on hash table lookups and works efficiently even when n is up to 1e9 because only lamp positions are stored.
Approach 2: Sparse Representation for Efficient Processing (O(L + Q) time, O(L) space)
Instead of thinking about a dense grid, treat the board as a sparse system where only lamp coordinates matter. Store lamps in a hash-based structure such as unordered_set or a coordinate-encoded map. Maintain lightweight counters for rows, columns, and diagonals exactly like the first approach, but emphasize the sparse model: operations only touch positions that actually contain lamps. Each query checks illumination via counter lookups, then scans the nine surrounding cells and removes lamps if present. This representation keeps memory proportional to the number of lamps rather than n². It fits well in languages like C++ and JavaScript where encoded coordinates allow constant-time insert, delete, and membership checks. The technique is common when working with large array-based grids where most cells are empty.
Recommended for interviews: Interviewers expect the hash map counting strategy. A brute-force grid simulation would require scanning rows and diagonals per query and quickly becomes too slow. Demonstrating the counter-based approach shows that you recognize illumination depends only on row/column/diagonal presence and that you can reduce the grid to constant-time hash lookups. Handling lamp removal in the 3x3 neighborhood correctly is usually the tricky edge case that interviewers watch for.
Approach 1: Use Hash Maps for Row, Column, and Diagonal Tracking
This approach uses hash maps to keep track of the number of lamps currently illuminating each row, column, and diagonal.
When a lamp is turned on, increment the corresponding counts in the hash maps. When handling a query, simply check the counts to determine if a position is illuminated.
After each query, turn off the queried lamp and its adjacent lamps, and update the counts accordingly.
This Python code makes use of Python's defaultdict to keep track of how many lamps are illuminating each row, column, and both diagonals.
For each query, we check the counts to decide if the queried grid cell is illuminated and use a helper function to turn off the lamp and its adjacent lamps, updating the counts accordingly.
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 on average due to hashmap operations.
Space Complexity: O(L) for storing lamps in hashmaps.
Approach 2: Use Sparse Representation for Efficient Processing
In this approach, represented grid parts are sparse to efficiently store and update illuminated sections, and maintain light sources in compact data structures for faster query handling and updates.
Lamps are stored in a set of active lamps, and for each query, it is checked if there are active lights in any contributing row, column, or diagonal. After checking, related lamps are turned off.
This C++ solution implements efficient sparse representation of illuminated grid sections.
For each query, the grid cell's illumination is determined using hash maps to rapidly access row, column, and diagonals counts. Lamp positions are stored in a set for uniqueness and allow easy toggling of checked lamps and their neighbors.
Code
C++
JavaScript
Complexity
Time Complexity: O(L + Q), because each lamp and query is processed in constant time.
Space Complexity: O(L), due to the requirement to store individual lamp positions and relevant lighting information.
Approach 3: Hash Table
Suppose the coordinates of a lamp are (x, y). Then, the row value is x, the column value is y, the main diagonal value is x-y, and the anti-diagonal value is x+y. Once we determine the unique value identifier for a line, we can use a hash table to record the number of lamps on that line.
We traverse the array lamps, and for each lamp, we increment the count of lamps in its row, column, main diagonal, and anti-diagonal by 1.
Note that when processing lamps, we need to remove duplicates because we treat repeated lamps as the same lamp.
Next, we traverse the queries and check if there are lamps in the row, column, main diagonal, or anti-diagonal of the current query point. If there are, we set the value to 1, indicating that the point is illuminated during the query. Then, we perform the turn-off operation by checking the eight neighboring points of the query point and the point itself to see if there are any lamps. If there are, we decrement the count of lamps in the corresponding row, column, main diagonal, and anti-diagonal by 1 and remove the lamp from the grid.
Finally, we return the answer array.
The time complexity is O(m + q), where m and q are the lengths of the arrays lamps and queries, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Use Hash Maps for Row, Column, and Diagonal Tracking | 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 on average due to hashmap operations. Space Complexity: O(L) for storing lamps in hashmaps. |
| Use Sparse Representation for Efficient Processing | Time Complexity: O(L + Q), because each lamp and query is processed in constant time. Space Complexity: O(L), due to the requirement to store individual lamp positions and relevant lighting information. |
| Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Maps for Row, Column, and Diagonal Tracking | O(L + Q) | O(L) | General case and interview settings where fast illumination checks are required |
| Sparse Representation with Coordinate Hashing | O(L + Q) | O(L) | Large grids where storing the full grid is impossible and only lamp positions matter |
Video Solution
Leetcode 1001(Hard) Grid Illumination: Simple C++ Solution • Shivam Patel • 2,508 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Grid Illumination easy or hard?
Grid Illumination Python/Java solution
How to solve Grid Illumination in O(n)?
What is the best approach for Grid Illumination?
Is Grid Illumination asked at Google/Amazon/Meta?
What data structure is used in Grid Illumination?
What is the time complexity of Grid Illumination?
Ready to solve this problem?
Practice Grid Illumination with our built-in code editor and test cases.
Practice on FleetCode