Largest Rectangle with Column Swaps

Problem Overview

You may reorder columns freely, so a solid rectangle of 1s is limited only by how many columns share a given streak of consecutive 1s ending at the current row.

Intuition

You may reorder columns freely, so a solid rectangle of 1s is limited only by how many columns share a given streak of consecutive 1s ending at the current row. Treat each row as the bottom of a histogram: height[j] is the run of 1s in column j. For every possible minimum height h, the usable width is the number of columns with height at least h. The area is h times that width; take the maximum over rows and heights.

Algorithm

1Keep heights[0..m-1] for consecutive 1s ending at the current row.
2For each row i: set heights[j] = heights[j]+1 if mat[i][j] is 1, else 0.
3Count frequencies of heights in 0..n.
4Walk h from n down to 1, adding freq[h] into width (columns with height >= h). Update answer with h * width.
5Return the maximum area seen.

Example Walkthrough

Input: mat = [[0,1,1],[1,1,0],[1,1,1]]

1. After row 0, heights = [0,1,1]. Width for h=1 is 2, area = 2.
2. After row 1, heights = [1,2,0]. Width for h=1 is 2, area = 2; for h=2 width = 1, area = 2.
3. After row 2, heights = [2,3,1]. For h=1 width = 3 area = 3; h=2 width = 2 area = 4; h=3 width = 1 area = 3.
4. Best area is 4.

Output: 4

Common Pitfalls

• Do not run the classic largest-rectangle-in-histogram stack on unsorted heights. Column swaps make any order legal, so sorting (or counting) is required.
• Heights reset to 0 on a 0 cell; they do not carry across zeros.
• Counting sort over 0..n is enough. A full comparison sort is slower and unnecessary.
• width after scanning down to h counts columns with height >= h, not only height exactly h.

Largest Rectangle with Column Swaps.java

Java

// Approach: Consecutive-1 heights per column with each row as the bottom.
// Column swaps mean any order of those heights is allowed, so for minimum
// height h the width is the count of columns with height >= h. Counting sort
// over 0..n builds that in linear time; track max h * width.
// Complexity: O(n * (m + n)) time and O(m + n) extra space.

class Solution {

    public int maxArea(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[] heights = new int[m];
        int[] freq = new int[n + 1];
        int result = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                heights[j] = mat[i][j] == 1 ? heights[j] + 1 : 0;
            }

            for (int h = 0; h <= n; h++) {
                freq[h] = 0;
            }
            for (int h : heights) {
                freq[h]++;
            }

            int width = 0;
            for (int h = n; h >= 1; h--) {
                width += freq[h];
                if (width > 0) {
                    result = Math.max(result, h * width);
                }
            }
        }

        return result;
    }
}

Was this solution helpful?