1001. Grid Illumination
Problem Description
The problem describes a grid of size n x n
, where every cell can have a lamp. Initially, all lamps are turned off. A list of lamp positions is given that specifies which lamps are turned on. When a lamp is on, it illuminates its cell, as well as all cells in the same row, column, and diagonals. The main task is to process a series of queries. Each query asks whether a specific cell in the grid is illuminated. After checking a cell for a query, the lamp at that cell and the 8 adjacent cells (if they have lamps) should be turned off. The solution should return an array indicating for each query if the cell was illuminated (1
) or not (0
).
Intuition
The intuitive approach to solve this problem is to simulate the process as described. However, directly turning lamps on and off in a grid would be inefficient for large grids. Instead, we need a way to quickly determine if a cell is illuminated without traversing the whole grid.
The insight is to use hash tables to keep track of the counts of lit lamps in each row, column, and diagonal efficiently. When a lamp is turned on, we increase the count in its row, column, and both diagonals it belongs to. Similarly, when we turn off a lamp, we decrease the count for corresponding row, column, and diagonals.
row
and col
hash tables track the number of lamps turned on in each row and column.
diag1
and diag2
hash tables track the lamps for the two sets of diagonals. For a cell (i, j)
, diag1
uses i - j
for one set of diagonals, where cells on the same diagonal have the same i - j
value, and diag2
uses i + j
for the other set.
During each query, we check the counts in row
, col
, diag1
, and diag2
, to determine if a cell is illuminated. After that, we turn off the lamp at the queried cell and its adjacent lamps. This requires another nested loop over the cell and its neighbors, updating the hash tables and a set that keeps track of which lamps are currently on.
Following these steps ensures that the solution is efficient and can handle a large number of queries.
Solution Approach
The solution is implemented in Python, utilizing sets and multiple instances of the Counter
class from the collections
module for efficient data tracking and manipulation. Here is a walkthrough of the solution:
-
Initialize Data Structures:
- A set
s
is used to keep track of the unique positions of the turned-on lamps. - Four counters
row
,col
,diag1
, anddiag2
are used to track the count of lamps that are currently illuminating each row, column, and the two sets of diagonals, respectively.
- A set
-
Preprocessing Lamps:
- Iterate through each lamp in the set
s
. - For each lamp at position
(i, j)
, the corresponding row, column, and diagonal counters are incremented to reflect the presence of a lamp that illuminates these lines.
- Iterate through each lamp in the set
-
Processing Queries:
- Initialize an answer list
ans
with zeros, with the same length as the list of queries. - For each query
(i, j)
, do the following:- If the
row[i]
,col[j]
,diag1[i - j]
, ordiag2[i + j]
counter is greater than0
, it means the cell is illuminated. In this case, setans[k]
(wherek
is the index for the current query) to1
.
- If the
- Initialize an answer list
-
Turning Off Lamps:
- After each query check, proceed to turn off the lamp at the queried cell
(i, j)
and its 8 adjacent cells (if they exist). This is done by iterating through cells from(i - 1, j - 1)
to(i + 1, j + 1)
, including the cell itself and its neighbors. - For each cell
(x, y)
in this range, if it has a lamp (i.e., if(x, y)
exists in sets
), we remove the lamp from the sets
and decrement the counts in the correspondingrow
,col
,diag1
, anddiag2
.
- After each query check, proceed to turn off the lamp at the queried cell
-
Output:
- Return the answer list
ans
, which contains the results of each query represented as1
or0
.
- Return the answer list
In this solution, data structures are leveraged to ensure that we do not have to iterate through the entirety of the grid for each query, thereby achieving a more efficient algorithm. By using hash tables (here, implemented as Counter
objects) and a set, we are able to keep the time complexity lower than a brute-force solution. The counters enable us to quickly check whether a cell is illuminated or not, and the set allows us to efficiently update which lamps are turned on or off.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a 3x3 grid where n = 3
, with the initial lamp positions being:
- Lamp 1 at (0, 0)
- Lamp 2 at (1, 1)
- Lamp 3 at (2, 2)
And we have the following two queries:
- Is the cell at (0, 1) illuminated?
- Is the cell at (1, 1) illuminated?
Now, let's walk through the solution approach step-by-step with this example.
Step 1: Initialize Data Structures
- Create a set
s
with lamp positions:s = {(0, 0), (1, 1), (2, 2)}
- Create counters
row
,col
,diag1
,diag2
:- Initially all are empty and counts are zero.
Step 2: Preprocessing Lamps
- For each lamp, increment the corresponding row, column, and diagonal:
row[0]
now becomes1
because of lamp 1 at (0, 0)col[0]
also becomes1
because of lamp 1 at (0, 0)diag1[0]
(calculated as0 - 0
) becomes1
diag2[0]
(calculated as0 + 0
) becomes1
- Similar updates happen for lamp 2 at (1, 1) and lamp 3 at (2, 2)
Step 3: Processing Queries
- Initialize answer list
ans
to [0, 0] because there are two queries. - For Query 1 at (0, 1): Check
row[0]
,col[1]
,diag1[-1]
,diag2[1]
. Sincerow[0]
is1
, the cell (0, 1) is illuminated.- Set
ans[0]
to1
.
- Set
- For Query 2 at (1, 1): Check
row[1]
,col[1]
,diag1[0]
,diag2[2]
. Sincerow[1]
,col[1]
, and both diag counters are1
, the cell (1, 1) is illuminated.- Set
ans[1]
to1
.
- Set
Step 4: Turning Off Lamps
- After Query 1, turn off lamp 1 and its adjacent lamps (in this case, there are no other lamps adjacent).
- Remove
(0, 0)
froms
. - Decrement
row[0]
,col[0]
,diag1[0]
, anddiag2[0]
.
- Remove
- After Query 2, turn off lamp 2 at (1, 1) and any adjacent lamps. Lamp 3 at (2, 2) is adjacent and also gets turned off.
- Remove
(1, 1)
and(2, 2)
froms
. - Decrement
row[1]
,col[1]
, and both diagonal counters for both lamps.
- Remove
Step 5: Output
- Return the answer list
ans
which now is [1, 1] since both queries resulted in illuminated cells before turning off the lamps.
This example illustrates how the data structures and counts help in avoiding unnecessary scanning of the entire grid and instead use lookups to efficiently determine if a cell is illuminated and update the lamp states accordingly.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
5 # Convert the list of lamps into a set for O(1) access and to avoid duplicates
6 lamp_positions = {(i, j) for i, j in lamps}
7
8 # These counters will keep track of how many lamps are illuminating each row, column, and diagonal
9 row_count, col_count, diag1_count, diag2_count = Counter(), Counter(), Counter(), Counter()
10
11 # Initialize the counters based on the starting positions of lamps
12 for i, j in lamp_positions:
13 row_count[i] += 1
14 col_count[j] += 1
15 diag1_count[i - j] += 1
16 diag2_count[i + j] += 1
17
18 # Initialize the array to be returned with the results of the queries
19 results = [0] * len(queries)
20
21 # Process each query to check for illumination
22 for index, (i, j) in enumerate(queries):
23 # Check if the cell is illuminated by seeing if its row, column, or diagonals have any lamps.
24 if row_count[i] or col_count[j] or diag1_count[i - j] or diag2_count[i + j]:
25 results[index] = 1 # Illuminate
26
27 # Turn off lamps in adjacent cells including diagonals.
28 for x in range(i - 1, i + 2):
29 for y in range(j - 1, j + 2):
30 # Make sure to remove the lamp if it's in the list
31 if (x, y) in lamp_positions:
32 lamp_positions.remove((x, y))
33 # Update the counters since we turned off a lamp
34 row_count[x] -= 1
35 col_count[y] -= 1
36 diag1_count[x - y] -= 1
37 diag2_count[x + y] -= 1
38
39 # Return the results of the queries as a list of integers
40 return results
41
1class Solution {
2 private int gridSize; // The size of the grid
3 public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
4 this.gridSize = n; // Setting the grid size
5 Set<Long> illuminatedLamps = new HashSet<>();
6 Map<Integer, Integer> rows = new HashMap<>();
7 Map<Integer, Integer> columns = new HashMap<>();
8 Map<Integer, Integer> diagonal1 = new HashMap<>();
9 Map<Integer, Integer> diagonal2 = new HashMap<>();
10
11 // Initialize the maps and sets with the lamp positions
12 for (int[] lamp : lamps) {
13 int row = lamp[0], column = lamp[1];
14 if (illuminatedLamps.add(encode(row, column))) {
15 increaseCount(rows, row);
16 increaseCount(columns, column);
17 increaseCount(diagonal1, row - column);
18 increaseCount(diagonal2, row + column);
19 }
20 }
21
22 int queryCount = queries.length;
23 int[] results = new int[queryCount];
24
25 // Process each query to determine if the grid cell is illuminated
26 for (int k = 0; k < queryCount; ++k) {
27 int row = queries[k][0], column = queries[k][1];
28 if (isIlluminated(rows, row) || isIlluminated(columns, column) ||
29 isIlluminated(diagonal1, row - column) || isIlluminated(diagonal2, row + column)) {
30 results[k] = 1;
31 }
32
33 // Turn off lamps in the surrounding (3x3) cells if they exist
34 for (int x = row - 1; x <= row + 1; ++x) {
35 for (int y = column - 1; y <= column + 1; ++y) {
36 if (x < 0 || x >= gridSize || y < 0 || y >= gridSize ||
37 !illuminatedLamps.contains(encode(x, y))) {
38 continue;
39 }
40 illuminatedLamps.remove(encode(x, y));
41 decreaseCount(rows, x);
42 decreaseCount(columns, y);
43 decreaseCount(diagonal1, x - y);
44 decreaseCount(diagonal2, x + y);
45 }
46 }
47 }
48 return results;
49 }
50
51 // Helper method to either increment or decrement the count of lit cells
52 private void increaseCount(Map<Integer, Integer> countMap, int key) {
53 countMap.merge(key, 1, Integer::sum);
54 }
55
56 // Helper method to decrease the illumination count when a lamp is turned off
57 private void decreaseCount(Map<Integer, Integer> countMap, int key) {
58 if (countMap.merge(key, -1, Integer::sum) == 0) {
59 countMap.remove(key);
60 }
61 }
62
63 // Helper method to check if a cell is illuminated in any direction
64 private boolean isIlluminated(Map<Integer, Integer> countMap, int key) {
65 return countMap.getOrDefault(key, 0) > 0;
66 }
67
68 // Helper method to encode the 2D position into a single long value
69 private long encode(long row, long column) {
70 return row * gridSize + column;
71 }
72}
73
1class Solution {
2public:
3 vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
4 // Lambda function to encode a 2D position (i, j) into a unique 1D integer
5 auto encode = [&](int i, int j) -> long long {
6 return static_cast<long long>(i) * n + j;
7 };
8
9 // A set to hold the unique encoding of the illuminated positions
10 unordered_set<long long> illuminated;
11 // Maps to keep track of the count of illuminated lamps in each row, column and two diagonals
12 unordered_map<int, int> rows, cols, diag1, diag2;
13
14 // Initializing the illuminated positions based on the provided lamps array
15 for (auto& lamp : lamps) {
16 int i = lamp[0], j = lamp[1];
17 long long code = encode(i, j);
18 if (!illuminated.count(code)) { // Ensure we don't process a lamp multiple times
19 illuminated.insert(code);
20 rows[i]++;
21 cols[j]++;
22 diag1[i - j]++;
23 diag2[i + j]++;
24 }
25 }
26
27 int queryCount = queries.size();
28 vector<int> answers(queryCount); // Vector to hold the answers to the queries
29
30 // Process each query to check if the grid cell is illuminated
31 for (int i = 0; i < queryCount; ++i) {
32 int queryRow = queries[i][0], queryCol = queries[i][1];
33
34 // If any lamp is illuminating the cell at (queryRow, queryCol), set the answer to 1
35 if (rows[queryRow] > 0 || cols[queryCol] > 0 || diag1[queryRow - queryCol] > 0 || diag2[queryRow + queryCol] > 0) {
36 answers[i] = 1;
37 }
38
39 // Check the surroundings of the cell (3x3 area around the query point) to turn off lamps
40 for (int x = queryRow - 1; x <= queryRow + 1; ++x) {
41 for (int y = queryCol - 1; y <= queryCol + 1; ++y) {
42 if (x < 0 || x >= n || y < 0 || y >= n) { // Check boundary conditions
43 continue;
44 }
45 long long positionCode = encode(x, y);
46 if (!illuminated.count(positionCode)) { // Skip if there's no lamp
47 continue;
48 }
49
50 // If a lamp exists at this position, turn it off by removing from set and updating counts
51 illuminated.erase(positionCode);
52 rows[x]--;
53 cols[y]--;
54 diag1[x - y]--;
55 diag2[x + y]--;
56 }
57 }
58 }
59
60 return answers; // Return the results of the queries
61 }
62};
63
1function gridIllumination(n: number, lamps: number[][], queries: number[][]): number[] {
2 // Maps to keep track of the counts for each row, column, and diagonal
3 const rowCount = new Map<number, number>();
4 const colCount = new Map<number, number>();
5 const diag1Count = new Map<number, number>(); // primary diagonal (top-left to bottom-right)
6 const diag2Count = new Map<number, number>(); // secondary diagonal (top-right to bottom-left)
7
8 // Set to keep track of unique lamp positions using a unique identifier for each position
9 const activeLamps = new Set<number>();
10
11 // Initialize the light grid and populate the maps with lamp information
12 for (const [row, col] of lamps) {
13 const id = row * n + col; // Create a unique identifier for the lamp position
14
15 // If the lamp is already added, skip it
16 if (activeLamps.has(id)) {
17 continue;
18 }
19
20 // Add the lamp to the set of active lamps
21 activeLamps.add(id);
22
23 // Increment counts for corresponding row, column, and both diagonals
24 rowCount.set(row, (rowCount.get(row) || 0) + 1);
25 colCount.set(col, (colCount.get(col) || 0) + 1);
26 diag1Count.set(row - col, (diag1Count.get(row - col) || 0) + 1);
27 diag2Count.set(row + col, (diag2Count.get(row + col) || 0) + 1);
28 }
29
30 // Array to hold the results of the queries
31 const results: number[] = [];
32
33 // Process each query
34 for (const [row, col] of queries) {
35 // Check if any of the row, column, or diagonals are illuminated
36 if (rowCount.get(row)! > 0 || colCount.get(col)! > 0 ||
37 diag1Count.get(row - col)! > 0 || diag2Count.get(row + col)! > 0) {
38 results.push(1); // The cell is illuminated
39 } else {
40 results.push(0); // The cell is not illuminated
41 }
42
43 // Turn off all lamps in the surrounding (3x3) area of the query
44 for (let x = row - 1; x <= row + 1; ++x) {
45 for (let y = col - 1; y <= col + 1; ++y) {
46 // Skip positions outside the grid bounds or without a lamp
47 if (x < 0 || x >= n || y < 0 || y >= n || !activeLamps.has(x * n + y)) {
48 continue;
49 }
50
51 // Remove the lamp from the set of active lamps
52 activeLamps.delete(x * n + y);
53
54 // Decrement counts for the corresponding row, column, and diagonals
55 rowCount.set(x, rowCount.get(x)! - 1);
56 colCount.set(y, colCount.get(y)! - 1);
57 diag1Count.set(x - y, diag1Count.get(x - y)! - 1);
58 diag2Count.set(x + y, diag2Count.get(x + y)! - 1);
59 }
60 }
61 }
62 // Return the array of query results
63 return results;
64}
65
Time and Space Complexity
Time Complexity
The provided code has several main parts that contribute to the overall time complexity:
-
Initialization of Sets and Counters: The creation of the initial set
s
and the counters forrow
,col
,diag1
, anddiag2
. This part has a time complexity ofO(L)
, whereL
is the number of lamps, since each lamp is visited once. -
Updating Counters: For each lamp, the code updates the
row
,col
,diag1
, anddiag2
counters. Since there areL
lamps, and each update operation isO(1)
, this is alsoO(L)
in total. -
Processing Queries: The main portion of the work occurs during the processing of the queries. For each query, the code checks counters which is
O(1)
, but then potentially updates counters for up to 9 cells (including the query cell and its neighbors). Since there areQ
queries, and each query may result in updates to a fixed number of lamp positions (at most 9), this part has a time complexity ofO(Q)
.
Combining these parts, the total time complexity of the algorithm is O(L + Q)
.
Space Complexity
The space complexity of the code is influenced by the storage required for the set s
and the counters row
, col
, diag1
, and diag2
.
-
Storage for lamp positions (
s
): Space complexity isO(L)
because we store each lamp's position at most once in the set. -
Counters: Each of the counters (
row
,col
,diag1
, anddiag2
) could potentially have as many entries as there are lamps if all lamps are in distinct rows, columns, and diagonals. Therefore, each of these counters also contributesO(L)
to the space complexity. -
Result Array (
ans
): This array has a length equal to the number of queries, which contributesO(Q)
to the space complexity.
Thus, the overall space complexity of the algorithm is O(L + Q)
since space is allocated for storing lamps and the output for the queries.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.