LeetCode 1001 - Grid Illumination

LeetCode Problem 1001

Difficulty: 🔴 Hard
Topics: Array, Hash Table

Solution

Problem Understanding

This problem models a very large chessboard-like grid where certain cells contain active lamps. A lamp illuminates four directions simultaneously:

• Its entire row
• Its entire column
• Its main diagonal, identified by row - col
• Its anti-diagonal, identified by row + col

For every query, we must determine whether the queried cell is illuminated by at least one currently active lamp. After answering the query, we must turn off any lamp located in the queried cell or one of its eight neighboring cells.

The important detail is that illumination is global along rows, columns, and diagonals. A lamp at (r, c) illuminates all cells:

• (r, any)
• (any, c)
• (r + k, c + k)
• (r + k, c - k)

for all valid positions.

The input consists of:

• n, the grid size
• lamps, a list of initially active lamp positions
• queries, a sequence of cells to check

The output is an array where:

• 1 means the queried cell is illuminated
• 0 means it is not illuminated

The constraints are the most important part of this problem:

• n can be as large as 10^9
• Up to 20,000 lamps
• Up to 20,000 queries

The huge value of n tells us immediately that constructing the grid explicitly is impossible. A 10^9 x 10^9 grid cannot be stored or iterated over. This means the solution must depend only on the positions of active lamps, not on the grid size itself.

Several edge cases are important:

• Duplicate lamp positions may appear in the input
• Turning off lamps must not decrement counters multiple times for duplicates
• Queries may repeatedly target the same area
• Lamps removed by earlier queries must stay removed
• A queried cell may itself contain a lamp
• The surrounding 3x3 removal area may partially go outside the grid

A correct solution must efficiently support:

1. Fast illumination checks
2. Fast lamp removals
3. Duplicate-safe bookkeeping

Approaches

Brute Force Approach

A straightforward solution would explicitly simulate the illumination process.

For every query:

1. Check every active lamp
2. Determine whether any lamp shares:

• the same row
• the same column
• the same diagonal

3. If any lamp matches, the cell is illuminated
4. Then scan all active lamps again and remove lamps in the 3x3 neighborhood

This approach is correct because it directly follows the problem definition. Every query compares against every active lamp, so no illuminating lamp can be missed.

However, this is far too slow.

If there are L lamps and Q queries:

• Each illumination check costs O(L)
• Each removal phase also costs O(L)

Overall complexity becomes O(Q * L).

With both potentially equal to 20,000, this can reach 400 million operations, which is too large.

Optimal Approach

The key observation is that we do not need to know exactly which cells are illuminated. We only need to know whether at least one active lamp affects a queried cell.

Instead of simulating illumination across the grid, we maintain counts:

• How many active lamps exist in each row
• How many active lamps exist in each column
• How many active lamps exist in each main diagonal
• How many active lamps exist in each anti-diagonal

Then a cell (r, c) is illuminated if any of these counts is positive:

• row_count[r] > 0
• col_count[c] > 0
• diag_count[r - c] > 0
• anti_diag_count[r + c] > 0

This transforms illumination checks into constant-time hash map lookups.

We also maintain a hash set of active lamp positions so that removals can be performed efficiently and duplicates are handled safely.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(Q * L)	O(L)	Checks every lamp for every query
Optimal	O(L + Q)	O(L)	Uses hash maps and hash sets for constant-time checks

Algorithm Walkthrough

1. Create four hash maps to count active lamps by:

• row
• column
• main diagonal (row - col)
• anti-diagonal (row + col)

These structures let us determine illumination in constant time. 2. Create a hash set containing all unique active lamp positions.

This is critical because the input may contain duplicate lamps. We only want to count each active lamp once. 3. Initialize the counting maps using the unique lamp positions.

For each lamp (r, c):

• increment rows[r]
• increment cols[c]
• increment diag[r - c]
• increment anti[r + c]

4. Process each query (r, c).

A cell is illuminated if any of these conditions hold:

• rows[r] > 0
• cols[c] > 0
• diag[r - c] > 0
• anti[r + c] > 0

If any are true, append 1 to the answer array. Otherwise append 0. 5. After answering the query, examine the 3x3 region centered at (r, c).

This includes:

• the queried cell itself
• all eight neighboring cells

6. For every candidate cell (nr, nc) in that region:

• verify it lies inside the grid
• check whether it exists in the active lamp set

If the lamp exists:

• remove it from the set
• decrement all four counters associated with it

7. Continue until all queries are processed.

Why it works

The algorithm maintains an invariant:

• The hash maps always reflect the exact number of currently active lamps affecting each row, column, and diagonal.

A queried cell is illuminated if and only if at least one active lamp contributes to one of those four structures. Since every lamp insertion and removal updates all relevant counters consistently, the illumination checks are always correct.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def gridIllumination(
        self,
        n: int,
        lamps: List[List[int]],
        queries: List[List[int]]
    ) -> List[int]:

        rows = defaultdict(int)
        cols = defaultdict(int)
        diag = defaultdict(int)
        anti_diag = defaultdict(int)

        active_lamps = set()

        # Add unique lamps only
        for r, c in lamps:
            if (r, c) in active_lamps:
                continue

            active_lamps.add((r, c))

            rows[r] += 1
            cols[c] += 1
            diag[r - c] += 1
            anti_diag[r + c] += 1

        result = []

        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 = (
                rows[r] > 0 or
                cols[c] > 0 or
                diag[r - c] > 0 or
                anti_diag[r + c] > 0
            )

            result.append(1 if illuminated else 0)

            # Turn off lamps in surrounding 3x3 area
            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if not (0 <= nr < n and 0 <= nc < n):
                    continue

                if (nr, nc) not in active_lamps:
                    continue

                active_lamps.remove((nr, nc))

                rows[nr] -= 1
                cols[nc] -= 1
                diag[nr - nc] -= 1
                anti_diag[nr + nc] -= 1

        return result

The implementation begins by constructing four frequency maps that track how many active lamps illuminate each row, column, and diagonal.

The active_lamps set prevents duplicate lamps from being counted multiple times. Since the input may contain repeated lamp coordinates, this step is essential for correctness.

During each query, illumination is checked using only four hash lookups. This avoids scanning all lamps.

The directions array represents the nine cells in the 3x3 neighborhood. For each nearby cell, we first verify bounds, then check whether a lamp exists. If it does, we remove it and decrement all associated counters.

Every operation on the hash maps and set is expected O(1), which keeps the entire algorithm efficient.

Go Solution

package main

func gridIllumination(n int, lamps [][]int, queries [][]int) []int {
	rows := make(map[int]int)
	cols := make(map[int]int)
	diag := make(map[int]int)
	antiDiag := make(map[int]int)

	active := make(map[[2]int]bool)

	// Add unique lamps only
	for _, lamp := range lamps {
		r, c := lamp[0], lamp[1]

		key := [2]int{r, c}

		if active[key] {
			continue
		}

		active[key] = true

		rows[r]++
		cols[c]++
		diag[r-c]++
		antiDiag[r+c]++
	}

	directions := [][2]int{
		{-1, -1}, {-1, 0}, {-1, 1},
		{0, -1}, {0, 0}, {0, 1},
		{1, -1}, {1, 0}, {1, 1},
	}

	result := make([]int, 0, len(queries))

	for _, query := range queries {
		r, c := query[0], query[1]

		illuminated := rows[r] > 0 ||
			cols[c] > 0 ||
			diag[r-c] > 0 ||
			antiDiag[r+c] > 0

		if illuminated {
			result = append(result, 1)
		} else {
			result = append(result, 0)
		}

		// Turn off lamps in surrounding 3x3 area
		for _, d := range directions {
			nr := r + d[0]
			nc := c + d[1]

			if nr < 0 || nr >= n || nc < 0 || nc >= n {
				continue
			}

			key := [2]int{nr, nc}

			if !active[key] {
				continue
			}

			delete(active, key)

			rows[nr]--
			cols[nc]--
			diag[nr-nc]--
			antiDiag[nr+nc]--
		}
	}

	return result
}

The Go version follows the same algorithmic structure as the Python implementation.

Go does not have a built-in tuple type, so lamp coordinates are represented using a fixed-size array [2]int, which can be used as a map key.

Maps in Go return the zero value for missing keys automatically, which simplifies illumination checks because nonexistent counts behave as 0.

The implementation uses delete to remove active lamps from the hash set representation.

Worked Examples

Example 1

Input:

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

Initial State

Structure	Value
Active Lamps	{(0,0), (4,4)}
rows	{0:1, 4:1}
cols	{0:1, 4:1}
diag	{0:2}
anti_diag	{0:1, 8:1}

Query 1: (1,1)

Check illumination:

Check	Value
rows[1]	0
cols[1]	0
diag[0]	2
anti_diag[2]	0

Since diag[0] > 0, the cell is illuminated.

Answer becomes:

[1]

Now remove lamps in the surrounding 3x3 region.

Cells checked:

(0,0) (0,1) (0,2)
(1,0) (1,1) (1,2)
(2,0) (2,1) (2,2)

Lamp (0,0) is removed.

Updated structures:

Structure	Value
Active Lamps	{(4,4)}
rows	{0:0, 4:1}
cols	{0:0, 4:1}
diag	{0:1}
anti_diag	{0:0, 8:1}

Query 2: (1,0)

Check illumination:

Check	Value
rows[1]	0
cols[0]	0
diag[1]	0
anti_diag[1]	0

No illumination exists.

Answer becomes:

[1,0]

Example 2

Input:

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

After the first query, only (0,0) is removed.

Lamp (4,4) still illuminates diagonal 0.

The second query (1,1) remains illuminated because:

1 - 1 = 0

which matches the active lamp diagonal.

Final answer:

[1,1]

Example 3

Input:

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

Initial State

Structure	Value
Active Lamps	{(0,0), (0,4)}
rows	{0:2}
cols	{0:1, 4:1}

Query 1: (0,4)

The cell itself contains a lamp, so it is illuminated.

After answering, remove lamps in the surrounding area.

Lamp (0,4) is removed.

Remaining active lamps:

{(0,0)}

Query 2: (0,1)

Row 0 still contains lamp (0,0), so the cell is illuminated.

Answer so far:

[1,1]

The 3x3 removal area now includes (0,0), so that lamp is removed.

No active lamps remain.

Query 3: (1,4)

No rows, columns, or diagonals contain active lamps.

Answer:

[1,1,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(L + Q)	Each lamp and query is processed in constant expected time
Space	O(L)	Hash maps and set store active lamps and counts

The initialization phase processes each unique lamp once.

Each query performs:

• Four constant-time illumination checks
• At most nine lamp removal attempts

Since the surrounding region is always bounded by nine cells, the per-query work remains constant.

Therefore the total complexity is linear in the number of lamps and queries.

Test Cases

from typing import List

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        from collections import defaultdict

        rows = defaultdict(int)
        cols = defaultdict(int)
        diag = defaultdict(int)
        anti_diag = defaultdict(int)

        active = set()

        for r, c in lamps:
            if (r, c) in active:
                continue

            active.add((r, c))

            rows[r] += 1
            cols[c] += 1
            diag[r - c] += 1
            anti_diag[r + c] += 1

        result = []

        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 = (
                rows[r] > 0 or
                cols[c] > 0 or
                diag[r - c] > 0 or
                anti_diag[r + c] > 0
            )

            result.append(1 if illuminated else 0)

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if 0 <= nr < n and 0 <= nc < n and (nr, nc) in active:
                    active.remove((nr, nc))

                    rows[nr] -= 1
                    cols[nc] -= 1
                    diag[nr - nc] -= 1
                    anti_diag[nr + nc] -= 1

        return result

sol = Solution()

assert sol.gridIllumination(
    5,
    [[0,0],[4,4]],
    [[1,1],[1,0]]
) == [1,0]  # Basic example from prompt

assert sol.gridIllumination(
    5,
    [[0,0],[4,4]],
    [[1,1],[1,1]]
) == [1,1]  # Repeated query after partial lamp removal

assert sol.gridIllumination(
    5,
    [[0,0],[0,4]],
    [[0,4],[0,1],[1,4]]
) == [1,1,0]  # Lamps removed progressively

assert sol.gridIllumination(
    1,
    [[0,0]],
    [[0,0],[0,0]]
) == [1,0]  # Smallest possible grid

assert sol.gridIllumination(
    10,
    [],
    [[5,5]]
) == [0]  # No lamps at all

assert sol.gridIllumination(
    10,
    [[2,2],[2,2],[2,2]],
    [[2,3]]
) == [1]  # Duplicate lamps counted once

assert sol.gridIllumination(
    10,
    [[5,5]],
    [[4,4],[5,5]]
) == [1,0]  # Query removes neighboring lamp

assert sol.gridIllumination(
    1000000000,
    [[999999999,999999999]],
    [[0,0],[999999999,0]]
) == [1,1]  # Very large grid size

assert sol.gridIllumination(
    5,
    [[1,3]],
    [[0,2],[2,4]]
) == [1,0]  # Diagonal illumination only

assert sol.gridIllumination(
    5,
    [[2,1]],
    [[0,1],[2,2]]
) == [1,0]  # Column illumination removed after first query

Test Summary

Test	Why
Basic prompt example	Verifies core functionality
Repeated query	Ensures removals persist correctly
Progressive removals	Confirms nearby lamp shutdown logic
Single-cell grid	Smallest boundary condition
No lamps	Ensures unlit queries return 0
Duplicate lamps	Prevents double counting bugs
Neighbor removal	Validates 3x3 shutdown region
Huge n	Confirms solution does not depend on grid size
Diagonal illumination	Verifies diagonal bookkeeping
Column illumination	Verifies column tracking and removals

Edge Cases

One important edge case is duplicate lamp entries in the input. The problem explicitly allows repeated coordinates in lamps. A naive implementation might count the same lamp multiple times, causing row and diagonal counts to become incorrect. This implementation avoids that bug by storing lamps in a hash set first and ignoring duplicates during initialization.

Another critical edge case occurs when a query removes lamps that were already removed by earlier queries. Without checking whether a lamp is still active, counters could be decremented below zero. The solution safely checks membership in active_lamps before performing any removal.

Boundary handling is also important because queries near the edges or corners of the grid have neighboring cells outside the valid range. For example, query (0,0) has neighbors with negative coordinates. The implementation explicitly validates:

0 <= nr < n and 0 <= nc < n

before attempting removals, preventing invalid accesses.

A final subtle edge case involves extremely large grid sizes. Since n may be 10^9, any solution attempting to build the grid explicitly would immediately fail due to memory constraints. This implementation stores only active lamp positions and aggregate counts, so memory usage depends only on the number of lamps, not on the grid dimensions.