Formatted question description: https://leetcode.ca/all/1727.html

1727. Largest Submatrix With Rearrangements

Level

Medium

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

Example 4:

Input: matrix = [[0,0],[0,0]]

Output: 0

Explanation: As there are no 1s, no submatrix of 1s can be formed and the area is 0.

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m * n <= 10^5
• matrix[i][j] is 0 or 1.

Solution

For each element in matrix, calculate the number of consecutive 1’s above the element. Concretely, if matrix[i][j] == 1, then find the minimum k such that for all k <= p <= i, there is matrix[p][j] == 1. Create newMatrix with the same size as matrix, and set newMatrix[i][j] = i - k + 1 where k is defined above.

Then for each row curRow in newMatrix, sort curRow and loop over curRow backwards. For curRow[j], the current area is calculated as (n - j) * curRow[j]. Maintain the maximum area in the process.

Finally, return the maximum area.

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int maxArea = 0;
        int rows = matrix.length, columns = matrix[0].length;
        int[][] newMatrix = new int[rows][columns];
        for (int j = 0; j < columns; j++)
            newMatrix[0][j] = matrix[0][j];
        for (int i = 1; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == 1)
                    newMatrix[i][j] = newMatrix[i - 1][j] + 1;
            }
        }
        for (int i = 0; i < rows; i++) {
            int[] curRow = new int[columns];
            System.arraycopy(newMatrix[i], 0, curRow, 0, columns);
            Arrays.sort(curRow);
            for (int j = columns - 1; j >= 0; j--) {
                if (curRow[j] == 0)
                    break;
                int area = (columns - j) * curRow[j];
                maxArea = Math.max(maxArea, area);
            }
        }
        return maxArea;
    }
}

All Problems

All Solutions