LeetCode Solutions Blog

Grid Illumination

Number: 1043

Difficulty: Hard

Paid? No

Companies: Dropbox

Problem Description

We are given an n x n grid and a list of lamp locations that are initially turned on. When a lamp is on, it illuminates its entire row, column, and both diagonals. For a series of queries asking if a particular cell is illuminated, we must return 1 if it is illuminated or 0 otherwise. After each query, we turn off any lamp (if present) at the query cell and its 8 adjacent cells.

Key Insights

Use hash maps (or dictionaries) to track the count of active lamps in each row, column, diagonal (r - c), and anti-diagonal (r + c) so that checking illumination for any cell becomes O(1).
Use a set to maintain the active lamp positions and to avoid duplicate processing.
For each query, check if any corresponding count (for the cell’s row, column, diags) is positive; if yes, the cell is illuminated.
Turn off all lamps in the 3 x 3 neighborhood around the query cell and update all maps accordingly.
Efficiently updating and checking data structures is crucial given the constraints.

Space and Time Complexity

Time Complexity: O(L + Q) on average, where L is the number of lamps and Q is the number of queries. Each query and each lamp update is O(1) average due to hash map and set operations. Space Complexity: O(L), for storing lamp positions and the counters.

Solution

We maintain four hash maps for rows, columns, diagonals, and anti-diagonals. All active lamp positions are stored in a set. During initialization, we add each lamp to our set and update the counters. For each query, we check if the queried cell is illuminated by any lamp using our maps. Then we iterate over the query cell and its 8 adjacent positions, removing any lamp present and decrementing the corresponding counts.

Code Solutions

# Python solution for Grid Illumination with detailed comments.
class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        # Dictionaries to track lamp counts in rows, columns, diagonal (r-c) and anti-diagonal (r+c)
        rowCount = {}
        colCount = {}
        diagCount = {}
        antiDiagCount = {}
        
        # Set to keep track of unique lamp positions
        lampsSet = set()
        
        # Initialize all lamp positions and update the counters.
        for r, c in lamps:
            if (r, c) in lampsSet:  # Avoid duplicate processing
                continue
            lampsSet.add((r, c))
            rowCount[r] = rowCount.get(r, 0) + 1
            colCount[c] = colCount.get(c, 0) + 1
            diagCount[r - c] = diagCount.get(r - c, 0) + 1
            antiDiagCount[r + c] = antiDiagCount.get(r + c, 0) + 1
            
        ans = []
        # Directions: the cell itself and its 8 adjacent positions.
        directions = [(0,0), (0,1), (0,-1), (1,0), (-1,0), (1,1), (1,-1), (-1,1), (-1,-1)]
        
        # Process each query.
        for r, c in queries:
            # Check if the cell is illuminated by any lamp in its row, column, diagonal, or anti-diagonal.
            if rowCount.get(r, 0) > 0 or colCount.get(c, 0) > 0 or diagCount.get(r - c, 0) > 0 or antiDiagCount.get(r + c, 0) > 0:
                ans.append(1)
            else:
                ans.append(0)
            
            # Turn off the lamp at this cell and its adjacent cells.
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if (nr, nc) in lampsSet:
                    lampsSet.remove((nr, nc))
                    # Update row count.
                    rowCount[nr] -= 1
                    if rowCount[nr] == 0:
                        del rowCount[nr]
                    # Update column count.
                    colCount[nc] -= 1
                    if colCount[nc] == 0:
                        del colCount[nc]
                    # Update diagonal count.
                    diagCount[nr - nc] -= 1
                    if diagCount[nr - nc] == 0:
                        del diagCount[nr - nc]
                    # Update anti-diagonal count.
                    antiDiagCount[nr + nc] -= 1
                    if antiDiagCount[nr + nc] == 0:
                        del antiDiagCount[nr + nc]
        
        return ans