Introduction

In this blog post, we will explore how to solve the LeetCode problem "1001" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 lamps, where lamps[i] = [rowi, coli] indicates that the lamp at grid[rowi][coli] is turned on. Even if the same lamp is listed more than once, it 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] = [rowj, colj]. For the jth query, determine whether grid[rowj][colj] is illuminated or not. After answering the jth query, turn off the lamp at grid[rowj][colj] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[rowj][colj]. Return an array of integers ans, where ans[j] should be 1 if the cell in the jth query was illuminated, or 0 if the lamp was not. Example 1: Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]] Output: [1,0] Explanation: 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 3: Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]] Output: [1,1,0] 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

Explanation

Here's a breakdown of the approach, followed by the Python code:

• Use Hashmaps for Efficient Lookups: Instead of representing the entire n x n grid (which could be very large), use hashmaps (dictionaries in Python) to store the counts of lamps in each row, column, and diagonal. This allows for constant-time lookups and updates.
• Track Lamp Positions: Use a set to store the exact coordinates of all turned-on lamps. This makes it easy to check if a lamp exists at a specific location before turning it off.

• Illuminate Check and Turn Off: For each query, check if the queried cell is illuminated based on the counts in the hashmaps. If illuminated, turn off the lamp at the queried cell and its adjacent cells, updating the hashmaps and the set of lamp positions.

• Runtime & Storage Complexity: The runtime complexity is O(L + Q), where L is the number of lamps and Q is the number of queries. This is because we iterate through the lamps once and then process each query in constant time on average. The storage complexity is O(L) because we store the lamp positions and the counts in hashmaps, which are proportional to the number of lamps.

Code

    def gridIllumination(n: int, lamps: list[list[int]], queries: list[list[int]]) -> list[int]:
    """
    Determines if grid[rowj][colj] is illuminated for each query and returns an array of integers.
    """

    row_counts = {}
    col_counts = {}
    diag1_counts = {}  # row + col
    diag2_counts = {}  # row - col
    lamp_positions = set()

    # Turn on the lamps and update the counts
    for row, col in lamps:
        if (row, col) in lamp_positions:
            continue  # Avoid double counting

        lamp_positions.add((row, col))

        row_counts[row] = row_counts.get(row, 0) + 1
        col_counts[col] = col_counts.get(col, 0) + 1
        diag1 = row + col
        diag2 = row - col
        diag1_counts[diag1] = diag1_counts.get(diag1, 0) + 1
        diag2_counts[diag2] = diag2_counts.get(diag2, 0) + 1

    ans = []
    # Process the queries
    for row, col in queries:
        illuminated = False
        if row in row_counts and row_counts[row] > 0:
            illuminated = True
        elif col in col_counts and col_counts[col] > 0:
            illuminated = True
        elif row + col in diag1_counts and diag1_counts[row + col] > 0:
            illuminated = True
        elif row - col in diag2_counts and diag2_counts[row - col] > 0:
            illuminated = True

        ans.append(1 if illuminated else 0)

        # Turn off the lamp and its adjacent lamps
        for r in range(row - 1, row + 2):
            for c in range(col - 1, col + 2):
                if 0 <= r < n and 0 <= c < n and (r, c) in lamp_positions:
                    lamp_positions.remove((r, c))

                    row_counts[r] -= 1
                    if row_counts[r] == 0:
                        del row_counts[r]

                    col_counts[c] -= 1
                    if col_counts[c] == 0:
                        del col_counts[c]

                    diag1 = r + c
                    diag1_counts[diag1] -= 1
                    if diag1_counts[diag1] == 0:
                        del diag1_counts[diag1]

                    diag2 = r - c
                    diag2_counts[diag2] -= 1
                    if diag2_counts[diag2] == 0:
                        del diag2_counts[diag2]

    return ans