1727. Largest Submatrix With Rearrangements

/**
 * Problem: LeetCode 1727 - Largest Submatrix With Rearrangements
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.Arrays;

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int maxArea = 0;

        // Compute consecutive 1s height for each column
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] += matrix[i - 1][j];
                }
            }
        }

        // For each row, sort heights and find max rectangular area
        for (int i = 0; i < m; i++) {
            int[] row = matrix[i].clone();
            Arrays.sort(row);

            for (int j = 0; j < n; j++) {
                int height = row[j];
                int width = n - j;
                maxArea = Math.max(maxArea, height * width);
            }
        }

        return maxArea;
    }
}

"""
Problem: LeetCode 1727 - Largest Submatrix With Rearrangements
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List


class Solution:

    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        max_area = 0

        # Accumulate consecutive 1s for each column
        for i in range(1, m):
            for j in range(n):
                if matrix[i][j] == 1:
                    matrix[i][j] += matrix[i - 1][j]

        # For each row, sort heights in descending order to compute maximum rectangle
        for i in range(m):
            row = sorted(matrix[i], reverse=True)
            for k in range(n):
                height = row[k]
                width = k + 1
                max_area = max(max_area, height * width)

        return max_area

/**
 * Problem: LeetCode 1727 - Largest Submatrix With Rearrangements
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int largestSubmatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int maxArea = 0;

        // Compute consecutive 1s height for each column
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 1) {
                    matrix[i][j] += matrix[i - 1][j];
                }
            }
        }

        // For each row, sort heights and find maximum rectangular area
        for (int i = 0; i < m; i++) {
            vector<int> row = matrix[i];
            sort(row.begin(), row.end());

            for (int j = 0; j < n; j++) {
                int height = row[j];
                int width = n - j;
                maxArea = max(maxArea, height * width);
            }
        }

        return maxArea;
    }
};

/**
 * Problem: LeetCode 1727 - Largest Submatrix With Rearrangements
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var largestSubmatrix = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    let maxArea = 0;

    // Compute consecutive 1s height for each column
    for (let i = 1; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (matrix[i][j] === 1) {
                matrix[i][j] += matrix[i - 1][j];
            }
        }
    }

    // For each row, sort heights and find max rectangular area
    for (let i = 0; i < m; i++) {
        const row = matrix[i].slice().sort((a, b) => a - b);
        for (let j = 0; j < n; j++) {
            const height = row[j];
            const width = n - j;
            maxArea = Math.max(maxArea, height * width);
        }
    }

    return maxArea;
};