{x}
blog image

Largest Submatrix With Rearrangements

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 <= 105
  • matrix[i][j] is either 0 or 1.

Solution Explanation: Largest Submatrix With Rearrangements

This problem asks to find the largest submatrix containing only 1s after optimally rearranging the columns of a given binary matrix. The optimal rearrangement is not explicitly determined; instead, we focus on finding the maximum area achievable through any column rearrangement.

Approach: Preprocessing and Sorting

The solution employs a two-step approach:

  1. Preprocessing: We iterate through the matrix, updating each '1' to represent the height of a consecutive column of 1s above it. This is efficiently done by accumulating the values from the row above. This step effectively transforms the problem from finding a submatrix to finding the largest rectangle in a histogram-like representation where each row represents a histogram.

  2. Sorting and Area Calculation: For each row, we sort the column heights in descending order. This is crucial because sorting allows us to easily find the largest submatrix bounded by that row. Consider the sorted row as a histogram. The largest rectangle will always be formed by taking the tallest bars and extending downwards. Iterating through the sorted row from the largest to smallest column height, we calculate the area (height * width) for a rectangle using the current height and its index (representing the width, as there are at least that many columns with heights greater than or equal to the current height). We keep track of the maximum area found.

Time and Space Complexity Analysis

  • Time Complexity: The preprocessing step takes O(mn) time, where 'm' is the number of rows and 'n' is the number of columns. Sorting each row takes O(n log n) time, and we do this for 'm' rows, resulting in O(mn log n) time. The area calculation within each row also takes O(n) time. Therefore, the overall time complexity is dominated by the sorting, giving us O(m*n log n).

  • Space Complexity: The solution modifies the input matrix in place; hence, the space complexity is O(1) (constant). We do not use any extra data structures whose size depends on the input size.

Code Implementation (Python)

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        for i in range(1, m):
            for j in range(n):
                if matrix[i][j] == 1:
                    matrix[i][j] += matrix[i - 1][j]  # Preprocessing: accumulate height
 
        max_area = 0
        for row in matrix:
            row.sort(reverse=True)  # Sort in descending order
            for i, height in enumerate(row):
                max_area = max(max_area, height * (i + 1)) # Area calculation
 
        return max_area

The code in other languages (Java, C++, Go, TypeScript) follows the same algorithm, with minor syntactic differences. The core logic—preprocessing, sorting, and area calculation—remains consistent across all implementations.