Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For each possible bottom row, column heights describe consecutive ones ending there. Since columns may be rearranged, a rectangle of width w can use the w tallest columns; its height is the shortest among those chosen. Sorting heights exposes that best area for every width.

Approach

Update consecutive-one heights in their original column positions. Sort a copy in descending order and test sortedHeight[i] * (i + 1) for each prefix. Maximize across all rows and widths. Keep the original height array unsorted so the next row updates the correct columns. Different candidate rectangles may imply different rearrangements; only one winning rectangle and its corresponding column permutation need to be realized.

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        acc = [0] * m
        res = 0

        for i in range(n):
            for j in range(m):
                if matrix[i][j]:
                    acc[j] += 1
                else:
                    acc[j] = 0

            s = sorted(acc, reverse = True)
            for ci in range(len(s)):
                res = max(res, s[ci] * (ci + 1))

        return res

Complexity analysis

For r rows and c columns, histogram updates and area scans take O(rc), and sorting one c-element copy per row takes O(rc log c). Total time is O(rc log(c + 1)), including the linear one-column case. Auxiliary space is O(c) for heights, the sorted copy and sorting workspace.