We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Grid Illumination

Difficulty: Hard

Problem Description

There is a 2D grid of size n x n where each cell of this grid has a lamp that is initially turned off. You are given a 2D array of lamp positions, where lamps[i] = [row_i, col_i] indicates that the lamp at grid[row_i][col_i] is turned on. When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal. You are also given another 2D array queries, where queries[j] = [row_j, col_j]. For the j-th query, determine whether grid[row_j][col_j] is illuminated or not. After answering the j-th query, turn off the lamp at grid[row_j][col_j] and its 8 adjacent lamps if they exist. Return an array of integers ans, where ans[j] should be 1 if the cell in the j-th query was illuminated, or 0 if the lamp was not.

Key Insights

  • Each lamp illuminates its cell and all cells in the same row, column, and diagonal.
  • A grid can be very large (up to 10^9), but the number of lamps and queries is limited (up to 20,000).
  • Efficient tracking of illuminated cells and lamp states is crucial due to the large potential grid size.
  • Using hash maps (dictionaries) can help track the number of lamps in each row, column, and diagonal.

Space and Time Complexity

Time Complexity: O(q + l), where q is the number of queries and l is the number of lamps. Space Complexity: O(l), where l is the number of lamps due to the hash maps used for tracking the states.

Solution

To solve this problem, we can use hash maps to keep track of the number of lamps in each row, column, and both diagonals. For each query, we check if any of the corresponding row, column, or diagonals have lamps turned on. If they do, the queried cell is illuminated. After processing the query, we turn off the lamp at the queried position and its adjacent lamps by updating our hash maps accordingly.

  1. Use hash maps to count the number of lamps in each row, column, and both diagonals.
  2. For each query:
    • Check the relevant counts in the hash maps to determine if the queried cell is illuminated.
    • Turn off the lamp at the queried position and its adjacent positions by updating the counts in the hash maps.
  3. Return the results for each query.

Code Solutions

def gridIllumination(n, lamps, queries):
    from collections import defaultdict

    row_count = defaultdict(int)
    col_count = defaultdict(int)
    diag1_count = defaultdict(int)
    diag2_count = defaultdict(int)
    lamp_set = set()

    # Turn on the lamps
    for r, c in lamps:
        row_count[r] += 1
        col_count[c] += 1
        diag1_count[r - c] += 1
        diag2_count[r + c] += 1
        lamp_set.add((r, c))

    ans = []

    # Directions for 8 adjacent lamps
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)]

    for r, c in queries:
        if row_count[r] > 0 or col_count[c] > 0 or diag1_count[r - c] > 0 or diag2_count[r + c] > 0:
            ans.append(1)  # Cell is illuminated
        else:
            ans.append(0)  # Cell is not illuminated

        # Turn off the lamp and its adjacent lamps
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (nr, nc) in lamp_set:
                lamp_set.remove((nr, nc))
                row_count[nr] -= 1
                col_count[nc] -= 1
                diag1_count[nr - nc] -= 1
                diag2_count[nr + nc] -= 1

    return ans
← Back to All Questions