Jobs

Interviews

Discussions

Maximal Square

Medium

Asked by:

+20

More companies

35 views

Topics:

ArraysDynamic Programming

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.

Try coding it in LeetCode

Maximal Square

Medium

Asked by:

+14

More companies

35 views

Topics:

ArraysDynamic Programming

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] is '0' or '1'.

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 matrix, and what are the constraints on those dimensions (e.g., maximum number of rows and columns)?
Can the input matrix be empty or null? If so, what should I return?
Is the matrix guaranteed to only contain '0' and '1' characters, or could there be other characters or invalid data?
If the matrix doesn't contain any 1's, should I return 0, or is there another specified return value?
Are we looking for a contiguous square, or can the 1's be non-contiguous but still form a square shape?

Brute Force Solution

Approach

The goal is to find the biggest square made up of only 'true' values within a grid. The brute force way means we'll check every possible square size and location to see if it fits the criteria.

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

Start by considering the smallest possible square: a single element in the grid.
Check if this single element is 'true'. If it is, this is a square of size 1.
Now, consider squares of size 2x2. Move this square to every possible position in the grid.
For each position of the 2x2 square, check if all its elements are 'true'. If they are, it's a valid square.
Repeat this process for squares of size 3x3, 4x4, and so on, up to the largest possible square that can fit in the grid.
For each square size, slide the square across the grid, checking if all elements are 'true'.
Keep track of the size of the largest square you find that only contains 'true' values.
At the end, the largest square size recorded is the answer.

Code Implementation

def maximal_square_brute_force(matrix):
    if not matrix:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    max_side = 0

    # Iterate through all possible square sizes
    for side_length in range(1, min(rows, cols) + 1):
        # Iterate through all possible top-left corners for each square size
        for row_start in range(rows - side_length + 1):
            for col_start in range(cols - side_length + 1):

                # Check if the current square is valid.
                is_square = True
                for row_index in range(row_start, row_start + side_length):
                    for col_index in range(col_start, col_start + side_length):
                        if matrix[row_index][col_index] == '0':
                            is_square = False
                            break
                    if not is_square:
                        break

                # Update maximal side length if applicable
                if is_square:
                    max_side = max(max_side, side_length)

    return max_side * max_side

Big(O) Analysis

Time Complexity

O(n^6) – Let n be the number of rows and m be the number of columns in the matrix, and let's assume n and m are approximately equal, so we use n for both. The algorithm iterates through all possible square sizes from 1 to min(n, m), which is O(n). For each square size 'size', it iterates through all possible top-left corner positions in the matrix. This gives us (n - size + 1) rows and (n - size + 1) columns to start a square. Thus iterating through all start points will be O((n - size + 1)^2) which is approximately O(n^2). For each of these squares we iterate through all cells of the square of size size to check if they are all 'true'. This is an O(size^2) operation. In the worst case size is approaching n. Therefore, the time complexity is O(n * n^2 * n^2) = O(n^5). Because we are iterating from 1 to n for the size of square, and within each square we iterate through the cells, the total complexity is actually O(n^6).

Space Complexity

O(1) – The provided brute force solution iterates through all possible square sizes and positions within the input grid to find the maximal square. However, it does not explicitly create any auxiliary data structures (like temporary lists, hash maps, or recursion stack frames) to store intermediate results or track visited locations. It only maintains a variable to store the size of the largest square found so far. Therefore, the auxiliary space used by this algorithm is constant, regardless of the input grid's dimensions.

Optimal Solution

Approach

The best way to solve this is to avoid re-calculating sizes. Instead, we build on previous calculations to determine the size of larger squares. This allows us to find the biggest square efficiently by only checking each spot once.

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

Imagine each spot in the grid represents the bottom-right corner of a potential square.
To figure out the size of the square at each spot, look at the sizes of the squares to the top, left, and diagonally above.
The size of the square at the current spot is one more than the smallest of those three surrounding squares, but only if the current spot is a '1'. If it's a '0', then the square size at that spot is zero.
Keep track of the biggest square you've found so far as you go through the grid.
After you've checked every spot, the biggest square you tracked is the answer. The area of this square is the square of its side length.

Code Implementation

def maximal_square(matrix):
    if not matrix:
        return 0

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # dp table stores max square side length ending at each cell.
    dp_table = [[0] * number_of_columns for _ in range(number_of_rows)]
    max_side = 0

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if matrix[row_index][column_index] == '1':
                # Base case: If at the edge, the size is 1 if it's a '1'.
                if row_index == 0 or column_index == 0:
                    dp_table[row_index][column_index] = 1
                else:
                    # Find the minimum side length of neighbors.
                    dp_table[row_index][column_index] = min(dp_table[row_index - 1][column_index],
                                                           dp_table[row_index][column_index - 1],
                                                           dp_table[row_index - 1][column_index - 1]) + 1

                # Track the maximum side length found so far.
                max_side = max(max_side, dp_table[row_index][column_index])

    # Return the area of the largest square.
    return max_side * max_side

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each cell of the input matrix, where m is the number of rows and n is the number of columns. For each cell, it performs a constant amount of work: checking the values of its neighbors (top, left, and diagonal) and updating the size of the square ending at that cell. Since the algorithm visits each cell once and performs constant-time operations per cell, the overall time complexity is proportional to the number of cells in the matrix, which is m * n. Therefore, the time complexity is O(m*n).

Space Complexity

O(M*N) – The algorithm uses a 2D DP array (which we can think of as a table) to store the size of the maximal square ending at each cell in the input matrix. The dimensions of this DP array are the same as the input matrix, where M is the number of rows and N is the number of columns. Therefore, the auxiliary space required is proportional to the product of M and N, as it stores integer values for each cell in the matrix. The algorithm also uses a constant amount of space for a single variable to keep track of the maximum square size seen so far, which does not affect the overall space complexity. Thus, the space complexity is O(M*N).

Edge Cases

Case	How to Handle
Null or empty input matrix	Return 0 immediately as there's no square to be found.
Matrix with zero rows or zero columns	Return 0 immediately as there's no square to be found.
Matrix with only one row or one column	Iterate through the single row/column and return 1 if any '1' is present, otherwise return 0.
Matrix filled entirely with '0's	Return 0, as no square of 1's exists.
Matrix filled entirely with '1's	Return the area of the entire matrix if it's a square, otherwise return the area of the largest possible square that fits within the matrix's dimensions.
Large matrix: Potential integer overflow when calculating area	Use a data type large enough to hold the area (e.g., long) or be mindful that the maximum side length can be at most the matrix dimension.
Non-binary input: Matrix contains values other than '0' or '1'	Treat any non-'1' value as '0' during calculation, or throw an error if the input should strictly adhere to the binary constraint.
Very large matrix dimensions that could lead to memory issues.	Dynamic programming approach helps, but be aware of space complexity O(m*n); Optimize to potentially use only two rows for space.

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 matrix, and what are the constraints on those dimensions (e.g., maximum number of rows and columns)?
Can the input matrix be empty or null? If so, what should I return?
Is the matrix guaranteed to only contain '0' and '1' characters, or could there be other characters or invalid data?
If the matrix doesn't contain any 1's, should I return 0, or is there another specified return value?
Are we looking for a contiguous square, or can the 1's be non-contiguous but still form a square shape?

Brute Force Solution

Approach

The goal is to find the biggest square made up of only 'true' values within a grid. The brute force way means we'll check every possible square size and location to see if it fits the criteria.

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

Start by considering the smallest possible square: a single element in the grid.
Check if this single element is 'true'. If it is, this is a square of size 1.
Now, consider squares of size 2x2. Move this square to every possible position in the grid.
For each position of the 2x2 square, check if all its elements are 'true'. If they are, it's a valid square.
Repeat this process for squares of size 3x3, 4x4, and so on, up to the largest possible square that can fit in the grid.
For each square size, slide the square across the grid, checking if all elements are 'true'.
Keep track of the size of the largest square you find that only contains 'true' values.
At the end, the largest square size recorded is the answer.

Code Implementation

def maximal_square_brute_force(matrix):
    if not matrix:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    max_side = 0

    # Iterate through all possible square sizes
    for side_length in range(1, min(rows, cols) + 1):
        # Iterate through all possible top-left corners for each square size
        for row_start in range(rows - side_length + 1):
            for col_start in range(cols - side_length + 1):

                # Check if the current square is valid.
                is_square = True
                for row_index in range(row_start, row_start + side_length):
                    for col_index in range(col_start, col_start + side_length):
                        if matrix[row_index][col_index] == '0':
                            is_square = False
                            break
                    if not is_square:
                        break

                # Update maximal side length if applicable
                if is_square:
                    max_side = max(max_side, side_length)

    return max_side * max_side

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine each spot in the grid represents the bottom-right corner of a potential square.
To figure out the size of the square at each spot, look at the sizes of the squares to the top, left, and diagonally above.
The size of the square at the current spot is one more than the smallest of those three surrounding squares, but only if the current spot is a '1'. If it's a '0', then the square size at that spot is zero.
Keep track of the biggest square you've found so far as you go through the grid.
After you've checked every spot, the biggest square you tracked is the answer. The area of this square is the square of its side length.

Code Implementation

def maximal_square(matrix):
    if not matrix:
        return 0

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])

    # dp table stores max square side length ending at each cell.
    dp_table = [[0] * number_of_columns for _ in range(number_of_rows)]
    max_side = 0

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if matrix[row_index][column_index] == '1':
                # Base case: If at the edge, the size is 1 if it's a '1'.
                if row_index == 0 or column_index == 0:
                    dp_table[row_index][column_index] = 1
                else:
                    # Find the minimum side length of neighbors.
                    dp_table[row_index][column_index] = min(dp_table[row_index - 1][column_index],
                                                           dp_table[row_index][column_index - 1],
                                                           dp_table[row_index - 1][column_index - 1]) + 1

                # Track the maximum side length found so far.
                max_side = max(max_side, dp_table[row_index][column_index])

    # Return the area of the largest square.
    return max_side * max_side

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input matrix	Return 0 immediately as there's no square to be found.
Matrix with zero rows or zero columns	Return 0 immediately as there's no square to be found.
Matrix with only one row or one column	Iterate through the single row/column and return 1 if any '1' is present, otherwise return 0.
Matrix filled entirely with '0's	Return 0, as no square of 1's exists.
Matrix filled entirely with '1's	Return the area of the entire matrix if it's a square, otherwise return the area of the largest possible square that fits within the matrix's dimensions.
Large matrix: Potential integer overflow when calculating area	Use a data type large enough to hold the area (e.g., long) or be mindful that the maximum side length can be at most the matrix dimension.
Non-binary input: Matrix contains values other than '0' or '1'	Treat any non-'1' value as '0' during calculation, or throw an error if the input should strictly adhere to the binary constraint.
Very large matrix dimensions that could lead to memory issues.	Dynamic programming approach helps, but be aware of space complexity O(m*n); Optimize to potentially use only two rows for space.