Introduction

In this blog post, we will explore how to solve the LeetCode problem "764" 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

You are given an integer n. You have an n x n binary grid grid with all values initially 1's except for some indices given in the array mines. The ith element of the array mines is defined as mines[i] = [xi, yi] where grid[xi][yi] == 0. Return the order of the largest axis-aligned plus sign of 1's contained in grid. If there is none, return 0. An axis-aligned plus sign of 1's of order k has some center grid[r][c] == 1 along with four arms of length k - 1 going up, down, left, and right, and made of 1's. Note that there could be 0's or 1's beyond the arms of the plus sign, only the relevant area of the plus sign is checked for 1's. Example 1: Input: n = 5, mines = [[4,2]] Output: 2 Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown. Example 2: Input: n = 1, mines = [[0,0]] Output: 0 Explanation: There is no plus sign, so return 0. Constraints: 1 <= n <= 500 1 <= mines.length <= 5000 0 <= xi, yi < n All the pairs (xi, yi) are unique.

Explanation

• Grid Initialization and Zeroing: Initialize an n x n grid with all 1s. Then, iterate through the mines array and set the corresponding grid cells to 0.
  • Dynamic Programming for Arm Lengths: Use dynamic programming to compute the maximum length of consecutive 1s extending in each of the four directions (up, down, left, right) from each cell. This involves creating four auxiliary grids to store these lengths.
  • Finding the Maximum Order: Iterate through the grid, and for each cell, find the minimum of the four arm lengths calculated in the previous step. This minimum value represents the order of the largest plus sign centered at that cell. Track and return the maximum order found across all cells.

• Runtime Complexity: O(n²)
• Storage Complexity: O(n²)

Code

    def orderOfLargestPlusSign(n: int, mines: list[list[int]]) -> int:
    """
    Finds the order of the largest axis-aligned plus sign of 1's contained in grid.

    Args:
        n: The size of the grid.
        mines: A list of coordinates that are 0.

    Returns:
        The order of the largest plus sign.
    """

    grid = [[1] * n for _ in range(n)]
    for x, y in mines:
        grid[x][y] = 0

    up = [[0] * n for _ in range(n)]
    down = [[0] * n for _ in range(n)]
    left = [[0] * n for _ in range(n)]
    right = [[0] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                up[i][j] = (up[i - 1][j] if i > 0 else 0) + 1
                left[i][j] = (left[i][j - 1] if j > 0 else 0) + 1

    for i in range(n - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if grid[i][j] == 1:
                down[i][j] = (down[i + 1][j] if i < n - 1 else 0) + 1
                right[i][j] = (right[i][j + 1] if j < n - 1 else 0) + 1

    max_order = 0
    for i in range(n):
        for j in range(n):
            max_order = max(max_order, min(up[i][j], down[i][j], left[i][j], right[i][j]))

    return max_order