Largest Submatrix With Rearrangements

medium matrix sorting greedy

Problem

Given a binary matrix, you may rearrange the columns. Return the largest area submatrix of all 1s.

Inputmatrix = [[0,0,1],[1,1,1],[1,0,1]]

Output4

After rearranging columns row 1 still 1s → height=2 across 2 cols, plus row 2 contributes; answer 4.

matrix (rows ';' csv 0/1)

def largest_submatrix(matrix):
    m, n = len(matrix), len(matrix[0])
    for r in range(1, m):
        for c in range(n):
            if matrix[r][c] == 1:
                matrix[r][c] = matrix[r-1][c] + 1
    best = 0
    for row in matrix:
        s = sorted(row, reverse=True)
        for j, h in enumerate(s):
            best = max(best, h * (j + 1))
    return best

function largestSubmatrix(matrix) {
  const m = matrix.length, n = matrix[0].length;
  for (let r = 1; r < m; r++)
    for (let c = 0; c < n; c++)
      if (matrix[r][c] === 1) matrix[r][c] = matrix[r-1][c] + 1;
  let best = 0;
  for (const row of matrix) {
    const s = row.slice().sort((a, b) => b - a);
    for (let j = 0; j < s.length; j++) best = Math.max(best, s[j] * (j + 1));
  }
  return best;
}

class Solution {
    public int largestSubmatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for (int r = 1; r < m; r++)
            for (int c = 0; c < n; c++)
                if (matrix[r][c] == 1) matrix[r][c] = matrix[r-1][c] + 1;
        int best = 0;
        for (int[] row : matrix) {
            int[] s = row.clone();
            Arrays.sort(s);
            for (int j = 0; j < s.length; j++)
                best = Math.max(best, s[j] * (s.length - j));
        }
        return best;
    }
}

int largestSubmatrix(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    for (int r = 1; r < m; r++)
        for (int c = 0; c < n; c++)
            if (matrix[r][c] == 1) matrix[r][c] = matrix[r-1][c] + 1;
    int best = 0;
    for (auto row : matrix) {
        sort(row.begin(), row.end(), greater<int>());
        for (int j = 0; j < (int)row.size(); j++) best = max(best, row[j] * (j + 1));
    }
    return best;
}

Explanation

Since we are allowed to shuffle columns freely, the order of columns does not matter — only how tall each column of 1s is. The idea is to turn each column into a stack height, then for each row find the best rectangle we can form.

First we build heights: for every cell that holds a 1, we replace it with the count of consecutive 1s ending at that cell going up. We do this with matrix[r][c] = matrix[r-1][c] + 1 whenever the cell is a 1.

Now treat each row as a list of column heights. Because columns can be rearranged, we sort each row descending. If the sorted heights are [3, 2, 2, 1], then using the first j+1 tallest columns the rectangle area is height * (j+1).

We take the best area over every position in every row. Sorting puts the tallest columns side by side, which is exactly the widest solid block we can make at that height.

Example row of heights [2, 1, 2] sorts to [2, 2, 1]. At j=1 the area is 2 * 2 = 4, which is the answer for the sample matrix.

Time: O(m·n log n) Space: O(1)