1001. Grid Illumination

HardArrayHash Table
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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:

  1. 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, and diag2 are used to track the count of lamps that are currently illuminating each row, column, and the two sets of diagonals, respectively.

  2. 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.

  3. 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], or diag2[i + j] counter is greater than 0, it means the cell is illuminated. In this case, set ans[k] (where k is the index for the current query) to 1.

  4. 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 set s), we remove the lamp from the set s and decrement the counts in the corresponding row, col, diag1, and diag2.

  5. Output:

    • Return the answer list ans, which contains the results of each query represented as 1 or 0.

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.

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

Which of these properties could exist for a graph but not a tree?

Example 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:

  1. Is the cell at (0, 1) illuminated?
  2. 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 becomes 1 because of lamp 1 at (0, 0)
    • col[0] also becomes 1 because of lamp 1 at (0, 0)
    • diag1[0] (calculated as 0 - 0) becomes 1
    • diag2[0] (calculated as 0 + 0) becomes 1
    • 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]. Since row[0] is 1, the cell (0, 1) is illuminated.
    • Set ans[0] to 1.
  • For Query 2 at (1, 1): Check row[1], col[1], diag1[0], diag2[2]. Since row[1], col[1], and both diag counters are 1, the cell (1, 1) is illuminated.
    • Set ans[1] to 1.

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) from s.
    • Decrement row[0], col[0], diag1[0], and diag2[0].
  • 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) from s.
    • Decrement row[1], col[1], and both diagonal counters for both lamps.

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
Not Sure What to Study? Take the 2-min Quiz：

What are the most two important steps in writing a depth first search function? (Select 2)

Time and Space Complexity

Time Complexity

The provided code has several main parts that contribute to the overall time complexity:

  1. Initialization of Sets and Counters: The creation of the initial set s and the counters for row, col, diag1, and diag2. This part has a time complexity of O(L), where L is the number of lamps, since each lamp is visited once.

  2. Updating Counters: For each lamp, the code updates the row, col, diag1, and diag2 counters. Since there are L lamps, and each update operation is O(1), this is also O(L) in total.

  3. 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 are Q queries, and each query may result in updates to a fixed number of lamp positions (at most 9), this part has a time complexity of O(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.

  1. Storage for lamp positions (s): Space complexity is O(L) because we store each lamp's position at most once in the set.

  2. Counters: Each of the counters (row, col, diag1, and diag2) 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 contributes O(L) to the space complexity.

  3. Result Array (ans): This array has a length equal to the number of queries, which contributes O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used to implement priority queue?

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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 to Algo Cheat Sheet

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫