1727. Largest Submatrix With Rearrangements - Explanation

Description

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: 3

Explanation: You can rearrange the columns as shown above.
The largest submatrix of 1s, in bold, has an area of 3.

Example 2:

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:

1 <= (matrix.length * matrix[i].length) <= 100,000
matrix[i][j] is either 0 or 1.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        res = 0

        for start_row in range(ROWS):
            ones = deque(list(range(COLS)))

            for r in range(start_row, ROWS):
                if not ones:
                    break
                for _ in range(len(ones)):
                    c = ones.popleft()
                    if matrix[r][c] == 1:
                        ones.append(c)

                res = max(res, len(ones) * (r - start_row + 1))

        return res

Time & Space Complexity

Time complexity: $O(m * n ^ 2)$
Space complexity: $O(n)$

Where $m$ is the number of rows and $n$ is the number of columns.

2. Greedy + Sorting

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        res = 0
        prev_heights = [0] * COLS

        for r in range(ROWS):
            heights = matrix[r][:]
            for c in range(COLS):
                if heights[c] > 0:
                    heights[c] += prev_heights[c]

            sorted_heights = sorted(heights, reverse=True)
            for i in range(COLS):
                res = max(res, (i + 1) * sorted_heights[i])

            prev_heights = heights

        return res

Time & Space Complexity

Time complexity: $O(m * n \log n)$
Space complexity: $O(n)$

Where $m$ is the number of rows and $n$ is the number of columns.

3. Greedy + Sorting (Overwriting the Input)

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        res = 0

        for r in range(1, ROWS):
            for c in range(COLS):
                if matrix[r][c]:
                    matrix[r][c] += matrix[r - 1][c]

        for r in range(ROWS):
            matrix[r].sort(reverse=True)
            for i in range(COLS):
                res = max(res, (i + 1) * matrix[r][i])

        return res

Time & Space Complexity

Time complexity: $O(m * n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algoirhtm.

Where $m$ is the number of rows and $n$ is the number of columns.

4. Greedy

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        res = 0
        prevHeights = []

        for r in range(ROWS):
            heights = []
            for c in prevHeights:
                if matrix[r][c]:
                    matrix[r][c] += matrix[r - 1][c]
                    heights.append(c)

            for c in range(COLS):
                if matrix[r][c] == 1:
                    heights.append(c)

            for i, c in enumerate(heights):
                res = max(res, (i + 1) * matrix[r][c])

            prevHeights = heights

        return res

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the number of rows and $n$ is the number of columns.