How do you solve Grid Illumination on LeetCode?

Grid Illumination (LeetCode #1001) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using hash maps allows for efficient tracking of lamp states.

What is the brute force solution for Grid Illumination?

The brute force approach for Grid Illumination is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each query against all lamps to determine if the queried cell is illuminated. This is straightforward but inefficient since it involves checking multiple conditions for each query. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Grid Illumination?

Grid Illumination uses the following concepts: Array, Hash Table. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Grid Illumination?

Clarify the problem requirements before jumping into coding. Discuss your thought process and approach with the interviewer. Consider edge cases and test your solution with them.

What are common mistakes when solving Grid Illumination?

Not considering the diagonal illumination. Failing to update lamp states correctly after queries.

#1001

Grid Illumination

Hard

ArrayHash TableHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Instead of checking each lamp for every query, we can use hash maps to track the number of lamps illuminating each row, column, and diagonal. This allows us to efficiently determine if a cell is illuminated in constant time.

⚙️

Algorithm

3 steps

1Step 1: Use hash maps to count lamps in each row, column, and diagonal.
2Step 2: For each query, check the counts in the respective row, column, and diagonals to determine if the cell is illuminated.
3Step 3: If illuminated, record '1' in the result and decrement the counts for the lamp at the queried position and its adjacent lamps.

solution.py27 lines

1# Full working Python code
2class Solution:
3    def gridIllumination(self, n, lamps, queries):
4        row_count, col_count, diag1_count, diag2_count = {}, {}, {}, {}
5        lamps_set = set()
6        for r, c in lamps:
7            row_count[r] = row_count.get(r, 0) + 1
8            col_count[c] = col_count.get(c, 0) + 1
9            diag1_count[r - c] = diag1_count.get(r - c, 0) + 1
10            diag2_count[r + c] = diag2_count.get(r + c, 0) + 1
11            lamps_set.add((r, c))
12        ans = []
13        for r, c in queries:
14            if (row_count.get(r, 0) > 0 or col_count.get(c, 0) > 0 or diag1_count.get(r - c, 0) > 0 or diag2_count.get(r + c, 0) > 0):
15                ans.append(1)
16            else:
17                ans.append(0)
18            # Turn off the lamp and its adjacent lamps
19            for dr in [-1, 0, 1]:
20                for dc in [-1, 0, 1]:
21                    if (r + dr, c + dc) in lamps_set:
22                        lamps_set.remove((r + dr, c + dc))
23                        row_count[r + dr] -= 1
24                        col_count[c + dc] -= 1
25                        diag1_count[r + dr - (c + dc)] -= 1
26                        diag2_count[r + dr + (c + dc)] -= 1
27        return ans

ℹ

Complexity note: The time complexity is O(n) because each query can be processed in constant time using the hash maps, while the space complexity is O(n) due to the storage of lamp counts and positions.

1Using hash maps allows for efficient tracking of lamp states.
2Understanding the illumination pattern helps optimize the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.