Jobs

Interviews

Discussions

Maximal Rectangle

Hard

Google

3 views

Topics:

ArraysDynamic Programming

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example:

matrix = [["1","0","1","0","0"],
            ["1","0","1","1","1"],
            ["1","1","1","1","1"],
            ["1","0","0","1","0"]]

In this case, the function should return 6 because the largest rectangle containing only 1's has an area of 6 (as shown in the example in the original prompt).

As another example:

matrix = [["0"]]

In this case, the function should return 0.

Write an efficient algorithm to solve this problem.

Maximal Rectangle

Hard

Google

3 views

Topics:

ArraysDynamic Programming

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

For example:

matrix = [["1","0","1","0","0"],
            ["1","0","1","1","1"],
            ["1","1","1","1","1"],
            ["1","0","0","1","0"]]

In this case, the function should return 6 because the largest rectangle containing only 1's has an area of 6 (as shown in the example in the original prompt).

As another example:

matrix = [["0"]]

In this case, the function should return 0.

Write an efficient algorithm to solve this problem.

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 size of each dimension? What is the data type of the matrix elements (e.g., 0 or 1)?
Is the input matrix guaranteed to be rectangular (i.e., all rows have the same length)?
What should be returned if the input matrix is empty or null?
If there are multiple maximal rectangles with the same area, should I return any one of them or is there a specific criteria for selecting one?
Are there any memory constraints I should be aware of, given the potential size of the matrix?

Brute Force Solution

Approach

The maximal rectangle problem asks for the biggest rectangular area we can find within a grid filled with ones and zeros. The brute force method involves checking every possible rectangle we can make and figuring out if it's valid.

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

Think about choosing two corners to define a rectangle.
Start by picking any possible top-left corner in the grid.
Then, for that chosen corner, try every possible bottom-right corner that's below and to the right of the top-left corner.
For each pair of corners, check if the rectangle they define is completely filled with ones. If even one zero is inside, that rectangle isn't valid.
If the rectangle is valid (all ones), calculate its area.
Keep track of the largest area you've found so far.
Repeat this process by starting with a new top-left corner and checking all possible bottom-right corners for it.
Continue until you've considered every possible top-left corner in the entire grid.
At the end, the largest area you recorded is the maximal rectangle.

Code Implementation

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

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

    for top_row in range(rows):
        for left_col in range(cols):
            # Iterate through all possible bottom-right corners for the chosen top-left
            for bottom_row in range(top_row, rows):
                for right_col in range(left_col, cols):
                    is_valid_rectangle = True

                    # Check if the submatrix contains only 1s
                    for row_to_check in range(top_row, bottom_row + 1):
                        for col_to_check in range(left_col, right_col + 1):
                            if matrix[row_to_check][col_to_check] == '0':
                                is_valid_rectangle = False
                                break
                        if not is_valid_rectangle:
                            break

                    # Calculate area only for valid rectangles
                    if is_valid_rectangle:

                        rectangle_width = right_col - left_col + 1
                        rectangle_height = bottom_row - top_row + 1
                        area = rectangle_width * rectangle_height
                        max_area = max(max_area, area)

    return max_area

Big(O) Analysis

Time Complexity

O(m^2 * n^2 * k^2) – Let m be the number of rows and n be the number of columns in the matrix. The algorithm iterates through all possible top-left corners, which is O(m * n). For each top-left corner, it iterates through all possible bottom-right corners, which is also O(m * n) in the worst case. For each pair of corners (defining a rectangle), it checks if all elements within that rectangle are 1s. This check involves iterating through all elements within the rectangle, which takes O(k * k) time in the worst case, where k is the maximum of m and n, since the rectangle's sides can be at most m and n. Therefore, the total time complexity is O(m * n * m * n * k^2) which is O(m^2 * n^2 * k^2).

Space Complexity

O(1) – The provided brute force solution iterates through all possible rectangles by selecting top-left and bottom-right corners. It keeps track of the largest area found so far. These operations require only a few variables (to store corner coordinates, current area, and maximum area) which take constant extra space, irrespective of the dimensions of the input grid, which we can consider of size N (where N is the number of cells in the grid). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The best way to find the biggest rectangle in the grid is to think about building it up row by row. We treat each row as a series of bars and use information from the rows above to figure out how tall the bars can be, then we find the biggest rectangle using these bars.

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

First, go through the grid row by row and transform each cell into a height. The height represents how many consecutive '1's are stacked up above that cell, including itself. If a cell is '0', its height is zero, meaning no bar.
For each row, imagine you have a histogram where the height of each bar is determined by the 'height' value we calculated in the previous step.
To find the largest rectangle in that histogram, look at each bar and figure out how far you can expand it to the left and right until you reach a shorter bar.
The area of the rectangle you can make from that bar (its height multiplied by the width you found in the previous step) is a possible candidate for the largest rectangle.
Keep track of the largest rectangle found so far as you go through all bars in the current row.
Repeat this process for every row of the grid, updating the largest rectangle found overall.

Code Implementation

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

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    heights = [[0] * number_of_columns for _ in range(number_of_rows)]
    max_area = 0

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if matrix[row_index][column_index] == '1':
                # Accumulate heights based on consecutive '1's.
                heights[row_index][column_index] = (heights[row_index - 1][column_index] + 1
                                                     if row_index > 0 else 1)

        # Find the largest rectangle area for the current row.
        max_area = max(max_area, largest_rectangle_area(heights[row_index]))

    return max_area

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    index = 0

    while index < len(heights):
        if not stack or heights[index] > heights[stack[-1]]:
            stack.append(index)
            index += 1
        else:
            # Calculate area when encountering a smaller height
            top = stack.pop()
            area = (heights[top] *
                    (index - stack[-1] - 1 if stack else index))

            max_area = max(max_area, area)

    # Process remaining bars in the stack
    while stack:
        top = stack.pop()
        #Calculate area with the remaining histogram bars
        area = (heights[top] *
                (index - stack[-1] - 1 if stack else index))

        max_area = max(max_area, area)

    return max_area

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each of the 'm' rows of the matrix. For each row of 'n' elements, it calculates the height of the bars. The largest rectangle area within each row (histogram) is determined by iterating through each bar (n) and finding its left and right boundaries which could involve scanning left and right from each bar, up to 'n' operations. Therefore, since the algorithm iterates through 'm' rows and for each row requires O(n) for height calculation and then potentially O(n*n) for the histogram, the overall time complexity is O(m * n). (Technically it is O(m*n*n), but this simplifies to O(m*n) because the histogram area calculation is amortized because it might use a stack in an optimal implementation to calculate the width of each bar).

Space Complexity

O(n) – The algorithm uses an auxiliary data structure to store the heights of the bars for each row. In the worst case, this 'height' array will have the same length as the number of columns in the input matrix. If we denote the number of columns as n, then the auxiliary space required for storing the bar heights will be proportional to n. Therefore, the space complexity is O(n).

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 immediately as there's no rectangle to compute.
Matrix with zero rows or columns	Return 0, as a rectangle requires at least one row and one column.
Matrix with a single row	Treat the row as a histogram and calculate the largest rectangular area in it.
Matrix with a single column	Calculate the maximum consecutive '1's multiplied by the width (which is 1).
Matrix filled entirely with '0's	Return 0, as no rectangle of '1's can be formed.
Matrix filled entirely with '1's	Return the area of the entire matrix (rows * cols).
Integer overflow when calculating area (height * width)	Use long or equivalent data type to store the intermediate area result before comparison.
Large matrix that might cause stack overflow if using recursive histogram area calculation	Implement the histogram area calculation iteratively using a stack to avoid stack overflow.

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 size of each dimension? What is the data type of the matrix elements (e.g., 0 or 1)?
Is the input matrix guaranteed to be rectangular (i.e., all rows have the same length)?
What should be returned if the input matrix is empty or null?
If there are multiple maximal rectangles with the same area, should I return any one of them or is there a specific criteria for selecting one?
Are there any memory constraints I should be aware of, given the potential size of the matrix?

Brute Force Solution

Approach

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

Think about choosing two corners to define a rectangle.
Start by picking any possible top-left corner in the grid.
Then, for that chosen corner, try every possible bottom-right corner that's below and to the right of the top-left corner.
For each pair of corners, check if the rectangle they define is completely filled with ones. If even one zero is inside, that rectangle isn't valid.
If the rectangle is valid (all ones), calculate its area.
Keep track of the largest area you've found so far.
Repeat this process by starting with a new top-left corner and checking all possible bottom-right corners for it.
Continue until you've considered every possible top-left corner in the entire grid.
At the end, the largest area you recorded is the maximal rectangle.

Code Implementation

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

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

    for top_row in range(rows):
        for left_col in range(cols):
            # Iterate through all possible bottom-right corners for the chosen top-left
            for bottom_row in range(top_row, rows):
                for right_col in range(left_col, cols):
                    is_valid_rectangle = True

                    # Check if the submatrix contains only 1s
                    for row_to_check in range(top_row, bottom_row + 1):
                        for col_to_check in range(left_col, right_col + 1):
                            if matrix[row_to_check][col_to_check] == '0':
                                is_valid_rectangle = False
                                break
                        if not is_valid_rectangle:
                            break

                    # Calculate area only for valid rectangles
                    if is_valid_rectangle:

                        rectangle_width = right_col - left_col + 1
                        rectangle_height = bottom_row - top_row + 1
                        area = rectangle_width * rectangle_height
                        max_area = max(max_area, area)

    return max_area

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, go through the grid row by row and transform each cell into a height. The height represents how many consecutive '1's are stacked up above that cell, including itself. If a cell is '0', its height is zero, meaning no bar.
For each row, imagine you have a histogram where the height of each bar is determined by the 'height' value we calculated in the previous step.
To find the largest rectangle in that histogram, look at each bar and figure out how far you can expand it to the left and right until you reach a shorter bar.
The area of the rectangle you can make from that bar (its height multiplied by the width you found in the previous step) is a possible candidate for the largest rectangle.
Keep track of the largest rectangle found so far as you go through all bars in the current row.
Repeat this process for every row of the grid, updating the largest rectangle found overall.

Code Implementation

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

    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    heights = [[0] * number_of_columns for _ in range(number_of_rows)]
    max_area = 0

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if matrix[row_index][column_index] == '1':
                # Accumulate heights based on consecutive '1's.
                heights[row_index][column_index] = (heights[row_index - 1][column_index] + 1
                                                     if row_index > 0 else 1)

        # Find the largest rectangle area for the current row.
        max_area = max(max_area, largest_rectangle_area(heights[row_index]))

    return max_area

def largest_rectangle_area(heights):
    stack = []
    max_area = 0
    index = 0

    while index < len(heights):
        if not stack or heights[index] > heights[stack[-1]]:
            stack.append(index)
            index += 1
        else:
            # Calculate area when encountering a smaller height
            top = stack.pop()
            area = (heights[top] *
                    (index - stack[-1] - 1 if stack else index))

            max_area = max(max_area, area)

    # Process remaining bars in the stack
    while stack:
        top = stack.pop()
        #Calculate area with the remaining histogram bars
        area = (heights[top] *
                (index - stack[-1] - 1 if stack else index))

        max_area = max(max_area, area)

    return max_area

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 immediately as there's no rectangle to compute.
Matrix with zero rows or columns	Return 0, as a rectangle requires at least one row and one column.
Matrix with a single row	Treat the row as a histogram and calculate the largest rectangular area in it.
Matrix with a single column	Calculate the maximum consecutive '1's multiplied by the width (which is 1).
Matrix filled entirely with '0's	Return 0, as no rectangle of '1's can be formed.
Matrix filled entirely with '1's	Return the area of the entire matrix (rows * cols).
Integer overflow when calculating area (height * width)	Use long or equivalent data type to store the intermediate area result before comparison.
Large matrix that might cause stack overflow if using recursive histogram area calculation	Implement the histogram area calculation iteratively using a stack to avoid stack overflow.