LeetCode 1001: Grid Illumination

Problem Restatement

We have an n x n grid.

We are given an array lamps, where each element is [row_i, col_i], meaning a lamp is placed at that cell.

A lamp illuminates its entire row, its entire column, its main diagonal, and its anti-diagonal.

We are also given an array queries, where each query is [row_j, col_j].

For each query:

1. If the queried cell is illuminated, record 1. Otherwise record 0.
2. Turn off the lamp at the queried cell and all eight neighbors (if they exist).

Return the array of answers for each query.

The official constraints include 1 <= n <= 10^9, 0 <= lamps.length <= 20000, and 0 <= queries.length <= 20000.

Input and Output

Function shape:

def gridIllumination(n: int, lamps: list[list[int]], queries: list[list[int]]) -> list[int]:
    ...

Examples

Example 1:

n = 5
lamps = [[0, 0], [4, 4]]
queries = [[1, 1], [1, 0]]

Lamp at [0, 0] illuminates row 0, col 0, diagonal 0 (row - col = 0), anti-diagonal 0 (row + col = 0).

Lamp at [4, 4] illuminates row 4, col 4, diagonal 0 (row - col = 0), anti-diagonal 8 (row + col = 8).

Query [1, 1]: diagonal 1 - 1 = 0 is illuminated by both lamps. Answer is 1. Then turn off neighbors of [1, 1] including [0, 0] and [1, 1].

Lamp at [0, 0] is turned off. Lamp at [4, 4] remains.

Query [1, 0]: row 1 has no lamp, col 0 has no lamp (lamp was off), diagonal 1 - 0 = 1 has no lamp, anti-diagonal 1 + 0 = 1 has no lamp. Answer is 0.

Answer:

[1, 0]

First Thought: Simulate Every Cell

With n up to 10^9, we cannot store the full grid.

But we can track which rows, columns, and diagonals are illuminated by counting lamps on each.

Key Insight

Track four counts:

A cell [r, c] is illuminated if any of:

row_count[r] > 0
col_count[c] > 0
diag_count[r - c] > 0
anti_count[r + c] > 0

When turning off a lamp at [r, c], decrement all four counts.

Store lamp positions in a set to quickly check if a lamp exists at a position before turning it off.

Algorithm

1. For every lamp, increment row_count[r], col_count[c], diag_count[r - c], anti_count[r + c].
2. Store all lamp positions in a set.
3. For each query [r, c]:
   • If any of the four counts is positive, record 1.
   • For each of the 9 cells (center plus 8 neighbors):
     • If the cell contains a lamp, remove it from the set and decrement all four counts.
4. Return results.

Correctness

Each lamp contributes exactly one to each of its four count arrays. A cell is illuminated if and only if some lamp covers it, which is equivalent to one of the four counts being positive.

When we turn off a lamp, we decrement its four counts. If a count reaches zero, no remaining lamp covers that row, column, or diagonal.

We process neighbors in the correct order because we check and remove lamps from the set before decrementing, preventing double-decrement.

Since lamps are deduplicated using a set, placing two lamps at the same cell counts only once.

Edge Cases

• Duplicates usually matter; store counts when a set would lose necessary multiplicity.
• Update the frequency structure in the same order the invariant assumes.
• Check empty or one-element inputs if the problem allows them.

Complexity

Let L = len(lamps) and Q = len(queries).

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import defaultdict

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

        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

        results = []
        directions = [
            (-1, -1), (-1, 0), (-1, 1),
            (0, -1),  (0, 0),  (0, 1),
            (1, -1),  (1, 0),  (1, 1),
        ]

        for r, c in queries:
            illuminated = (
                row_count[r] > 0
                or col_count[c] > 0
                or diag_count[r - c] > 0
                or anti_count[r + c] > 0
            )
            results.append(1 if illuminated else 0)

            for dr, dc in directions:
                nr, nc = r + dr, c + 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 results

Code Explanation

We deduplicate lamps and build four count maps:

if (r, c) not in lamp_set:
    lamp_set.add((r, c))
    row_count[r] += 1

For each query, we check if the cell is illuminated:

illuminated = (
    row_count[r] > 0
    or col_count[c] > 0
    or diag_count[r - c] > 0
    or anti_count[r + c] > 0
)

Then turn off all 9 neighboring cells:

for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if (nr, nc) in lamp_set:
        lamp_set.remove((nr, nc))
        row_count[nr] -= 1

Testing

def run_tests():
    s = Solution()

    assert s.gridIllumination(5, [[0, 0], [4, 4]], [[1, 1], [1, 0]]) == [1, 0]
    assert s.gridIllumination(5, [[0, 0], [0, 4]], [[0, 4], [0, 1], [1, 1]]) == [1, 1, 0]
    assert s.gridIllumination(1, [[0, 0]], [[0, 0]]) == [1]

    print("all tests passed")

run_tests()