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

Largest Plus Sign

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem requires us to find the largest plus sign made up of 1's in a binary grid.
  • A plus sign of order k consists of a center and four arms each of length k-1.
  • We can use dynamic programming to calculate the maximum arm length in each direction (up, down, left, right) for each cell.
  • Cells containing 0's (mines) cannot be part of any plus sign.

Space and Time Complexity

Time Complexity: O(n^2) – We traverse the grid multiple times to calculate arm lengths. Space Complexity: O(n^2) – We use additional space to store arm lengths for each direction.

Solution

To solve this problem, we will utilize a dynamic programming approach. We will create four matrices to store the maximum arm lengths extending in each of the four directions (up, down, left, right).

  1. Initialize a 2D list grid of size n x n with all values set to 1.
  2. Set the cells specified in the mines array to 0.
  3. Create four matrices up, down, left, and right to store the lengths of arms:
    • Traverse the grid to calculate the maximum lengths of arms in the up and left directions.
    • Traverse the grid in reverse order to calculate the maximum lengths in the down and right directions.
  4. For each cell, the order of the plus sign can be determined by taking the minimum of the four arm lengths + 1.
  5. Return the maximum order found.

Code Solutions

def largestPlusSign(n, mines):
    # Create a grid initialized with 1's
    grid = [[1] * n for _ in range(n)]
    
    # Mark the mines in the grid
    for x, y in mines:
        grid[x][y] = 0

    # Initialize the four direction arrays
    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)]

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

    # Fill the down and right matrices
    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] + 1) if i < n-1 else 1
                right[i][j] = (right[i][j+1] + 1) if j < n-1 else 1

    # Calculate the largest plus sign order
    max_order = 0
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                order = min(up[i][j], down[i][j], left[i][j], right[i][j])
                max_order = max(max_order, order)

    return max_order
← Back to All Questions