Largest Submatrix With Rearrangements - Practice Coding Problems

Largest Submatrix With Rearrangements - Problem

You are given a binary matrix matrix of size m × 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.

A submatrix is a contiguous rectangular area within the matrix. The area is calculated as width × height.

Input & Output

Example 1 — Basic Rearrangement

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

› Output: 2

💡 Note: Rearrange columns to [[1,1,0],[1,0,1]] or similar. The largest submatrix of 1s has area 2 (either 2×1 or 1×2).

Example 2 — Larger Matrix

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

› Output: 2

💡 Note: After optimal rearrangement, we can get a 2×1 or 1×2 submatrix of all 1s.

Example 3 — All Zeros

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

› Output: 0

💡 Note: No 1s in the matrix, so the largest submatrix of 1s has area 0.

Constraints

1 ≤ m, n ≤ 10⁵
1 ≤ m × n ≤ 10⁵
matrix[i][j] is 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 1s and 0s that can be rearranged by columns

Rearrange Columns

Find optimal column order to maximize submatrix of 1s

Maximum Area

Calculate area of largest rectangular submatrix containing only 1s

Key Takeaway

🎯 Key Insight: Transform into histogram problem by calculating consecutive 1s heights, then use greedy column sorting to maximize rectangle area.

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to transform this into a histogram problem for each row. Calculate consecutive 1s heights, sort columns optimally, then find maximum rectangle. Best approach uses greedy column sorting. Time: O(m × n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Row by Row Heights	O(m × n log n)	O(n)	Calculate consecutive 1s height for each row and use greedy column sorting
Brute Force - Try All Arrangements	O(n! × m² × n²)	O(m × n)	Generate all column permutations and find maximum submatrix area

Greedy - Row by Row Heights — Algorithm Steps

Calculate heights of consecutive 1s for each position
For each row, sort columns by their heights
Apply largest rectangle in histogram algorithm

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Heights

For each row, calculate consecutive 1s height per column

Sort Columns

Sort columns by height in descending order

Find Max Area

Use histogram approach to find maximum rectangle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)b - *(int*)a);  // Descending order
}

int solution(int** matrix, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    int* heights = (int*)calloc(n, sizeof(int));
    int* sortedHeights = (int*)malloc(n * sizeof(int));
    int maxArea = 0;
    
    for (int i = 0; i < m; i++) {
        // Update heights for current row
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                heights[j]++;
            } else {
                heights[j] = 0;
            }
        }
        
        // Copy and sort heights in descending order
        memcpy(sortedHeights, heights, n * sizeof(int));
        qsort(sortedHeights, n, sizeof(int), compare);
        
        // Find maximum rectangle area
        for (int width = 1; width <= n; width++) {
            int height = sortedHeights[width - 1];
            int area = width * height;
            if (area > maxArea) maxArea = area;
        }
    }
    
    free(heights);
    free(sortedHeights);
    return maxArea;
}

int main() {
    // Simple example: [[1,0,1],[1,1,0]]
    int m = 2, n = 3;
    int** matrix = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        matrix[i] = (int*)malloc(n * sizeof(int));
    }
    
    matrix[0][0] = 1; matrix[0][1] = 0; matrix[0][2] = 1;
    matrix[1][0] = 1; matrix[1][1] = 1; matrix[1][2] = 0;
    
    printf("%d\n", solution(matrix, m, n));
    
    for (int i = 0; i < m; i++) free(matrix[i]);
    free(matrix);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n log n)

For each of m rows, sort n columns (O(n log n)) and find max rectangle (O(n))

⚡ Linearithmic

Space Complexity

O(n)

Arrays to store heights and stack for histogram algorithm

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Row by Row Heights — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler