1001. Grid Illumination

HardArrayHash Table

Problem Description

You have an n x n grid where each cell contains a lamp that starts in the "off" state.

You're given an array lamps where each element lamps[i] = [row_i, col_i] represents a lamp at position (row_i, col_i) that is turned on. If the same lamp position appears multiple times in the array, it's still just one lamp that's turned on.

When a lamp is on, it illuminates:

Its own cell
All cells in the same row
All cells in the same column
All cells on the same diagonal (both main diagonal and anti-diagonal)

You're also given an array queries where each queries[j] = [row_j, col_j] represents a query position. For each query, you need to:

Check if the cell at (row_j, col_j) is currently illuminated (by any lamp)
After checking, turn off the lamp at (row_j, col_j) if it exists, AND turn off all lamps in the 8 adjacent cells (the cells that share a side or corner with the query cell)

Return an array ans where ans[j] = 1 if the cell at the j-th query position was illuminated when checked, or 0 if it wasn't illuminated.

The key challenge is efficiently tracking which cells are illuminated as lamps get turned on and off, especially since a single lamp can illuminate an entire row, column, and both diagonals.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that we don't need to track every single illuminated cell in the grid - that would be inefficient for large grids. Instead, we can track which rows, columns, and diagonals have at least one lamp turned on.

Think about it this way: if there's even one lamp in row 5, then ALL cells in row 5 are illuminated. We don't need to mark each cell individually. The same logic applies to columns and diagonals.

For diagonals, we need a way to uniquely identify each diagonal line. If you observe cells on the same main diagonal (going from top-left to bottom-right), they all have the same value for row - col. For example, cells (2,1), (3,2), and (4,3) all have row - col = 1. Similarly, cells on the same anti-diagonal (going from top-right to bottom-left) have the same value for row + col.

So instead of a 2D grid tracking illumination, we can use four counters:

One for counting lamps in each row
One for counting lamps in each column
One for counting lamps on each main diagonal (identified by row - col)
One for counting lamps on each anti-diagonal (identified by row + col)

When checking if a cell (i, j) is illuminated, we just need to check if any of these four counters are non-zero:

Is there any lamp in row i?
Is there any lamp in column j?
Is there any lamp on the main diagonal with value i - j?
Is there any lamp on the anti-diagonal with value i + j?

For turning off lamps, we need to maintain a set of actual lamp positions. When we turn off a lamp at position (x, y), we decrement the corresponding counters for that lamp's row, column, and diagonals. This way, we can efficiently track when a line no longer has any lamps illuminating it.

Solution Approach

Let's walk through the implementation step by step:

1. Initialize Data Structures

First, we create a set s to store unique lamp positions: s = {(i, j) for i, j in lamps}. This removes duplicate lamp positions since we treat repeated lamps as a single lamp.

Then we create four Counter objects to track the number of lamps on each line:

row[i]: counts lamps in row i
col[j]: counts lamps in column j
diag1[i-j]: counts lamps on the main diagonal with value i-j
diag2[i+j]: counts lamps on the anti-diagonal with value i+j

2. Count Initial Lamps

For each unique lamp position (i, j) in the set:

row[i] += 1
col[j] += 1
diag1[i - j] += 1
diag2[i + j] += 1

This populates our counters with the initial lamp configuration.

3. Process Queries

For each query at position (i, j):

Check Illumination: A cell is illuminated if any of the following counters are non-zero:

row[i] (any lamp in the same row)
col[j] (any lamp in the same column)
diag1[i - j] (any lamp on the same main diagonal)
diag2[i + j] (any lamp on the same anti-diagonal)

If any of these are true, we set ans[k] = 1.

4. Turn Off Adjacent Lamps

After checking illumination, we need to turn off the lamp at the query position and all 8 adjacent lamps. We iterate through a 3×3 grid centered at (i, j):

for x in range(i - 1, i + 2):
    for y in range(j - 1, j + 2):

For each position (x, y) in this 3×3 grid, if there's a lamp (i.e., (x, y) in s):

Remove it from the set: s.remove((x, y))

Decrement all corresponding counters:

row[x] -= 1
col[y] -= 1
diag1[x - y] -= 1
diag2[x + y] -= 1

This ensures that if a line no longer has any lamps, its counter becomes 0, and cells on that line won't be considered illuminated in future queries.

5. Return Results

Finally, return the ans array containing the illumination status for each query.

The time complexity is O(L + Q) where L is the number of lamps and Q is the number of queries, since we process each lamp once initially and for each query we check at most 9 positions. The space complexity is O(L) for storing the lamp positions and counters.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with a 4×4 grid, 3 lamps, and 2 queries.

Initial Setup:

Grid size: n = 4
Lamps: [[1,1], [2,2], [0,3]]
Queries: [[1,0], [2,2]]

Step 1: Initialize and count lamps

Create a set of unique lamp positions: s = {(1,1), (2,2), (0,3)}

Initialize counters and populate them:

Lamp at (1,1):
- row[1] = 1, col[1] = 1, diag1[0] = 1, diag2[2] = 1
Lamp at (2,2):
- row[2] = 1, col[2] = 1, diag1[0] = 2, diag2[4] = 1
Lamp at (0,3):
- row[0] = 1, col[3] = 1, diag1[-3] = 1, diag2[3] = 1

Final counters:

row = {0:1, 1:1, 2:1}
col = {1:1, 2:1, 3:1}
diag1 = {0:2, -3:1} (note: diagonal 0 has 2 lamps!)
diag2 = {2:1, 3:1, 4:1}

Step 2: Process Query 1 at (1,0)

Check if (1,0) is illuminated:

row[1] = 1 ✓ (row 1 has a lamp)
col[0] = 0 ✗ (column 0 has no lamps)
diag1[1-0] = diag1[1] = 0 ✗ (diagonal 1 has no lamps)
diag2[1+0] = diag2[1] = 0 ✗ (anti-diagonal 1 has no lamps)

Result: Cell (1,0) IS illuminated (because row 1 has a lamp), so ans[0] = 1

Turn off lamps in 3×3 area around (1,0):

Check positions: (0,-1), (0,0), (0,1), (1,-1), (1,0), (1,1), (2,-1), (2,0), (2,1)
Only (1,1) has a lamp, so remove it:
- Remove (1,1) from set: s = {(2,2), (0,3)}
- Update counters: row[1]--, col[1]--, diag1[0]--, diag2[2]--

Updated counters:

row = {0:1, 1:0, 2:1}
col = {1:0, 2:1, 3:1}
diag1 = {0:1, -3:1}
diag2 = {2:0, 3:1, 4:1}

Step 3: Process Query 2 at (2,2)

Check if (2,2) is illuminated:

row[2] = 1 ✓ (row 2 has a lamp)
col[2] = 1 ✓ (column 2 has a lamp)
diag1[2-2] = diag1[0] = 1 ✓ (diagonal 0 has a lamp)
diag2[2+2] = diag2[4] = 1 ✓ (anti-diagonal 4 has a lamp)

Result: Cell (2,2) IS illuminated, so ans[1] = 1

Turn off lamps in 3×3 area around (2,2):

Check positions: (1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)
Only (2,2) has a lamp, so remove it:
- Remove (2,2) from set: s = {(0,3)}
- Update counters: row[2]--, col[2]--, diag1[0]--, diag2[4]--

Final counters:

row = {0:1, 1:0, 2:0}
col = {1:0, 2:0, 3:1}
diag1 = {0:0, -3:1}
diag2 = {2:0, 3:1, 4:0}

Final Answer: [1, 1]

Both query positions were illuminated when checked. The key insight is that we never tracked individual cell illumination - we only tracked which lines (rows, columns, diagonals) had lamps, making the solution efficient even for large grids.

Solution Implementation

1class Solution:
2    def gridIllumination(
3        self, n: int, lamps: List[List[int]], queries: List[List[int]]
4    ) -> List[int]:
5        # Convert lamp positions to a set for O(1) lookup and to remove duplicates
6        lamp_positions = {(row, col) for row, col in lamps}
7      
8        # Initialize counters to track illuminated rows, columns, and diagonals
9        # Each counter tracks how many lamps illuminate that particular line
10        illuminated_rows = Counter()
11        illuminated_cols = Counter()
12        illuminated_main_diag = Counter()  # Main diagonal (top-left to bottom-right)
13        illuminated_anti_diag = Counter()  # Anti-diagonal (top-right to bottom-left)
14      
15        # Count illumination for each lamp
16        for row, col in lamp_positions:
17            illuminated_rows[row] += 1
18            illuminated_cols[col] += 1
19            illuminated_main_diag[row - col] += 1  # Main diagonal has constant row - col
20            illuminated_anti_diag[row + col] += 1  # Anti-diagonal has constant row + col
21      
22        # Initialize result array
23        result = [0] * len(queries)
24      
25        # Process each query
26        for query_idx, (query_row, query_col) in enumerate(queries):
27            # Check if the queried cell is illuminated
28            # A cell is illuminated if its row, column, or either diagonal has any lamp
29            if (illuminated_rows[query_row] or 
30                illuminated_cols[query_col] or 
31                illuminated_main_diag[query_row - query_col] or 
32                illuminated_anti_diag[query_row + query_col]):
33                result[query_idx] = 1
34          
35            # Turn off all lamps in the 3x3 grid centered at the query position
36            for neighbor_row in range(query_row - 1, query_row + 2):
37                for neighbor_col in range(query_col - 1, query_col + 2):
38                    if (neighbor_row, neighbor_col) in lamp_positions:
39                        # Remove the lamp from the set
40                        lamp_positions.remove((neighbor_row, neighbor_col))
41                      
42                        # Update illumination counters
43                        illuminated_rows[neighbor_row] -= 1
44                        illuminated_cols[neighbor_col] -= 1
45                        illuminated_main_diag[neighbor_row - neighbor_col] -= 1
46                        illuminated_anti_diag[neighbor_row + neighbor_col] -= 1
47      
48        return result
49

1class Solution {
2    private int gridSize;
3  
4    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
5        this.gridSize = n;
6      
7        // Set to store positions of lit lamps (encoded as single long value)
8        Set<Long> litLamps = new HashSet<>();
9      
10        // Maps to count how many lamps illuminate each row, column, and diagonal
11        Map<Integer, Integer> rowCount = new HashMap<>();
12        Map<Integer, Integer> colCount = new HashMap<>();
13        Map<Integer, Integer> diag1Count = new HashMap<>();  // diagonal: top-left to bottom-right (i - j)
14        Map<Integer, Integer> diag2Count = new HashMap<>();  // diagonal: top-right to bottom-left (i + j)
15      
16        // Process initial lamp positions
17        for (int[] lamp : lamps) {
18            int row = lamp[0];
19            int col = lamp[1];
20          
21            // Only process if this lamp hasn't been added before (avoid duplicates)
22            if (litLamps.add(encodePosition(row, col))) {
23                // Increment counts for row, column, and both diagonals
24                updateCount(rowCount, row, 1);
25                updateCount(colCount, col, 1);
26                updateCount(diag1Count, row - col, 1);
27                updateCount(diag2Count, row + col, 1);
28            }
29        }
30      
31        // Process queries
32        int queryCount = queries.length;
33        int[] result = new int[queryCount];
34      
35        for (int queryIndex = 0; queryIndex < queryCount; queryIndex++) {
36            int queryRow = queries[queryIndex][0];
37            int queryCol = queries[queryIndex][1];
38          
39            // Check if the queried cell is illuminated
40            if (isIlluminated(rowCount, queryRow) || 
41                isIlluminated(colCount, queryCol) || 
42                isIlluminated(diag1Count, queryRow - queryCol) || 
43                isIlluminated(diag2Count, queryRow + queryCol)) {
44                result[queryIndex] = 1;
45            }
46          
47            // Turn off lamps in the 3x3 grid centered at query position
48            for (int neighborRow = queryRow - 1; neighborRow <= queryRow + 1; neighborRow++) {
49                for (int neighborCol = queryCol - 1; neighborCol <= queryCol + 1; neighborCol++) {
50                    // Skip if position is out of bounds
51                    if (neighborRow < 0 || neighborRow >= gridSize || 
52                        neighborCol < 0 || neighborCol >= gridSize) {
53                        continue;
54                    }
55                  
56                    // Skip if there's no lamp at this position
57                    long encodedPosition = encodePosition(neighborRow, neighborCol);
58                    if (!litLamps.contains(encodedPosition)) {
59                        continue;
60                    }
61                  
62                    // Turn off the lamp
63                    litLamps.remove(encodedPosition);
64                  
65                    // Decrement counts for row, column, and both diagonals
66                    updateCount(rowCount, neighborRow, -1);
67                    updateCount(colCount, neighborCol, -1);
68                    updateCount(diag1Count, neighborRow - neighborCol, -1);
69                    updateCount(diag2Count, neighborRow + neighborCol, -1);
70                }
71            }
72        }
73      
74        return result;
75    }
76  
77    /**
78     * Updates the count for a given key in the map.
79     * Removes the key if count becomes 0 to save memory.
80     */
81    private void updateCount(Map<Integer, Integer> countMap, int key, int delta) {
82        if (countMap.merge(key, delta, Integer::sum) == 0) {
83            countMap.remove(key);
84        }
85    }
86  
87    /**
88     * Checks if a given row/column/diagonal is illuminated (has at least one lamp).
89     */
90    private boolean isIlluminated(Map<Integer, Integer> countMap, int key) {
91        return countMap.getOrDefault(key, 0) > 0;
92    }
93  
94    /**
95     * Encodes 2D grid position (i, j) into a single long value.
96     * This allows us to store positions in a Set efficiently.
97     */
98    private long encodePosition(long row, long col) {
99        return row * gridSize + col;
100    }
101}
102

1class Solution {
2public:
3    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
4        // Lambda function to convert 2D coordinates to a unique 1D value
5        // Using long long to avoid integer overflow for large grids
6        auto coordinateToKey = [&](int row, int col) -> long long {
7            return (long long)row * n + col;
8        };
9      
10        // Set to store currently lit lamps (using their unique keys)
11        unordered_set<long long> litLamps;
12      
13        // Maps to count how many lamps illuminate each row, column, and diagonal
14        unordered_map<int, int> rowCount;       // Count of lamps in each row
15        unordered_map<int, int> colCount;       // Count of lamps in each column
16        unordered_map<int, int> mainDiagCount;  // Count of lamps on each main diagonal (row - col)
17        unordered_map<int, int> antiDiagCount;  // Count of lamps on each anti-diagonal (row + col)
18      
19        // Initialize all lamps and update illumination counts
20        for (auto& lamp : lamps) {
21            int row = lamp[0];
22            int col = lamp[1];
23            long long lampKey = coordinateToKey(row, col);
24          
25            // Only process if this lamp isn't already lit (avoid duplicates)
26            if (!litLamps.count(lampKey)) {
27                litLamps.insert(lampKey);
28                rowCount[row]++;
29                colCount[col]++;
30                mainDiagCount[row - col]++;
31                antiDiagCount[row + col]++;
32            }
33        }
34      
35        int numQueries = queries.size();
36        vector<int> result(numQueries);
37      
38        // Process each query
39        for (int queryIdx = 0; queryIdx < numQueries; ++queryIdx) {
40            int queryRow = queries[queryIdx][0];
41            int queryCol = queries[queryIdx][1];
42          
43            // Check if the queried cell is illuminated
44            // A cell is illuminated if any lamp in its row, column, or diagonals is lit
45            if (rowCount[queryRow] > 0 || 
46                colCount[queryCol] > 0 || 
47                mainDiagCount[queryRow - queryCol] > 0 || 
48                antiDiagCount[queryRow + queryCol] > 0) {
49                result[queryIdx] = 1;
50            }
51          
52            // Turn off all lamps in the 3x3 grid centered at the query cell
53            for (int adjacentRow = queryRow - 1; adjacentRow <= queryRow + 1; ++adjacentRow) {
54                for (int adjacentCol = queryCol - 1; adjacentCol <= queryCol + 1; ++adjacentCol) {
55                    // Skip if out of bounds
56                    if (adjacentRow < 0 || adjacentRow >= n || 
57                        adjacentCol < 0 || adjacentCol >= n) {
58                        continue;
59                    }
60                  
61                    long long lampKey = coordinateToKey(adjacentRow, adjacentCol);
62                  
63                    // Skip if no lamp at this position
64                    if (!litLamps.count(lampKey)) {
65                        continue;
66                    }
67                  
68                    // Turn off the lamp and update all affected counts
69                    litLamps.erase(lampKey);
70                    rowCount[adjacentRow]--;
71                    colCount[adjacentCol]--;
72                    mainDiagCount[adjacentRow - adjacentCol]--;
73                    antiDiagCount[adjacentRow + adjacentCol]--;
74                }
75            }
76        }
77      
78        return result;
79    }
80};
81

1/**
2 * Solves the grid illumination problem where lamps illuminate entire rows, columns, and diagonals.
3 * After each query, lamps in the 3x3 area centered at the query position are turned off.
4 * 
5 * @param n - The size of the n x n grid
6 * @param lamps - Array of lamp positions [row, col]
7 * @param queries - Array of query positions to check illumination status
8 * @returns Array of 0s and 1s indicating whether each query position is illuminated
9 */
10function gridIllumination(n: number, lamps: number[][], queries: number[][]): number[] {
11    // Maps to track the count of lamps illuminating each row, column, and diagonal
12    const rowLampCount = new Map<number, number>();
13    const colLampCount = new Map<number, number>();
14    const mainDiagonalCount = new Map<number, number>();  // Diagonal from top-left to bottom-right
15    const antiDiagonalCount = new Map<number, number>();  // Diagonal from top-right to bottom-left
16  
17    // Set to track which lamps are currently on (using flattened coordinates)
18    const activeLamps = new Set<number>();
19  
20    // Initialize lamp positions and update illumination counts
21    for (const [row, col] of lamps) {
22        const flattenedPosition = row * n + col;
23      
24        // Skip if lamp is already placed at this position
25        if (activeLamps.has(flattenedPosition)) {
26            continue;
27        }
28      
29        // Add lamp to active set
30        activeLamps.add(flattenedPosition);
31      
32        // Increment illumination counts for affected row, column, and diagonals
33        rowLampCount.set(row, (rowLampCount.get(row) || 0) + 1);
34        colLampCount.set(col, (colLampCount.get(col) || 0) + 1);
35        mainDiagonalCount.set(row - col, (mainDiagonalCount.get(row - col) || 0) + 1);
36        antiDiagonalCount.set(row + col, (antiDiagonalCount.get(row + col) || 0) + 1);
37    }
38  
39    const result: number[] = [];
40  
41    // Process each query
42    for (const [queryRow, queryCol] of queries) {
43        // Check if the query position is illuminated by any lamp
44        const isIlluminated = 
45            (rowLampCount.get(queryRow) || 0) > 0 ||
46            (colLampCount.get(queryCol) || 0) > 0 ||
47            (mainDiagonalCount.get(queryRow - queryCol) || 0) > 0 ||
48            (antiDiagonalCount.get(queryRow + queryCol) || 0) > 0;
49      
50        result.push(isIlluminated ? 1 : 0);
51      
52        // Turn off all lamps in the 3x3 area centered at the query position
53        for (let neighborRow = queryRow - 1; neighborRow <= queryRow + 1; neighborRow++) {
54            for (let neighborCol = queryCol - 1; neighborCol <= queryCol + 1; neighborCol++) {
55                // Check if the neighbor position is within grid bounds
56                if (neighborRow < 0 || neighborRow >= n || neighborCol < 0 || neighborCol >= n) {
57                    continue;
58                }
59              
60                const flattenedPosition = neighborRow * n + neighborCol;
61              
62                // Check if there's an active lamp at this position
63                if (!activeLamps.has(flattenedPosition)) {
64                    continue;
65                }
66              
67                // Turn off the lamp and update illumination counts
68                activeLamps.delete(flattenedPosition);
69                rowLampCount.set(neighborRow, rowLampCount.get(neighborRow)! - 1);
70                colLampCount.set(neighborCol, colLampCount.get(neighborCol)! - 1);
71                mainDiagonalCount.set(neighborRow - neighborCol, mainDiagonalCount.get(neighborRow - neighborCol)! - 1);
72                antiDiagonalCount.set(neighborRow + neighborCol, antiDiagonalCount.get(neighborRow + neighborCol)! - 1);
73            }
74        }
75    }
76  
77    return result;
78}
79

Time and Space Complexity

Time Complexity: O(m + q)

The time complexity breaks down as follows:

Creating the set s from lamps takes O(m) time, where m is the number of lamps
Initializing the counters (row, col, diag1, diag2) by iterating through the set takes O(m) time
Processing queries takes O(q) time, where q is the number of queries:
- For each query, checking if the position is illuminated takes O(1) time
- Turning off adjacent lamps involves checking a 3×3 grid (at most 9 cells), which is O(1) constant time
- Set removal and counter updates are O(1) operations
Total: O(m) + O(m) + O(q) = O(m + q)

Space Complexity: O(m)

The space complexity consists of:

Set s stores at most m unique lamp positions: O(m)
Four Counter objects (row, col, diag1, diag2) each store at most m entries: O(m)
Answer array stores q results: O(q)
Total: O(m) + O(q), which simplifies to O(m + q)

However, if we consider that the output array is required for the result and not counted as extra space, the auxiliary space complexity is O(m).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling Grid Boundaries When Turning Off Adjacent Lamps

A critical pitfall is not checking whether the adjacent cells are within the valid grid boundaries (0 to n-1) when turning off lamps. The current code iterates through a 3×3 grid without boundary validation:

for neighbor_row in range(query_row - 1, query_row + 2):
    for neighbor_col in range(query_col - 1, query_col + 2):
        if (neighbor_row, neighbor_col) in lamp_positions:
            # Process lamp...

Problem: When the query is at the edge of the grid (e.g., position (0, 0) or (n-1, n-1)), this code will check positions outside the grid like (-1, -1) or (n, n). While this won't cause an error since we're using a set lookup, it's inefficient and conceptually incorrect to check invalid positions.

Solution: Add boundary checks before processing each adjacent position:

for neighbor_row in range(max(0, query_row - 1), min(n, query_row + 2)):
    for neighbor_col in range(max(0, query_col - 1), min(n, query_col + 2)):
        if (neighbor_row, neighbor_col) in lamp_positions:
            # Process lamp...

2. Processing Duplicate Lamps Multiple Times

Another common mistake is forgetting to handle duplicate lamp positions in the input array. If the same lamp position appears multiple times in the lamps array, counting it multiple times would incorrectly inflate the illumination counters.

Problem Example: If lamps = [[1, 1], [1, 1], [2, 2]], processing the lamp at (1, 1) twice would set illuminated_rows[1] = 2 instead of 1, causing incorrect illumination detection even after the lamp is turned off.

Solution: The code correctly handles this by converting the lamp list to a set first:

lamp_positions = {(row, col) for row, col in lamps}

This ensures each unique position is processed only once when initializing the counters.

3. Using Wrong Diagonal Formulas

A subtle but critical error is using incorrect formulas for diagonal identification. The correct formulas are:

Main diagonal: row - col (constant for all cells on the same main diagonal)
Anti-diagonal: row + col (constant for all cells on the same anti-diagonal)

Common Mistake: Swapping these formulas or using row + col for main diagonal and row - col for anti-diagonal would cause incorrect illumination tracking.

Verification: You can verify the formulas by checking a few examples:

Main diagonal through (2,1), (3,2), (4,3): all have row - col = 1
Anti-diagonal through (0,2), (1,1), (2,0): all have row + col = 2

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Depth First Search

Breadth First Search

I don't know