Problem Statement in English

You’re given a binary matrix matrix of size m x n. You can 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.

Approach

If for each row, we knew how many consecutive 1s there are in the column, we could sort the row in descending order with respect to the number of consecutive 1s ending at that position. Then, we can calculate the area of the largest submatrix for each row and keep track of the maximum area found. The width would be the number of columns (which is j + 1 since j is zero-indexed) and the height would be the number of consecutive 1s at that position.

Since the row is sorted to have the largest number of consecutive 1s at the beginning, we are guaranteed to have more 1s to the left of the current position, which allows us to calculate the area of the largest submatrix efficiently.

And we’re done!

Solution in Python


class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        M = len(matrix)
        N = 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]

        res = 0
        for i in range(M):
            matrix[i].sort(reverse=True)
            for j in range(N):
                res = max(res, matrix[i][j] * (j + 1))

        return res

Complexity

  • Time: $O(M \times N \log N)$
    Where M is the number of rows and N is the number of columns. We iterate through the matrix once and then sort each row.

  • Space: $O(1)$
    Since we’re only using a few variables to keep track of the result and dimensions of the matrix.

Mistakes I Made

I had to look this one up :(

And we are done.