Grid Illumination: Hash Map Line Counting

You have an n x n grid. Some cells have lamps that are initially turned on. Each lamp illuminates every cell in its row, column, and both diagonals. You are given a list of queries. For each query [row, col], first check whether that cell is currently illuminated. Then turn off the lamp at that cell (if any) and all lamps in the 8 adjacent cells. Return an array where each entry is 1 if the queried cell was illuminated, or 0 if it was not.

That is LeetCode 1001: Grid Illumination. The grid can be up to 10^9 x 10^9, so you cannot build the actual grid. The trick is to never store the grid at all. Instead, track which lines (rows, columns, diagonals) are illuminated by counting how many lamps sit on each one.

Why this problem matters

Grid Illumination combines two skills that show up constantly in interviews: hash map counting and neighbor enumeration on a grid. The counting part is the same idea behind Valid Sudoku, where you track constraints per row, column, and box. The neighbor cleanup part is the same 8-directional adjacency pattern from Number of Islands, just applied to a different purpose.

The problem also tests whether you can avoid the brute-force trap. With n up to a billion, any approach that allocates an n x n array is dead on arrival. You need to think in terms of lamp positions and line counts, not grid cells.

The key insight

A cell is illuminated if any lamp shares its row, column, main diagonal, or anti-diagonal. Instead of checking every lamp for every query, maintain four counters:

• row_count[r]: number of lamps in row r
• col_count[c]: number of lamps in column c
• diag_count[r - c]: number of lamps on the main diagonal through (r, c)
• anti_count[r + c]: number of lamps on the anti-diagonal through (r, c)

A cell at (r, c) is illuminated whenever any of its four counters is greater than zero.

You also keep a set of lamp positions so you know exactly which cells have lamps. When a query asks you to turn off lamps, you look at the queried cell and its 8 neighbors. For each one that contains a lamp, you remove it from the set and decrement the four counters.

The row - col and row + col formulas for diagonals are the same trick used in N-Queens. Every cell on the same main diagonal shares the same row - col value, and every cell on the same anti-diagonal shares the same row + col value. If you have seen N-Queens before, this part is already familiar.

The solution

from collections import defaultdict

def grid_illumination(n: int, lamps: list[list[int]], queries: list[list[int]]) -> list[int]:
    row_count = defaultdict(int)
    col_count = defaultdict(int)
    diag_count = defaultdict(int)
    anti_count = defaultdict(int)
    lamp_set = set()

    for r, c in lamps:
        if (r, c) not in lamp_set:
            lamp_set.add((r, c))
            row_count[r] += 1
            col_count[c] += 1
            diag_count[r - c] += 1
            anti_count[r + c] += 1

    result = []
    for qr, qc in queries:
        lit = (row_count[qr] > 0 or col_count[qc] > 0
               or diag_count[qr - qc] > 0 or anti_count[qr + qc] > 0)
        result.append(1 if lit else 0)

        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = qr + dr, qc + dc
                if (nr, nc) in lamp_set:
                    lamp_set.remove((nr, nc))
                    row_count[nr] -= 1
                    col_count[nc] -= 1
                    diag_count[nr - nc] -= 1
                    anti_count[nr + nc] -= 1

    return result

Let's walk through each part.

Initialization. We create four defaultdict(int) counters and a set for lamp positions. For each lamp, we add it to the set and increment the four relevant counters. We check for duplicate lamp positions in the input and skip them.

Processing queries. For each query (qr, qc), we check whether any of the four counters for that cell is positive. If so, the cell is illuminated and we append 1.

Turning off neighbors. We loop through all 9 cells in the 3x3 neighborhood around (qr, qc) (the cell itself plus its 8 neighbors). For each cell that contains a lamp, we remove it from the set and decrement its four counters.

The nested loop for dr in (-1, 0, 1): for dc in (-1, 0, 1) generates all 9 offsets. This is a compact way to enumerate the queried cell and its 8 neighbors without writing 9 separate blocks.

Visual walkthrough

Let's trace through a 5x5 grid with lamps at (0,0) and (2,2), processing queries [(0,0), (1,1), (2,2)].

The key moment is the cleanup after Query 2. The lamp at (2,2) falls within the 3x3 neighborhood of (1,1), so it gets turned off. By the time Query 3 checks (2,2), no lamps remain and the answer is 0. This shows why tracking lamp positions in a set is essential: you need to quickly find and remove lamps during the neighbor sweep.

Complexity analysis

Time: O(L) to initialize the counters, where L is the number of lamps. O(Q) to process all queries, since each query checks 4 counters (O(1)) and sweeps at most 9 neighbors (O(1) each). Total: O(L + Q).

Space: O(L) for the lamp set and the four counter maps. The counters can have at most L entries each.

Edge cases

• Duplicate lamps in the input: the problem says lamps may repeat. Skip duplicates by checking the lamp set before incrementing counters.
• Query on a cell with no lamp: the cell might still be illuminated by a distant lamp in the same row, column, or diagonal. The counters handle this correctly.
• All lamps turned off early: later queries should all return 0. Once a lamp is removed from the set, its counters are decremented and it will not be removed again.
• Lamp at the grid boundary: the 3x3 neighbor sweep naturally handles out-of-bounds neighbors because they will not be in the lamp set. No explicit bounds checking is needed.
• Very large n: since we never allocate an n x n structure, the solution works for n up to 10^9.

The building blocks

This problem is built on two reusable pieces that CodeBricks drills independently.

1. Hash map line counting

The pattern of using counters to track how many items share a property, rather than storing which cells are affected:

row_count = defaultdict(int)
col_count = defaultdict(int)
diag_count = defaultdict(int)
anti_count = defaultdict(int)

for r, c in items:
    row_count[r] += 1
    col_count[c] += 1
    diag_count[r - c] += 1
    anti_count[r + c] += 1

This "count by line" approach converts a 2D spatial query ("is this cell illuminated?") into four O(1) lookups. You will see the same idea in Valid Sudoku (tracking digits per row, column, and box), N-Queens (tracking occupied diagonals), and any problem where you need to check whether a row, column, or diagonal is "active." The key is recognizing that you do not need to store the grid itself. You only need to count how many items contribute to each line.

2. 3x3 neighbor enumeration

The pattern of iterating over a cell and its 8 neighbors using a nested loop over offsets:

for dr in (-1, 0, 1):
    for dc in (-1, 0, 1):
        nr, nc = r + dr, c + dc
        process(nr, nc)

This is the 8-directional version of the 4-directional neighbor pattern from grid BFS/DFS problems. You will use it in Game of Life (counting live neighbors), mine sweeper logic, and any grid problem that considers diagonal adjacency. The nested loop is more compact than listing all 9 cases explicitly, and it naturally includes the center cell (r, c) itself (when dr = 0 and dc = 0).

From understanding to recall

You see how the four hash maps replace the grid, how the diagonal formulas work, and how the neighbor sweep cleans up lamps. But can you write the initialization loop, the query check, and the neighbor cleanup from memory in an interview?

That is the gap between understanding and recall. The solution has specific details that slip under pressure: remembering to check for duplicate lamps, using defaultdict(int) so missing keys default to zero, decrementing all four counters when removing a lamp. These are not hard concepts. They are things you forget when you are nervous.

Spaced repetition closes that gap. You practice writing the counter initialization, the four-way illumination check, and the 3x3 neighbor sweep from scratch at increasing intervals. After a few reps, the pattern is automatic. You see "grid illumination" or "count by row/column/diagonal" and the code flows out.

The hash-map line counting and neighbor enumeration patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the details stick.

Related posts

• N-Queens - Uses the same row - col and row + col diagonal trick, but with sets instead of counters. If you master the diagonal formulas in one problem, they transfer directly to the other.
• Valid Sudoku - Another hash-set-per-line problem. Instead of counting lamps per row/column/diagonal, you track seen digits per row/column/box. Same structural pattern, different domain.
• Number of Islands - Grid traversal with neighbor enumeration. Grid Illumination uses the 8-directional version of the same neighbor pattern.

CodeBricks breaks Grid Illumination into its hash-map line counting and neighbor enumeration building blocks, then drills them independently with spaced repetition. You type the counter setup, the illumination check, and the lamp cleanup from scratch until the pattern is automatic. When a grid counting problem shows up in your interview, you do not think about it. You just write it.