Jobs

Interviews

Discussions

Largest Plus Sign

Medium

Asked by:

34 views

Topics:

ArraysDynamic Programming

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 i^th element of the array mines is defined as mines[i] = [x_i, y_i] where grid[x_i][y_i] == 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 <= x_i, y_i < n
All the pairs (x_i, y_i) are unique.

Try coding it in LeetCode

Largest Plus Sign

Medium

Asked by:

34 views

Topics:

ArraysDynamic Programming

Return the order of the largest axis-aligned plus sign of 1's contained in grid. If there is none, return 0.

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 <= x_i, y_i < n
All the pairs (x_i, y_i) are unique.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid n, and what is the upper bound for n?
What are the data types and ranges for the coordinates in the `mines` array? Can I assume they are valid coordinates within the grid?
If there are no '1's that can form a plus sign (e.g., the grid is filled with only '0's, or all '1's are adjacent to mines), what value should I return?
Are the mine coordinates guaranteed to be unique, or could the same coordinate appear multiple times in the `mines` array?
By 'largest plus sign,' do you mean the maximum *order* of the plus sign, or the maximum number of cells that are part of the plus sign? If the order is k, is the plus sign always centered at a cell (r, c) such that (r, c), (r+i, c), (r-i, c), (r, c+i), and (r, c-i) are all 1s for 0 <= i < k?

Brute Force Solution

Approach

We're looking for the biggest plus sign we can make on a grid, but some spots are blocked. The brute force way is to try making a plus at every possible spot and see how big we can make it.

Here's how the algorithm would work step-by-step:

Go to each empty spot on the grid, one at a time.
Imagine that spot is the center of a plus sign.
Start with a plus sign of size one (just the center spot itself).
See if we can make the plus sign bigger by adding one more spot to each arm of the plus.
If any of those new spots are blocked, we can't make the plus sign bigger from that center.
Keep trying to make the plus sign bigger until we can't anymore because a spot is blocked or we reach the edge of the grid.
Record the size of the biggest plus sign we could make from that center spot.
Do this for every empty spot on the grid.
Finally, find the biggest plus sign size we recorded from all the spots. That's our answer.

Code Implementation

def largest_plus_sign_brute_force(grid_size, mines):
    grid = [[1] * grid_size for _ in range(grid_size)]

    # Mark the mined cells as 0
    for row, col in mines:
        grid[row][col] = 0

    max_order = 0

    for row in range(grid_size):
        for col in range(grid_size):
            if grid[row][col] == 1:
                order = 0
                can_expand = True

                # Increase plus sign size while possible
                while can_expand:
                    order += 1
                    # Check if the plus sign extends beyond grid bounds or hits a mine
                    if (row - order < 0 or row + order >= grid_size or\
                        col - order < 0 or col + order >= grid_size or\
                        grid[row - order][col] == 0 or grid[row + order][col] == 0 or\
                        grid[row][col - order] == 0 or grid[row][col + order] == 0):

                        # Stop expanding if we hit a mine or edge
                        can_expand = False
                        order -= 1

                # Update the maximum order found so far
                max_order = max(max_order, order)

    return max_order

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through each cell of the n x n grid, which takes O(n^2) time. For each cell, it attempts to expand the plus sign. The expansion process, in the worst case, could extend to a length proportional to n in each of the four directions (up, down, left, right). Therefore, the expansion process for a single cell could take O(n) time in the worst case. Combining these, the overall time complexity becomes O(n^2 * n) which simplifies to O(n^3).

Space Complexity

O(1) – The provided algorithm iterates through the grid and calculates the size of the largest plus sign centered at each empty spot. It primarily uses variables to track the current plus sign size and does not create any auxiliary data structures that scale with the input size. Therefore, the space complexity remains constant, independent of the grid's dimensions or the number of blocked cells. Consequently, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The goal is to find the largest 'plus' shape of 1s within a grid, avoiding certain blocked cells. Instead of checking every possible plus shape size and location individually (which would be slow), we calculate the maximum possible 'arm length' extending in each of the four directions from every cell efficiently.

Here's how the algorithm would work step-by-step:

Imagine each cell in the grid could be the center of a 'plus' sign.
For each cell, figure out how far you can extend an 'arm' to the left, right, up, and down, only counting 1s and stopping if you hit a blocked cell.
Store these 'arm lengths' for each direction (left, right, up, down) for every cell.
The size of the biggest 'plus' you can make from a cell is the smallest of its four 'arm lengths' because all arms must be the same length to form a valid plus.
Go through every cell, find the biggest plus size possible from that cell (using the smallest arm length), and keep track of the overall biggest plus size you've found so far.
The biggest plus size you kept track of is your answer.

Code Implementation

def largest_plus_sign(grid_size, mines):
    grid = [[1] * grid_size for _ in range(grid_size)]
    for row, col in mines:
        grid[row][col] = 0

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

    for row_index in range(grid_size):
        for col_index in range(grid_size):
            if grid[row_index][col_index] == 1:
                left[row_index][col_index] = (left[row_index][col_index - 1] + 1
                                            if col_index > 0 else 1)
                up[row_index][col_index] = (up[row_index - 1][col_index] + 1
                                          if row_index > 0 else 1)

    for row_index in range(grid_size - 1, -1, -1):
        for col_index in range(grid_size - 1, -1, -1):
            if grid[row_index][col_index] == 1:
                right[row_index][col_index] = (right[row_index][col_index + 1] + 1
                                             if col_index < grid_size - 1 else 1)
                down[row_index][col_index] = (down[row_index + 1][col_index] + 1
                                            if row_index < grid_size - 1 else 1)

    max_plus_order = 0
    for row_index in range(grid_size):
        for col_index in range(grid_size):
            # Find min of arm lengths to determine plus size
            order = min(left[row_index][col_index],
                        right[row_index][col_index],
                        up[row_index][col_index],
                        down[row_index][col_index])

            # Track the maximum plus size seen so far.
            max_plus_order = max(max_plus_order, order)

    return max_plus_order

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each cell in the n x n grid. For each cell, it calculates the maximum arm lengths in four directions (up, down, left, right). Calculating each arm length takes at most O(n) time in the worst case, but because we precompute these arm lengths for all cells in each direction, the overall computation for determining these lengths across the entire n x n grid takes O(n²) time. Since the smallest arm length for each cell is computed in O(1) and finding the maximum of these minimums is also O(n²), the dominant cost is still O(n²). Therefore, the overall time complexity is O(n²).

Space Complexity

O(N^2) – The solution stores the 'arm lengths' for each direction (left, right, up, down) for every cell in the grid. This requires four separate 2D arrays (left, right, up, down), each with the same dimensions as the input grid. Therefore, the auxiliary space is proportional to 4 * N * N, where N is the number of rows (or columns, assuming a square grid). This simplifies to O(N^2).

Edge Cases

Case	How to Handle
N is zero or negative	Return 0 since a plus sign of order 0 doesn't exist and negative size is invalid.
mines is null or empty	Return N (the maximum possible order) since no cells are forbidden.
mines contains out-of-bounds coordinates	Filter out invalid coordinates before processing or handle them gracefully by treating them as forbidden cells without throwing an exception.
N is 1 and mines is empty	Return 1, as the entire grid consists of a single valid cell.
All cells are in mines	Return 0 since no valid plus sign of order 1 or greater can be formed.
Large N value that may cause integer overflow when calculating distances or dimensions	Use appropriate data types (e.g., long) to prevent integer overflow during calculations of distances or dimensions.
mines contains duplicate coordinates	The solution will overwrite duplicated mines; this behavior should be consistent with the problem definition (if duplicates are present treat as a single mine).
The mines configuration results in a single plus sign in the entire board, centered exactly in the middle	The algorithm should correctly identify and return the order of this single, isolated plus sign.

N is zero or negative

How to Handle:

Return 0 since a plus sign of order 0 doesn't exist and negative size is invalid.

mines is null or empty

How to Handle:

Return N (the maximum possible order) since no cells are forbidden.

mines contains out-of-bounds coordinates

How to Handle:

Filter out invalid coordinates before processing or handle them gracefully by treating them as forbidden cells without throwing an exception.

N is 1 and mines is empty

How to Handle:

Return 1, as the entire grid consists of a single valid cell.

All cells are in mines

How to Handle:

Return 0 since no valid plus sign of order 1 or greater can be formed.

Large N value that may cause integer overflow when calculating distances or dimensions

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during calculations of distances or dimensions.

mines contains duplicate coordinates

How to Handle:

The solution will overwrite duplicated mines; this behavior should be consistent with the problem definition (if duplicates are present treat as a single mine).

The mines configuration results in a single plus sign in the entire board, centered exactly in the middle

How to Handle:

The algorithm should correctly identify and return the order of this single, isolated plus sign.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid n, and what is the upper bound for n?
What are the data types and ranges for the coordinates in the `mines` array? Can I assume they are valid coordinates within the grid?
If there are no '1's that can form a plus sign (e.g., the grid is filled with only '0's, or all '1's are adjacent to mines), what value should I return?
Are the mine coordinates guaranteed to be unique, or could the same coordinate appear multiple times in the `mines` array?
By 'largest plus sign,' do you mean the maximum *order* of the plus sign, or the maximum number of cells that are part of the plus sign? If the order is k, is the plus sign always centered at a cell (r, c) such that (r, c), (r+i, c), (r-i, c), (r, c+i), and (r, c-i) are all 1s for 0 <= i < k?

Brute Force Solution

Approach

We're looking for the biggest plus sign we can make on a grid, but some spots are blocked. The brute force way is to try making a plus at every possible spot and see how big we can make it.

Here's how the algorithm would work step-by-step:

Go to each empty spot on the grid, one at a time.
Imagine that spot is the center of a plus sign.
Start with a plus sign of size one (just the center spot itself).
See if we can make the plus sign bigger by adding one more spot to each arm of the plus.
If any of those new spots are blocked, we can't make the plus sign bigger from that center.
Keep trying to make the plus sign bigger until we can't anymore because a spot is blocked or we reach the edge of the grid.
Record the size of the biggest plus sign we could make from that center spot.
Do this for every empty spot on the grid.
Finally, find the biggest plus sign size we recorded from all the spots. That's our answer.

Code Implementation

def largest_plus_sign_brute_force(grid_size, mines):
    grid = [[1] * grid_size for _ in range(grid_size)]

    # Mark the mined cells as 0
    for row, col in mines:
        grid[row][col] = 0

    max_order = 0

    for row in range(grid_size):
        for col in range(grid_size):
            if grid[row][col] == 1:
                order = 0
                can_expand = True

                # Increase plus sign size while possible
                while can_expand:
                    order += 1
                    # Check if the plus sign extends beyond grid bounds or hits a mine
                    if (row - order < 0 or row + order >= grid_size or\
                        col - order < 0 or col + order >= grid_size or\
                        grid[row - order][col] == 0 or grid[row + order][col] == 0 or\
                        grid[row][col - order] == 0 or grid[row][col + order] == 0):

                        # Stop expanding if we hit a mine or edge
                        can_expand = False
                        order -= 1

                # Update the maximum order found so far
                max_order = max(max_order, order)

    return max_order

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each cell in the grid could be the center of a 'plus' sign.
For each cell, figure out how far you can extend an 'arm' to the left, right, up, and down, only counting 1s and stopping if you hit a blocked cell.
Store these 'arm lengths' for each direction (left, right, up, down) for every cell.
The size of the biggest 'plus' you can make from a cell is the smallest of its four 'arm lengths' because all arms must be the same length to form a valid plus.
Go through every cell, find the biggest plus size possible from that cell (using the smallest arm length), and keep track of the overall biggest plus size you've found so far.
The biggest plus size you kept track of is your answer.

Code Implementation

def largest_plus_sign(grid_size, mines):
    grid = [[1] * grid_size for _ in range(grid_size)]
    for row, col in mines:
        grid[row][col] = 0

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

    for row_index in range(grid_size):
        for col_index in range(grid_size):
            if grid[row_index][col_index] == 1:
                left[row_index][col_index] = (left[row_index][col_index - 1] + 1
                                            if col_index > 0 else 1)
                up[row_index][col_index] = (up[row_index - 1][col_index] + 1
                                          if row_index > 0 else 1)

    for row_index in range(grid_size - 1, -1, -1):
        for col_index in range(grid_size - 1, -1, -1):
            if grid[row_index][col_index] == 1:
                right[row_index][col_index] = (right[row_index][col_index + 1] + 1
                                             if col_index < grid_size - 1 else 1)
                down[row_index][col_index] = (down[row_index + 1][col_index] + 1
                                            if row_index < grid_size - 1 else 1)

    max_plus_order = 0
    for row_index in range(grid_size):
        for col_index in range(grid_size):
            # Find min of arm lengths to determine plus size
            order = min(left[row_index][col_index],
                        right[row_index][col_index],
                        up[row_index][col_index],
                        down[row_index][col_index])

            # Track the maximum plus size seen so far.
            max_plus_order = max(max_plus_order, order)

    return max_plus_order

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
N is zero or negative	Return 0 since a plus sign of order 0 doesn't exist and negative size is invalid.
mines is null or empty	Return N (the maximum possible order) since no cells are forbidden.
mines contains out-of-bounds coordinates	Filter out invalid coordinates before processing or handle them gracefully by treating them as forbidden cells without throwing an exception.
N is 1 and mines is empty	Return 1, as the entire grid consists of a single valid cell.
All cells are in mines	Return 0 since no valid plus sign of order 1 or greater can be formed.
Large N value that may cause integer overflow when calculating distances or dimensions	Use appropriate data types (e.g., long) to prevent integer overflow during calculations of distances or dimensions.
mines contains duplicate coordinates	The solution will overwrite duplicated mines; this behavior should be consistent with the problem definition (if duplicates are present treat as a single mine).
The mines configuration results in a single plus sign in the entire board, centered exactly in the middle	The algorithm should correctly identify and return the order of this single, isolated plus sign.

N is zero or negative

How to Handle:

Return 0 since a plus sign of order 0 doesn't exist and negative size is invalid.

mines is null or empty

How to Handle:

Return N (the maximum possible order) since no cells are forbidden.

mines contains out-of-bounds coordinates

How to Handle:

Filter out invalid coordinates before processing or handle them gracefully by treating them as forbidden cells without throwing an exception.

N is 1 and mines is empty

How to Handle:

Return 1, as the entire grid consists of a single valid cell.

All cells are in mines

How to Handle:

Return 0 since no valid plus sign of order 1 or greater can be formed.

Large N value that may cause integer overflow when calculating distances or dimensions

How to Handle:

Use appropriate data types (e.g., long) to prevent integer overflow during calculations of distances or dimensions.

mines contains duplicate coordinates

How to Handle:

The solution will overwrite duplicated mines; this behavior should be consistent with the problem definition (if duplicates are present treat as a single mine).

The mines configuration results in a single plus sign in the entire board, centered exactly in the middle

How to Handle:

The algorithm should correctly identify and return the order of this single, isolated plus sign.