The O(n) Club: Maximal Rectangle — How Histograms Secretly Run the Grid

The O(n) Club: Maximal Rectangle — How Histograms Secretly Run the Grid

⚡ TL;DR

If you’re hunting for the biggest rectangle of 1’s in a binary matrix, don’t do the math equivalent of shoveling snow with a teaspoon. Treat each row as a histogram, stack bravely, and conquer efficiently:

// O(mn) time, no soul-crushing brute-force:
int maximalRectangle(char[][] matrix) {
    int max = 0;
    int[] heights = new int[matrix[0].length];
    for(int r = 0; r < matrix.length; r++) {
        for(int c = 0; c < matrix[0].length; c++) {
            heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
        }
        max = Math.max(max, largestRectangleArea(heights));
    }
    return max;
}

🧠 How Devs Usually Mess This Up

The classic: brute-forcing every possible rectangle, as if time and RAM grow on trees. O(n³m³) means you’ll see your code time out before your next meeting. Others faceplant when they forget how rows stack into histograms, or lose an existential duel with Java’s stack logic for Largest Rectangle in Histogram. If your solution is longer than War and Peace, you’re in the brute-force zone.

🔍 What’s Actually Going On

Every row is another “floor” for your histogram tower. For each cell, you remember how tall the pillar of 1’s is, counting straight up from the very first row to the current line. Each time you finish a row, imagine you’ve just sculpted a fresh skyline—now calculate the biggest rectangle using the classic stack trick. If rows are floors, heights[] is your skyscraper. Biggest rectangle? It’s just one histogram away, and stacks are your hardhat-wearing friends on this construction site.

🛠️ PseudoCode

• Loop through each row in the matrix:
  • heights[c] = (matrix[r][c] == '1') ? heights[c] + 1 : 0;
  Add 1 to the column height for a ‘1’, reset to 0 for a ‘0’. Each row “remembers” how many 1’s have stacked vertically.
• After updating heights, call Largest Rectangle in Histogram:
  • Use a stack to store the index of columns as long as bars keep growing.
  Pop for smaller heights, and at each pop, calculate area = popped-height * width-without-smaller-left.
• Keep max area found—across all rows, across all histograms. Winner takes all.
• All this runs O(n) per row and, yeah, that’s good. Coffee still hot when you’re done.

💻 The Code

public class MaximalRectangle {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int max = 0;
        int[] heights = new int[matrix[0].length];
        for (int r = 0; r < matrix.length; r++) {
            for (int c = 0; c < matrix[0].length; c++) {
                heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
            }
            max = Math.max(max, largestRectangleArea(heights));
        }
        return max;
    }
    private int largestRectangleArea(int[] heights) {
        java.util.Stack<Integer> stack = new java.util.Stack<>();
        int maxArea = 0;
        int n = heights.length;
        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!stack.isEmpty() && h < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty Matrix? Make sure you check for nulls and emptiness—otherwise, you’ll start debugging bugs that don’t exist (the Java way).
• Stack Slaps: Remember to push a zero-height at the end, or your rectangles won’t “close.”
• Heights[] Headache: Forget to reset a height at a ‘0’, and now your histograms are lying to you.
• Complexity Check: O(mn) time, O(n) space. Not a Big-O contest, but finally something you can brag about in interviews.

🧠 Interviewer Brain-Tattoo

“Every big rectangle is just a bunch of 1’s trying to be a histogram. Stack up, wise up.” 🏙️