Watch 10 video solutions for Grid Illumination, a hard level problem involving Array, Hash Table. This walkthrough by Shivam Patel has 2,430 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 < nProblem 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 | 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 |