Jobs

Interviews

Discussions

Largest 1-Bordered Square

Medium

Samsung

0 views

Topics:

ArraysDynamic Programming

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

Largest 1-Bordered Square

Medium

Samsung

0 views

Topics:

ArraysDynamic Programming

Given a 2D grid of 0s and 1s, return the number of elements in the largest square subgrid that has all 1s on its border, or 0 if such a subgrid doesn't exist in the grid.

Example 1:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]]
Output: 9

Example 2:

Input: grid = [[1,1,0,0]]
Output: 1

Constraints:

1 <= grid.length <= 100
1 <= grid[0].length <= 100
grid[i][j] is 0 or 1

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 input matrix, and what is the maximum possible size?
What are the possible values in the matrix; is it strictly 0 or 1, or can it contain other values?
If no 1-bordered square exists, what value should I return?
If there are multiple squares of the same largest size, should I return the size of any one of them, or is there a specific square I should prioritize (e.g., the one with the smallest top-left coordinates)?
Is the input matrix guaranteed to be rectangular (i.e., all rows have the same number of columns) and non-empty?

Brute Force Solution

Approach

The brute force method for finding the largest square completely surrounded by ones involves checking every possible square within the given grid. We start with the biggest possible square and then work our way down, looking at every possible position for that square within the grid.

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

Begin by considering the largest possible square size, which is limited by the smaller dimension of the grid.
Check if a square of that size exists with all its borders made of ones, by examining every possible top-left corner location within the grid for that square size.
If such a square is found, you've found the answer; you can stop.
If not, reduce the square size by one.
Repeat the process of checking all possible top-left corners for the new, smaller square size to see if it satisfies the border requirement.
Keep shrinking the square size and checking possible positions until you find a 1-bordered square.
If you reach a square size of 1 and haven't found a valid square, it means there is no 1-bordered square in the grid.

Code Implementation

def largest_1_bordered_square(grid):
    rows = len(grid)
    columns = len(grid[0])
    max_square_side = min(rows, columns)

    for current_side in range(max_square_side, 0, -1):
        # Iterate through possible top-left corners for each square side
        for row_start in range(rows - current_side + 1):
            for column_start in range(columns - current_side + 1):

                # Check if all borders of the square are ones
                is_valid_square = True
                for column_index in range(column_start, column_start + current_side):
                    if grid[row_start][column_index] == 0:
                        is_valid_square = False
                        break
                if not is_valid_square:
                    continue

                for column_index in range(column_start, column_start + current_side):
                    if grid[row_start + current_side - 1][column_index] == 0:
                        is_valid_square = False
                        break
                if not is_valid_square:
                    continue

                for row_index in range(row_start, row_start + current_side):
                    if grid[row_index][column_start] == 0:
                        is_valid_square = False
                        break
                if not is_valid_square:
                    continue

                for row_index in range(row_start, row_start + current_side):
                    if grid[row_index][column_start + current_side - 1] == 0:
                        is_valid_square = False
                        break

                # If the square is valid, return the area
                if is_valid_square:
                    return current_side * current_side

    # If no 1-bordered square is found, return 0
    return 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(min(M, N)^3 * M * N) – Let M and N be the dimensions of the input grid. The algorithm iterates from the largest possible square size, min(M, N), down to 1. For each square size `side`, it iterates through all possible top-left corner positions in the grid, which is O((M - side + 1) * (N - side + 1)), approximated as O(M * N). For each such position, it checks if the square formed by that position has all 1s on its border, which takes O(side) for each of the 4 sides or O(side) total. Because the size changes with an outer loop we must include that to arrive at O(min(M, N)^3 * M * N).

Space Complexity

O(1) – The brute force method described checks squares of decreasing sizes within the input grid. It doesn't create any auxiliary data structures like temporary arrays, lists, or hashmaps to store intermediate results or visited locations. The algorithm primarily uses a few variables to track the current square's top-left corner coordinates and its size. These variables occupy a constant amount of space, independent of the input grid's dimensions, thus the space complexity is O(1).

Optimal Solution

Approach

The most efficient approach involves creating helper tables that store information about continuous sequences of ones. We can use these tables to quickly check if a square of a certain size exists with all ones on its border, avoiding unnecessary checks.

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

Create two new tables that store the length of consecutive ones extending to the left and upwards from each position in the original table.
Start checking for the largest possible square, beginning with the maximum possible side length. Reduce the side length if a valid square is not found.
For each possible square size, check every possible top-left corner in the original table.
To check if a square exists, use the pre-calculated helper tables to verify that the top, left, right and bottom borders of that square consist of ones and are of the correct size.
If a valid square is found, return its side length immediately since we are searching for the largest square first.
If no valid square is found after checking all sizes and positions, return 0, indicating that no 1-bordered square exists.

Code Implementation

def largest_1_bordered_square(grid): 
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0
    
    left_table = [[0] * cols for _ in range(rows)]
    up_table = [[0] * cols for _ in range(rows)]
    
    for row_index in range(rows): 
        for col_index in range(cols): 
            if grid[row_index][col_index] == 1:
                left_table[row_index][col_index] = (left_table[row_index][col_index - 1] if col_index > 0 else 0) + 1
                up_table[row_index][col_index] = (up_table[row_index - 1][col_index] if row_index > 0 else 0) + 1

    max_side = min(rows, cols)
    
    for side_length in range(max_side, 0, -1): 
        for row_index in range(rows - side_length + 1): 
            for col_index in range(cols - side_length + 1): 
                # Check if all borders are 1s of the correct length.
                if left_table[row_index][col_index + side_length - 1] >= side_length and \
                   up_table[row_index + side_length - 1][col_index] >= side_length and \
                   left_table[row_index + side_length - 1][col_index + side_length - 1] >= side_length and \
                   up_table[row_index][col_index] >= side_length:

                    # We found the largest, return immediately.
                    return side_length

    # No square found.
    return 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible square side lengths, potentially from n down to 1. For each side length, it iterates through all possible top-left corners of the square within the n x n grid. For each potential square, it checks the borders to confirm they contain ones. The border check takes O(1) because it uses precomputed tables. Thus, we have approximately n (for side length) * n^2 (for top-left corner) * O(1) (border check) operations, resulting in a time complexity of O(n^3).

Space Complexity

O(N) – The solution creates two auxiliary tables (left and up) to store the lengths of consecutive ones, where N is the total number of cells in the input grid (rows * cols). The size of each of these tables is identical to the input grid's size, i.e., rows * cols. Therefore, the space required for these tables is directly proportional to the size of the input grid, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 if the input matrix is null or has zero rows or columns, as no square can exist.
Matrix with only one row or one column	Iterate through the single row/column to find the largest '1' and return 1 if found, otherwise 0.
Matrix filled entirely with zeros	Return 0, as no 1-bordered square can be formed.
Matrix filled entirely with ones	Return the minimum of the number of rows and columns since that's the maximum square size possible.
Rectangular matrix (number of rows != number of columns)	The solution should correctly handle rectangular matrices by considering the minimum dimension when determining the maximum possible square size.
Large matrix exceeding memory constraints	The solution should use a bottom-up dynamic programming approach that has optimal space complexity.
Matrix with rows of varying lengths	The solution must first validate that each row has the same length before proceeding, returning an error or default value (like 0) if not.
Integer overflow when calculating side length	Ensure calculations involving side lengths are done using `long` or a similar type to avoid overflow when dealing with maximum dimensions.

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 input matrix, and what is the maximum possible size?
What are the possible values in the matrix; is it strictly 0 or 1, or can it contain other values?
If no 1-bordered square exists, what value should I return?
If there are multiple squares of the same largest size, should I return the size of any one of them, or is there a specific square I should prioritize (e.g., the one with the smallest top-left coordinates)?
Is the input matrix guaranteed to be rectangular (i.e., all rows have the same number of columns) and non-empty?

Brute Force Solution

Approach

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

Begin by considering the largest possible square size, which is limited by the smaller dimension of the grid.
Check if a square of that size exists with all its borders made of ones, by examining every possible top-left corner location within the grid for that square size.
If such a square is found, you've found the answer; you can stop.
If not, reduce the square size by one.
Repeat the process of checking all possible top-left corners for the new, smaller square size to see if it satisfies the border requirement.
Keep shrinking the square size and checking possible positions until you find a 1-bordered square.
If you reach a square size of 1 and haven't found a valid square, it means there is no 1-bordered square in the grid.

Code Implementation

def largest_1_bordered_square(grid):
    rows = len(grid)
    columns = len(grid[0])
    max_square_side = min(rows, columns)

    for current_side in range(max_square_side, 0, -1):
        # Iterate through possible top-left corners for each square side
        for row_start in range(rows - current_side + 1):
            for column_start in range(columns - current_side + 1):

                # Check if all borders of the square are ones
                is_valid_square = True
                for column_index in range(column_start, column_start + current_side):
                    if grid[row_start][column_index] == 0:
                        is_valid_square = False
                        break
                if not is_valid_square:
                    continue

                for column_index in range(column_start, column_start + current_side):
                    if grid[row_start + current_side - 1][column_index] == 0:
                        is_valid_square = False
                        break
                if not is_valid_square:
                    continue

                for row_index in range(row_start, row_start + current_side):
                    if grid[row_index][column_start] == 0:
                        is_valid_square = False
                        break
                if not is_valid_square:
                    continue

                for row_index in range(row_start, row_start + current_side):
                    if grid[row_index][column_start + current_side - 1] == 0:
                        is_valid_square = False
                        break

                # If the square is valid, return the area
                if is_valid_square:
                    return current_side * current_side

    # If no 1-bordered square is found, return 0
    return 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Create two new tables that store the length of consecutive ones extending to the left and upwards from each position in the original table.
Start checking for the largest possible square, beginning with the maximum possible side length. Reduce the side length if a valid square is not found.
For each possible square size, check every possible top-left corner in the original table.
To check if a square exists, use the pre-calculated helper tables to verify that the top, left, right and bottom borders of that square consist of ones and are of the correct size.
If a valid square is found, return its side length immediately since we are searching for the largest square first.
If no valid square is found after checking all sizes and positions, return 0, indicating that no 1-bordered square exists.

Code Implementation

def largest_1_bordered_square(grid): 
    rows = len(grid)
    cols = len(grid[0]) if rows > 0 else 0
    
    left_table = [[0] * cols for _ in range(rows)]
    up_table = [[0] * cols for _ in range(rows)]
    
    for row_index in range(rows): 
        for col_index in range(cols): 
            if grid[row_index][col_index] == 1:
                left_table[row_index][col_index] = (left_table[row_index][col_index - 1] if col_index > 0 else 0) + 1
                up_table[row_index][col_index] = (up_table[row_index - 1][col_index] if row_index > 0 else 0) + 1

    max_side = min(rows, cols)
    
    for side_length in range(max_side, 0, -1): 
        for row_index in range(rows - side_length + 1): 
            for col_index in range(cols - side_length + 1): 
                # Check if all borders are 1s of the correct length.
                if left_table[row_index][col_index + side_length - 1] >= side_length and \
                   up_table[row_index + side_length - 1][col_index] >= side_length and \
                   left_table[row_index + side_length - 1][col_index + side_length - 1] >= side_length and \
                   up_table[row_index][col_index] >= side_length:

                    # We found the largest, return immediately.
                    return side_length

    # No square found.
    return 0

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 if the input matrix is null or has zero rows or columns, as no square can exist.
Matrix with only one row or one column	Iterate through the single row/column to find the largest '1' and return 1 if found, otherwise 0.
Matrix filled entirely with zeros	Return 0, as no 1-bordered square can be formed.
Matrix filled entirely with ones	Return the minimum of the number of rows and columns since that's the maximum square size possible.
Rectangular matrix (number of rows != number of columns)	The solution should correctly handle rectangular matrices by considering the minimum dimension when determining the maximum possible square size.
Large matrix exceeding memory constraints	The solution should use a bottom-up dynamic programming approach that has optimal space complexity.
Matrix with rows of varying lengths	The solution must first validate that each row has the same length before proceeding, returning an error or default value (like 0) if not.
Integer overflow when calculating side length	Ensure calculations involving side lengths are done using `long` or a similar type to avoid overflow when dealing with maximum dimensions.