Jobs

Interviews

Discussions

Largest Submatrix With Rearrangements

Medium

Asked by:

103 views

Topics:

ArraysGreedy Algorithms

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] is either 0 or 1.

Try coding it in LeetCode

Largest Submatrix With Rearrangements

Medium

Asked by:

103 views

Topics:

ArraysGreedy Algorithms

You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order.

Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally.

Example 1:

Input: matrix = [[0,0,1],[1,1,1],[1,0,1]]
Output: 4
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 4.

Example 2:

Input: matrix = [[1,0,1,0,1]]
Output: 3
Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 3:

Input: matrix = [[1,1,0],[1,0,1]]
Output: 2
Explanation: Notice that you must rearrange entire columns, and there is no way to make a submatrix of 1s larger than an area of 2.

Constraints:

m == matrix.length
n == matrix[i].length
1 <= m * n <= 10⁵
matrix[i][j] is either 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 input matrix, and what is the maximum possible size for the rows and columns?
Can the matrix contain non-binary values (i.e., values other than 0 and 1)?
If the input matrix is empty or null, what should the function return?
If there is no submatrix with any area (all rearrangements result in zero area), what should be returned?
Are the dimensions of the input matrix guaranteed to be rectangular (i.e., all rows have the same number of columns)?

Brute Force Solution

Approach

The brute force way to find the largest submatrix involves checking all possible submatrices and seeing which one, after rearranging its columns, has the biggest area of all 1s. This means we will look at every possible rectangular section within the given matrix.

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

First, consider every possible top-left corner for the submatrix.
For each of these corners, check every possible width and height that would fit within the original matrix.
So, we have a specific submatrix now. For this submatrix, consider every possible order of its columns.
For each column order, count how many consecutive rows in each column contain only 1s, and note the minimum of these consecutive counts across all columns.
Multiply this minimum count with the number of columns in the submatrix. This is the area of a rectangle that consists of entirely 1s for this column order.
Repeat the prior two steps for every possible column order, keeping track of the biggest rectangle we found with all 1s.
Repeat all these steps for every possible submatrix we can define using different top-left corners, widths, and heights. The largest rectangle with all 1s that we found across all submatrices is the answer.

Code Implementation

def largest_submatrix_with_rearrangements_brute_force(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0]) if number_of_rows > 0 else 0
    maximum_area = 0

    for top_row in range(number_of_rows):
        for left_column in range(number_of_columns):
            for height in range(1, number_of_rows - top_row + 1):
                for width in range(1, number_of_columns - left_column + 1):
                    # Extract the current submatrix
                    submatrix = [matrix[i][left_column:left_column + width] for i in range(top_row, top_row + height)]
                    import itertools
                    # Iterate through all possible column permutations
                    for column_permutation in itertools.permutations(range(width)):
                        minimum_height = float('inf')
                        
                        # Find the minimum height of consecutive 1s for the current permutation
                        for column_index in range(width):
                            current_height = 0
                            for row_index in range(height):
                                if submatrix[row_index][column_permutation[column_index]] == 1:
                                    current_height += 1
                                else:
                                    break
                            minimum_height = min(minimum_height, current_height)

                        # Update the maximum area
                        maximum_area = max(maximum_area, minimum_height * width)

    return maximum_area

Big(O) Analysis

Time Complexity

O(m^2 * n^2 * n! * n) – The algorithm iterates through all possible top-left corners of the submatrix, which takes O(m*n) time where m is the number of rows and n is the number of columns in the matrix. For each submatrix defined by the top-left corner, it checks all possible widths and heights which takes at most O(m*n) time. Then, for each submatrix, it considers all possible column orders, which takes O(n!) time where n is the number of columns of the submatrix. For each column order, it calculates the area of the largest submatrix with all 1s, which takes O(n) time because it iterates through each column of the submatrix once. Therefore the overall time complexity is O(m*n * m*n * n! * n) which simplifies to O(m^2 * n^2 * n! * n).

Space Complexity

O(N!) – The brute force algorithm considers all possible orderings of columns within each submatrix to find the largest submatrix of all 1s. To generate these permutations, the algorithm implicitly uses recursion, or an iterative method that effectively mimics a recursive approach, which creates a call stack (or stores intermediate states) whose maximum depth can reach the number of columns in the submatrix. In the worst case, the number of columns can be N (the size of one dimension of the original matrix), and generating all permutations of N columns requires storing intermediate arrays of size N. Thus, the space needed to store these permutations is proportional to N!, making the space complexity O(N!).

Optimal Solution

Approach

To find the largest submatrix, imagine we're building a histogram and want to find the largest rectangle inside it. The key idea is to transform the matrix to represent the heights of potential histogram bars and then rearrange rows to maximize those bars.

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

First, go through the matrix and for each cell that has a '1', update its value to be the sum of '1's above it, including itself. If a cell is '0', it stays '0'. Think of this step as counting the continuous stack of '1's.
Now, for each row, sort the values from largest to smallest. This is like arranging histogram bars from tallest to shortest, because to maximize the rectangle, you want taller bars to be next to each other.
After sorting each row, we can determine the height of a rectangle for any column. For example, the first entry on row 1 will be the height of the first bar on the histogram. Then the first entry on row 2 will be the height of the second bar on the histogram, and so forth.
Finally, find the biggest rectangle we can form in each column. The width of each rectangle will be the column index plus one, as all the numbers to the left of the column will be part of our base width. And the height is the value in our cell.
Keep track of the biggest rectangle area found and update it as necessary. This is the area of the largest submatrix we can get.

Code Implementation

def largestSubmatrix(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    max_area = 0

    # Update matrix to store heights of consecutive 1s.
    for row_index in range(1, number_of_rows):
        for column_index in range(number_of_columns):
            if matrix[row_index][column_index] == 1:
                matrix[row_index][column_index] += matrix[row_index - 1][column_index]

    for row_index in range(number_of_rows):
        # Sort each row to arrange heights for max rectangle area.
        matrix[row_index].sort(reverse=True)

        for column_index in range(number_of_columns):
            # Calculate area considering current height and width
            height = matrix[row_index][column_index]
            width = column_index + 1
            area = height * width
            max_area = max(max_area, area)

    return max_area

Big(O) Analysis

Time Complexity

O(m * n log n) – The algorithm iterates through each of the m rows and n columns of the input matrix once. The dominant operation within each row is sorting. Sorting each row, which contains n elements, takes O(n log n) time using an efficient sorting algorithm like merge sort or quicksort. This sorting is performed for each of the m rows. Therefore, the overall time complexity is O(m * n log n).

Space Complexity

O(1) – The algorithm modifies the input matrix in-place, so no additional space is used for storing an entirely new matrix. While each row is sorted, this is done in-place, not requiring a separate copy of the row. Therefore, the space complexity is dominated by a few constant-sized variables used for tracking the maximum area, loop indices, and intermediate calculations during sorting and area computation. Thus, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Null or empty matrix input	Return 0 immediately as there's no submatrix to evaluate.
Matrix with a single row or a single column	The largest submatrix would be the largest element in that single row or column, so the code should handle this efficiently by simply iterating and returning the maximum value.
Matrix with all zero values	The largest submatrix is zero, so the algorithm should correctly return 0.
Matrix with all one values	The largest submatrix area is the number of columns, as each column can be rearranged to form a submatrix of height equal to the number of rows and width equal to the number of columns.
Maximum-sized matrix (considering memory constraints)	Ensure the sorting and intermediate data structures (like histograms) used during column processing do not cause memory overflow.
Input matrix contains large integer values (potential overflow)	Ensure the calculations for area and intermediate values (e.g., height calculation) do not result in integer overflow; consider using larger data types if necessary.
Matrix with only one row having a '1' value and all other rows having '0' in that column.	The algorithm should correctly identify that the height of the submatrix in that column is 1.
Matrix where all columns are identical after sorting.	The maximum area is simply the height of the matrix times the number of columns (or a single column's sorted value iterated).

Null or empty matrix input

How to Handle:

Return 0 immediately as there's no submatrix to evaluate.

Matrix with a single row or a single column

How to Handle:

The largest submatrix would be the largest element in that single row or column, so the code should handle this efficiently by simply iterating and returning the maximum value.

Matrix with all zero values

How to Handle:

The largest submatrix is zero, so the algorithm should correctly return 0.

Matrix with all one values

How to Handle:

The largest submatrix area is the number of columns, as each column can be rearranged to form a submatrix of height equal to the number of rows and width equal to the number of columns.

Maximum-sized matrix (considering memory constraints)

How to Handle:

Ensure the sorting and intermediate data structures (like histograms) used during column processing do not cause memory overflow.

Input matrix contains large integer values (potential overflow)

How to Handle:

Ensure the calculations for area and intermediate values (e.g., height calculation) do not result in integer overflow; consider using larger data types if necessary.

Matrix with only one row having a '1' value and all other rows having '0' in that column.

How to Handle:

The algorithm should correctly identify that the height of the submatrix in that column is 1.

Matrix where all columns are identical after sorting.

How to Handle:

The maximum area is simply the height of the matrix times the number of columns (or a single column's sorted value iterated).

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 for the rows and columns?
Can the matrix contain non-binary values (i.e., values other than 0 and 1)?
If the input matrix is empty or null, what should the function return?
If there is no submatrix with any area (all rearrangements result in zero area), what should be returned?
Are the dimensions of the input matrix guaranteed to be rectangular (i.e., all rows have the same number of columns)?

Brute Force Solution

Approach

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

First, consider every possible top-left corner for the submatrix.
For each of these corners, check every possible width and height that would fit within the original matrix.
So, we have a specific submatrix now. For this submatrix, consider every possible order of its columns.
For each column order, count how many consecutive rows in each column contain only 1s, and note the minimum of these consecutive counts across all columns.
Multiply this minimum count with the number of columns in the submatrix. This is the area of a rectangle that consists of entirely 1s for this column order.
Repeat the prior two steps for every possible column order, keeping track of the biggest rectangle we found with all 1s.
Repeat all these steps for every possible submatrix we can define using different top-left corners, widths, and heights. The largest rectangle with all 1s that we found across all submatrices is the answer.

Code Implementation

def largest_submatrix_with_rearrangements_brute_force(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0]) if number_of_rows > 0 else 0
    maximum_area = 0

    for top_row in range(number_of_rows):
        for left_column in range(number_of_columns):
            for height in range(1, number_of_rows - top_row + 1):
                for width in range(1, number_of_columns - left_column + 1):
                    # Extract the current submatrix
                    submatrix = [matrix[i][left_column:left_column + width] for i in range(top_row, top_row + height)]
                    import itertools
                    # Iterate through all possible column permutations
                    for column_permutation in itertools.permutations(range(width)):
                        minimum_height = float('inf')
                        
                        # Find the minimum height of consecutive 1s for the current permutation
                        for column_index in range(width):
                            current_height = 0
                            for row_index in range(height):
                                if submatrix[row_index][column_permutation[column_index]] == 1:
                                    current_height += 1
                                else:
                                    break
                            minimum_height = min(minimum_height, current_height)

                        # Update the maximum area
                        maximum_area = max(maximum_area, minimum_height * width)

    return maximum_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 matrix and for each cell that has a '1', update its value to be the sum of '1's above it, including itself. If a cell is '0', it stays '0'. Think of this step as counting the continuous stack of '1's.
Now, for each row, sort the values from largest to smallest. This is like arranging histogram bars from tallest to shortest, because to maximize the rectangle, you want taller bars to be next to each other.
After sorting each row, we can determine the height of a rectangle for any column. For example, the first entry on row 1 will be the height of the first bar on the histogram. Then the first entry on row 2 will be the height of the second bar on the histogram, and so forth.
Finally, find the biggest rectangle we can form in each column. The width of each rectangle will be the column index plus one, as all the numbers to the left of the column will be part of our base width. And the height is the value in our cell.
Keep track of the biggest rectangle area found and update it as necessary. This is the area of the largest submatrix we can get.

Code Implementation

def largestSubmatrix(matrix):
    number_of_rows = len(matrix)
    number_of_columns = len(matrix[0])
    max_area = 0

    # Update matrix to store heights of consecutive 1s.
    for row_index in range(1, number_of_rows):
        for column_index in range(number_of_columns):
            if matrix[row_index][column_index] == 1:
                matrix[row_index][column_index] += matrix[row_index - 1][column_index]

    for row_index in range(number_of_rows):
        # Sort each row to arrange heights for max rectangle area.
        matrix[row_index].sort(reverse=True)

        for column_index in range(number_of_columns):
            # Calculate area considering current height and width
            height = matrix[row_index][column_index]
            width = column_index + 1
            area = height * width
            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 input	Return 0 immediately as there's no submatrix to evaluate.
Matrix with a single row or a single column	The largest submatrix would be the largest element in that single row or column, so the code should handle this efficiently by simply iterating and returning the maximum value.
Matrix with all zero values	The largest submatrix is zero, so the algorithm should correctly return 0.
Matrix with all one values	The largest submatrix area is the number of columns, as each column can be rearranged to form a submatrix of height equal to the number of rows and width equal to the number of columns.
Maximum-sized matrix (considering memory constraints)	Ensure the sorting and intermediate data structures (like histograms) used during column processing do not cause memory overflow.
Input matrix contains large integer values (potential overflow)	Ensure the calculations for area and intermediate values (e.g., height calculation) do not result in integer overflow; consider using larger data types if necessary.
Matrix with only one row having a '1' value and all other rows having '0' in that column.	The algorithm should correctly identify that the height of the submatrix in that column is 1.
Matrix where all columns are identical after sorting.	The maximum area is simply the height of the matrix times the number of columns (or a single column's sorted value iterated).

Null or empty matrix input

How to Handle:

Return 0 immediately as there's no submatrix to evaluate.

Matrix with a single row or a single column

How to Handle:

The largest submatrix would be the largest element in that single row or column, so the code should handle this efficiently by simply iterating and returning the maximum value.

Matrix with all zero values

How to Handle:

The largest submatrix is zero, so the algorithm should correctly return 0.

Matrix with all one values

How to Handle:

The largest submatrix area is the number of columns, as each column can be rearranged to form a submatrix of height equal to the number of rows and width equal to the number of columns.

Maximum-sized matrix (considering memory constraints)

How to Handle:

Ensure the sorting and intermediate data structures (like histograms) used during column processing do not cause memory overflow.

Input matrix contains large integer values (potential overflow)

How to Handle:

Ensure the calculations for area and intermediate values (e.g., height calculation) do not result in integer overflow; consider using larger data types if necessary.

Matrix with only one row having a '1' value and all other rows having '0' in that column.

How to Handle:

The algorithm should correctly identify that the height of the submatrix in that column is 1.

Matrix where all columns are identical after sorting.

How to Handle:

The maximum area is simply the height of the matrix times the number of columns (or a single column's sorted value iterated).