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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Largest Plus Sign

Number: 769

Difficulty: Medium

Paid? No

Companies: Microsoft, Intuit, Meta

Problem Description

Given an n x n grid initialized with 1’s, some cells are set to 0 based on the positions provided in mines. An axis-aligned plus sign of order k is defined by a center cell with value 1 and four arms (up, down, left, right) each of length k - 1 composed entirely of 1’s. The task is to compute the order of the largest plus sign that can be found in the grid. If no valid plus sign exists, return 0.

Key Insights

  • Convert the list of mines into a set for O(1) lookup when processing the grid.
  • Use dynamic programming to compute the number of consecutive 1's in each direction (left, right, up, down) for every cell.
  • The order of the plus sign centered at a given cell is determined by the minimum count among the four directions.
  • The final answer is the maximum order found among all cells.
  • Since multiple passes over the grid are needed (one for each direction), the overall complexity remains efficient for the given constraints.

Space and Time Complexity

Time Complexity: O(n^2) as we traverse the grid a constant number of times. Space Complexity: O(n^2) for storing the DP values for each cell.

Solution

We first initialize a grid using the value n for each cell (indicating the maximum possible continuous 1's) and then mark the mines (set to 0). We perform four passes over the grid:

  1. Left to right: Count consecutive 1's and store the minimum of the current value.
  2. Right to left: Repeat the process.
  3. Top to bottom: Update counts for upward arm.
  4. Bottom to top: Update counts for downward arm.

At each cell, the value (after all passes) represents the maximum order of a plus sign that can have its center at that cell. The answer is the maximum value in the grid.

Code Solutions

def largestPlusSign(n, mines):
    # Create a set for fast lookup of mine positions
    mines_set = { (x, y) for x, y in mines }
    # Initialize DP grid with default counts equal to n
    dp = [[n] * n for _ in range(n)]
    
    # Left to right: count consecutive ones in the row
    for i in range(n):
        count = 0
        for j in range(n):
            count = 0 if (i, j) in mines_set else count + 1
            dp[i][j] = min(dp[i][j], count)
    
    # Right to left: count consecutive ones in the row from right
    for i in range(n):
        count = 0
        for j in range(n-1, -1, -1):
            count = 0 if (i, j) in mines_set else count + 1
            dp[i][j] = min(dp[i][j], count)
    
    # Top to bottom: count consecutive ones in the column
    for j in range(n):
        count = 0
        for i in range(n):
            count = 0 if (i, j) in mines_set else count + 1
            dp[i][j] = min(dp[i][j], count)
    
    # Bottom to top: count consecutive ones in the column from bottom
    for j in range(n):
        count = 0
        for i in range(n-1, -1, -1):
            count = 0 if (i, j) in mines_set else count + 1
            dp[i][j] = min(dp[i][j], count)
    
    # Find the maximum order across all cells
    max_order = 0
    for i in range(n):
        for j in range(n):
            max_order = max(max_order, dp[i][j])
    return max_order

# Example usage:
print(largestPlusSign(5, [[4,2]]))  # Output: 2
← Back to All Questions