Largest Submatrix With Rearrangements

Medium
1571.

Largest Submatrix With Rearrangements

Largest Submatrix With Rearrangements is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Directi interviews.

You are given an m x n binary matrix matrix. You may reorder its columns in any way you like (each column moves as a whole).

After reordering optimally, return the area of the largest sub-matrix in which every cell is 1.

Example 1

Input
matrix = [[1,0,1],[1,1,1],[0,1,1]]
Output
4
Explanation
Put column 2 next to column 0: rows 0–1 of those two columns are all 1s (area 4). Columns 1 and 2 over rows 1–2 also give 4.

Example 2

Input
matrix = [[0,1,0,1,1]]
Output
3

Example 3

Input
matrix = [[0,0],[0,0]]
Output
0

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m * n <= 10^5
  • matrix[i][j] is 0 or 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var largestSubmatrix = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Submatrix With Rearrangements — Problem & Solution

Largest Submatrix With Rearrangements solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Largest Submatrix With Rearrangements is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Directi interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Greedy, Matrix
  • Asked at: Amazon, Google, Directi
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an m x n binary matrix matrix. You may reorder its columns in any way you like (each column moves as a whole).

After reordering optimally, return the area of the largest sub-matrix in which every cell is 1.

Example 1

Input: matrix = [[1,0,1],[1,1,1],[0,1,1]]
Output: 4
Explanation: Put column 2 next to column 0: rows 0–1 of those two columns are all 1s (area 4). Columns 1 and 2 over rows 1–2 also give 4.

Example 2

Input: matrix = [[0,1,0,1,1]]
Output: 3

Example 3

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

Constraints

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

Hints for Largest Submatrix With Rearrangements

  1. Hint 1

    Fix the bottom row of the sub-matrix. For each column, how tall a run of 1s ends at that row?

  2. Hint 2

    Columns can be reordered freely, so for a fixed bottom row you may line the columns up from tallest to shortest.

  3. Hint 3

    Sort the heights in descending order; using the first i + 1 of them gives width i + 1 and height heights[i]. Take the best product over all rows.

How to solve Largest Submatrix With Rearrangements

For each bottom row, the column heights (consecutive 1s ending there) fully describe what is possible, and sorting them descending turns the best rectangle into a simple scan.

Approach

  1. Maintain h[c]: the number of consecutive 1s in column c ending at the current row (reset to 0 on a 0).
  2. For each row, update h, copy it, and sort the copy in descending order.
  3. For each i, a rectangle of width i + 1 and height sorted[i] fits (the i + 1 tallest columns placed side by side); update the answer with sorted[i] * (i + 1).

Why it works

Any all-ones sub-matrix with bottom row r and height t uses columns whose heights at r are at least t. Reordering lets all such columns sit together, so the best rectangle with bottom row r and width w has height equal to the w-th largest height — exactly what the sorted scan checks.

Complexity

  • Time — O(m · n log n)
  • Space — O(n)

Pitfalls

  • Only whole columns move — rows keep their order, so heights must be consecutive runs in the original row order.
  • Reset a column's height to 0 when the current cell is 0.
  • Sort a copy of the heights; the running heights must stay in column order for the next row.

Reference solution

Python

from typing import List

def largestSubmatrix(matrix: List[List[int]]) -> int:
    n = len(matrix[0])
    h = [0] * n
    best = 0
    for row in matrix:
        for c in range(n):
            h[c] = h[c] + 1 if row[c] == 1 else 0
        s = sorted(h, reverse=True)
        for i, v in enumerate(s):
            best = max(best, v * (i + 1))
    return best

Java

public static int largestSubmatrix(int[][] matrix) {
    int n = matrix[0].length, best = 0;
    int[] h = new int[n];
    for (int[] row : matrix) {
        for (int c = 0; c < n; c++) h[c] = row[c] == 1 ? h[c] + 1 : 0;
        int[] s = h.clone();
        Arrays.sort(s);
        for (int i = n - 1; i >= 0; i--) best = Math.max(best, s[i] * (n - i));
    }
    return best;
}

C++

int largestSubmatrix(vector<vector<int>>& matrix) {
    int n = matrix[0].size(), best = 0;
    vector<int> h(n, 0);
    for (auto& row : matrix) {
        for (int c = 0; c < n; c++) h[c] = row[c] == 1 ? h[c] + 1 : 0;
        vector<int> s = h;
        sort(s.rbegin(), s.rend());
        for (int i = 0; i < n; i++) best = max(best, s[i] * (i + 1));
    }
    return best;
}

JavaScript

var largestSubmatrix = function(matrix) {
    var n = matrix[0].length, h = new Array(n).fill(0), best = 0;
    for (var r = 0; r < matrix.length; r++) {
        for (var c = 0; c < n; c++) h[c] = matrix[r][c] === 1 ? h[c] + 1 : 0;
        var s = h.slice().sort(function(a, b) { return b - a; });
        for (var i = 0; i < n; i++) best = Math.max(best, s[i] * (i + 1));
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms