Grid Illumination

Grid Illumination

What is this problem about?

The Grid Illumination interview question takes place on an N x N grid. You are given a list of lamps, each illuminating its own cell, its entire row, its entire column, and its two diagonals. You are also given a list of queries. For each query (r, c), you must check if the cell is illuminated. After answering a query, you must turn off the lamp at (r, c) and any lamps in the adjacent 8 cells.

Why is this asked in interviews?

Dropbox and other tech companies ask this Hash Table coding problem to test a candidate's ability to represent grid properties algebraically. Since N can be up to $10^9$, an $O(N^2)$ matrix is impossible. It evaluates if you know how to use Hash Maps to count "lines of illumination" (rows, columns, and diagonals) and how to handle dynamic updates (turning off lamps) efficiently.

Algorithmic pattern used

This problem relies on Algebraic Grid Representation and Hash Maps.

1. Coordinates: A cell (x, y) contributes to:
   • Row x
   • Column y
   • Positive diagonal: x - y
   • Negative diagonal: x + y
2. Mapping: Use four Hash Maps to count the number of lamps illuminating each specific row, column, and diagonal. Use a Set or Map to track the exact locations of active lamps.
3. Queries: A cell (r, c) is illuminated if row[r] > 0, col[c] > 0, diag1[r - c] > 0, or diag2[r + c] > 0.
4. Turning off: Iterate through the 9 cells around (r, c). If a lamp exists there in your active lamp Set, remove it and decrement the counts in your four Hash Maps.

Example explanation

N = 5, Lamp at (1, 1).

• Map updates: row[1]=1, col[1]=1, d1[0]=1 (1-1), d2[2]=1 (1+1).
• Query (2, 2): Check row[2], col[2]. Check d1[2-2=0]. d1[0] is 1, so it is illuminated!
• Turn off around (2, 2): Checks (1, 1), (1, 2) .... Finds lamp at (1, 1). Removes it. Decrements all maps.
• Next query won't be illuminated by that lamp.

Common mistakes candidates make

• Creating a 2D Array: Trying to allocate an $N imes N$ matrix, causing an immediate Memory Limit Exceeded error.
• Duplicate Lamps: The input might contain duplicate lamps at the same coordinate. If you count them twice but only remove them once, the cell might stay incorrectly illuminated.
• Diagonal Math: Confusing the formulas for the two diagonals. x - y and x + y are standard constants for cells on the same diagonal.

Interview preparation tip

Memorize the diagonal formulas for grid problems. If you need to group cells that share a diagonal going down-right, use row - col. For diagonals going down-left, use row + col. This trick appears in N-Queens, Grid Illumination, and many other matrix problems.