#1001

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Grid Illumination

Grid Illumination uses an array scanning approach with hash lookups to check illuminated cells in a large grid based on lamp positions.

array hash table

Problem Statement

You are given a 2D grid of size n x n where each cell has a lamp initially turned off. The grid has a set of lamp positions given in the array lamps, where each entry represents the coordinates of an active lamp. These lamps illuminate the row, column, and diagonals they belong to. The grid is sparse, and multiple lamps may reside in the same position.

Your task is to process a set of queries where each query asks if a specific grid cell is illuminated by any active lamp. After processing each query, you must turn off the lamps in the area affected by that query. Efficiently determining the state of the grid and the illumination status of queried cells is key, as the grid size can be enormous.

Examples

Example 1

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

Output: [1,0]

We have the initial grid with all lamps turned off. In the above picture we see the grid after turning on the lamp at grid[0][0] then turning on the lamp at grid[4][4]. The 0th query asks if the lamp at grid[1][1] is illuminated or not (the blue square). It is illuminated, so set ans[0] = 1. Then, we turn off all lamps in the red square.

The 1st query asks if the lamp at grid[1][0] is illuminated or not (the blue square). It is not illuminated, so set ans[1] = 0. Then, we turn off all lamps in the red rectangle.

Example 2

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

Output: [1,1]

Example details omitted.

Example 3

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

Output: [1,1,0]

Example details omitted.

Constraints

1 <= n <= 109
0 <= lamps.length <= 20000
0 <= queries.length <= 20000
lamps[i].length == 2
0 <= rowi, coli < n
queries[j].length == 2
0 <= rowj, colj < n

Solution Approach

Lamp Position Tracking

To efficiently solve this problem, track the positions of the lamps using hash sets for rows, columns, and diagonals. For each lamp, update the row, column, and diagonal sets with the lamp's coordinates. This allows quick verification whether a lamp illuminates a specific cell during the queries.

Query Resolution with Hash Lookups

For each query, check if the specific cell is illuminated by checking if its row, column, or diagonal contains an active lamp. The lookup can be done in constant time using the hash sets from the previous step. After processing the query, remove the affected lamp from all relevant sets to simulate turning it off.

Efficient Grid Updates

Efficient updates to the grid are necessary to handle large grid sizes. After each query, efficiently update the hash sets by removing lamps from the affected rows, columns, and diagonals. Ensure this removal happens only when necessary to maintain the optimal time complexity of the solution.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution primarily depends on the number of lamps and queries. Storing lamp positions in hash sets allows constant time lookups, making each query resolution efficient. Removing a lamp requires updating a few hash sets, which can also be done in constant time. Overall, the approach works in O(L + Q) time, where L is the number of lamps and Q is the number of queries, with space complexity O(L) for storing the lamp positions in hash sets.

What Interviewers Usually Probe

Can the candidate optimize the solution when lamps are sparse in the grid?
Is the candidate able to explain the trade-offs of storing lamp positions in hash sets versus a 2D array?
How does the candidate handle large grid sizes with respect to time and space complexity?

Common Pitfalls or Variants

Common pitfalls

Not using hash sets for row, column, and diagonal tracking, leading to inefficient query resolution.
Failure to remove lamps from the hash sets after processing queries, which can affect the results of subsequent queries.
Overcomplicating the grid updates when dealing with large values of n, leading to unnecessary computations.

Follow-up variants

Handling queries where multiple lamps are turned off at once, affecting multiple rows, columns, and diagonals.
Adapting the solution to handle multiple grid sizes more efficiently.
Optimizing memory usage when handling large n values by compressing lamp positions.

FAQ

What is the primary pattern used to solve the Grid Illumination problem?

The problem is solved using array scanning combined with hash lookup to efficiently check if a grid cell is illuminated by any lamp.

How does using hash sets improve the performance of Grid Illumination?

Hash sets allow constant-time lookups and updates for the row, column, and diagonal illuminations, ensuring that queries can be resolved efficiently even for large grids.

What should I keep in mind when handling large values of n in the Grid Illumination problem?

When dealing with large n, it is crucial to focus on the efficiency of the query resolution using hash sets, ensuring space complexity remains manageable while still processing queries in constant time.

Can I use a 2D array instead of hash sets for this problem?

While a 2D array could be used to track the lamps, it would result in inefficient time complexity for both lookup and updates, especially for large grids. Hash sets provide a more efficient solution.

How does GhostInterview help with solving Grid Illumination?

GhostInterview provides step-by-step guidance, ensuring the candidate leverages hash sets for optimal query resolution, avoids common pitfalls, and maintains efficient time and space complexity.

terminal

Solution

Solution 1: Hash Table

Suppose the coordinates of a lamp are $(x, y)$. Then, the row value is $x$, the column value is $y$, the main diagonal value is $x-y$, and the anti-diagonal value is $x+y$. Once we determine the unique value identifier for a line, we can use a hash table to record the number of lamps on that line.

class Solution:
    def gridIllumination(
        self, n: int, lamps: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        s = {(i, j) for i, j in lamps}
        row, col, diag1, diag2 = Counter(), Counter(), Counter(), Counter()
        for i, j in s:
            row[i] += 1
            col[j] += 1
            diag1[i - j] += 1
            diag2[i + j] += 1
        ans = [0] * len(queries)
        for k, (i, j) in enumerate(queries):
            if row[i] or col[j] or diag1[i - j] or diag2[i + j]:
                ans[k] = 1
            for x in range(i - 1, i + 2):
                for y in range(j - 1, j + 2):
                    if (x, y) in s:
                        s.remove((x, y))
                        row[x] -= 1
                        col[y] -= 1
                        diag1[x - y] -= 1
                        diag2[x + y] -= 1
        return ans

Continue Practicing

#1002 find common characters #997 find the town judge #996 number of squareful arrays