Largest Submatrix with Rearrangements LeetCode Solution

The Largest Submatrix with Rearrangements problem involves optimizing a binary matrix to find the largest submatrix with consecutive rows. We explore the approach and code solutions in Python, Java, and C++.

Problem Overview

Given a binary matrix (0s and 1s), the goal is to rearrange its rows to maximize the number of non-decreasing consecutive rows. Subsequently, we aim to find the area of the largest submatrix with these consecutive rows.

Intuition

We approach the problem by transforming the matrix into histograms, where each element represents consecutive 1s in a row. Sorting the rows optimally maximizes the consecutive 1s, facilitating the calculation of the area of the biggest submatrix with rearrangements leetcode problem.

Solution Approach

1. Convert the matrix into histograms, representing consecutive 1s in each row.
2. Sort the rows to maximize the number of consecutive 1s.
3. Calculate the area of the largest submatrix with consecutive rows using the sorted histograms.

Example Walkthrough

Consider the following matrix:1 0 1 1 1 0 1 1 0

Converting the matrix into histograms:1 0 1 2 1 0 3 2 0

Sorting the rows to maximize consecutive 1s:1 0 1 1 1 0 1 1 0

Calculating the area of the largest submatrix with consecutive rows:1 0 1 1 1 0

The area is 3.

Code Solutions

Python

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        for r in range(1, rows):
            for c in range(cols):
                if matrix[r][c] == 1:
                    matrix[r][c] += matrix[r - 1][c]
        max_area = 0
        for r in range(rows):
            sorted_row = sorted(matrix[r], reverse=True)
            for c in range(cols):
                max_area = max(max_area, sorted_row[c] * (c + 1))
        return max_area

Java

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        for (int r = 1; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 1) {
                    matrix[r][c] += matrix[r - 1][c];
                }
            }
        }
        int maxArea = 0;
        for (int r = 0; r < rows; r++) {
            int[] sortedRow = Arrays.copyOf(matrix[r], cols);
            Arrays.sort(sortedRow);
            for (int c = 0; c < cols; c++) {
                maxArea = Math.max(maxArea, sortedRow[c] * (c + 1));
            }
        }
        return maxArea;
    }
}

C++

class Solution {
public:
    int largestSubmatrix(vector>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        for (int r = 1; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (matrix[r][c] == 1) {
                    matrix[r][c] += matrix[r - 1][c];
                }
            }
        }
        int maxArea = 0;
        for (int r = 0; r < rows; r++) {
            vector sortedRow = matrix[r];
            sort(sortedRow.rbegin(), sortedRow.rend());
            for (int c = 0; c < cols; c++) {
                maxArea = max(maxArea, sortedRow[c] * (c + 1));
            }
        }
        return maxArea;
    }
};

Time and Space Complexity

Time Complexity: O(rows * cols * log(cols)) – Sorting rows for each column.

Space Complexity: O(1) – Constant space is used.