Largest Rectangle in Histogram Algorithm Solution

The largest rectangle in histogram problem requires finding the maximum rectangular area that can be formed within a given histogram. This classic algorithmic challenge demonstrates the power of stack-based approaches for solving geometric optimization problems efficiently.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can the input array be empty or null? What's the expected return in such cases?
2. Are duplicate heights allowed in the input array? How should we handle them?
3. Should I return the area value or the indices of the rectangle?
4. Can I modify the input array during computation?
5. What's the expected time complexity target - O(n) or O(n²) is acceptable?

Restatement of the problem: Given an array of non-negative integers representing the heights of bars in a histogram, find the area of the largest rectangular region that can be formed within the histogram.

Clarification of inputs, outputs, and constraints:

• Input: An array heights where heights[i] represents the height of bar at index i
• Output: An integer representing the maximum area of a rectangle that can be formed
• Constraints:
  • Array length can be up to 10⁵ (large input size)
  • Each height value is non-negative integer
  • Need to find contiguous bars that form a rectangle with maximum area

Assumptions I'm making:

• The histogram bars are of unit width (1)
• We're looking for the largest rectangular area that can be formed by taking any contiguous subsequence of bars as the base
• The rectangle must have a height that is at least as tall as all bars in its range

Data shape and hidden structure: The problem has a "maximum subarray" flavor but with area calculation instead of sum. The key insight is that for each bar, we want to find the maximum rectangle that uses that bar as its shortest bar. This creates a monotonic structure where we can use stack-based approaches to efficiently compute the result.

The problem is fundamentally about finding optimal ranges where each element in that range contributes to a rectangle's area, with the constraint that we're looking for maximum area rectangles.

2. Pattern Recognition

The problem asks us to find the largest rectangular area in a histogram where each bar has a given height and width. Looking at the problem statement, I can identify several key patterns:

Most likely pattern: Monotonic Stack The wording "largest rectangle" and the need to consider varying heights suggests we're looking for a maximum area subproblem. The key insight is that for any rectangle, its height is determined by the minimum height bar in that rectangle's range. This suggests we should look for a way to efficiently find the maximum area rectangle.

Why this fits the pattern:

• The histogram structure creates a natural "range" problem where we need to consider subarrays of bars
• We're looking for a maximum area, which often suggests either greedy or stack-based approaches
• The "largest rectangle" constraint hints at a divide-and-conquer or monotonic stack approach

Core insight needed: For each bar, we want to know the maximum rectangle that can be formed with that bar as the shortest bar in the rectangle. This means we need to find the leftmost and rightmost bars that are taller than or equal to our current bar. The key insight is that we can maintain a monotonic stack of indices where the corresponding heights are in increasing order.

Wording signals:

• "largest rectangle" - maximum area optimization problem
• "histogram" - array of bars with heights - suggests we can think in terms of ranges
• "rectangle" - requires considering width and height together

This is fundamentally about finding the maximum area rectangle in a histogram, which is a classic application of monotonic stack techniques where we process bars and maintain a stack of indices in increasing order of their heights.

The pattern is that we can process the histogram bars from left to right, and for each bar, we calculate what's the maximum rectangle that can be formed with that bar as the shortest bar in the rectangle. This requires maintaining a stack that helps us efficiently find the left and right boundaries for each bar.

3. Approach Evolution

My first instinct is to use a brute force approach where I check every possible rectangle by considering each bar as the shortest bar in that rectangle. For each bar, I would expand left and right to find the maximum width where that bar remains the shortest. This is O(n²) because for each of the n bars, I might need to scan up to n elements. But that's inefficient and not optimal for a FAANG interview.

Let me think about how to optimize this. I notice that if I maintain a monotonic stack of indices, I can calculate the maximum rectangle area more efficiently. The key insight is that for each bar, if I know the nearest smaller element to its left and right, I can calculate the maximum rectangle that includes that bar as the shortest one in that range.

I notice that if I maintain a stack of indices in increasing order of heights, when I encounter a bar with smaller height than the one at stack top, I can calculate the area for the bar at stack top. This approach reduces the complexity to O(n) by ensuring each element is pushed and popped at most once.

The core invariant I need to maintain is that the stack always contains indices in increasing order of their corresponding heights. When processing a new bar, if its height is less than the stack top's height, I pop from the stack and calculate area using the popped element as the shortest bar in that rectangle.

The key optimization is to use a stack-based approach that processes each bar once, calculating areas only when we know the left and right boundaries where that bar is the shortest.

My approach will be:

1. Use a stack to maintain indices in increasing order of heights
2. For each bar, if its height is less than stack top, calculate area for the popped element
3. Handle remaining elements in stack after processing all bars
4. The area for a popped element is calculated as: height × (right_boundary - left_boundary - 1)

This approach ensures we process each element only once and achieve O(n) time complexity.

4. Data Structure Choice

For solving the Largest Rectangle in Histogram problem, I'll use a stack-based approach with a monotonic stack to maintain indices of histogram bars in increasing order of their heights.

Primary Data Structures Used

1. Stack - to store indices of histogram bars
2. Array<Integer[]> - for storing height and index information (optional but helpful for clarity)

Why Each Data Structure Is Needed

The stack serves as the core data structure because:

• It maintains a monotonic property: heights in the stack are always in increasing order
• It allows us to efficiently track when we can calculate rectangle areas
• It enables O(1) amortized operations for both push and pop operations

Time and Space Impact

• Time Complexity: O(n) for stack operations (each element pushed and popped at most once)
• Space Complexity: O(n) for the stack in worst case (when histogram is strictly increasing)

Helper Structure

I'm using a stack of indices rather than stack of heights, because:

• We need to know the width of rectangles, which depends on the distance between indices
• Storing indices allows us to calculate width as current_index - stack.peek() - 1 when we pop from stack
• This approach avoids the need for additional arrays to store left/right boundaries

The stack-based approach is optimal here because:

1. It's space-efficient - only storing indices that might contribute to future rectangles
2. It's time-efficient - each element is processed at most twice (once pushed, once popped)
3. It's cleanly implementable - the monotonic property naturally handles the rectangle expansion logic

This choice is better than alternatives like:

• Using two separate arrays for left/right boundaries (O(n) extra space)
• Using brute force with nested loops (O(n²) time complexity)
• Using segment trees or other advanced structures (overkill for this problem)

The stack approach elegantly captures the core insight that we only need to track "candidate" bars that could form larger rectangles, making it the ideal choice for this problem.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

Example: heights = [2, 1, 5, 6, 2, 3]

Step 1: Initialize stack with -1 to handle edge case of rectangle starting from index 0.

• Stack: [-1]

Step 2: Process height = 2 at index 0

• Stack top = -1, height[0] = 2 > heights[stack.peek()] = heights[-1] = 0 (default)
• Push index 0 to stack
• Stack: [-1, 0]

Step 3: Process height = 1 at index 1

• Stack top = 0, height[1] = 1 < heights[stack.peek()] = heights[0] = 2
• Pop stack: index 0, height = 2, width = 1 - (-1) - 1 = 1
• Area = height × width = 2 × 1 = 2
• Update maxArea = max(0, 2) = 2
• Stack top = -1, height[1] = 1 > heights[stack.peek()] = heights[-1] = 0
• Push index 1 to stack
• Stack: [-1, 1]

Step 4: Process height = 5 at index 2

• Stack top = 1, height[2] = 5 > heights[stack.peek()] = heights[1] = 1
• Push index 2 to stack
• Stack: [-1, 1, 2]

Step 5: Process height = 6 at index 3

• Stack top = 2, height[3] = 6 > heights[stack.peek()] = heights[2] = 5
• Push index 3 to stack
• Stack: [-1, 1, 2, 3]

Step 6: Process height = 2 at index 4

• Stack top = 3, height[4] = 2 < heights[stack.peek()] = heights[3] = 6
• Pop stack: index 3, height = 6, width = 4 - (2) - 1 = 1
• Area = height × width = 6 × 1 = 6
• Update maxArea = max(2, 6) = 6
• Pop stack: index 2, height = 5, width = 4 - (1) - 1 = 2
• Area = height × width = 5 × 2 = 10
• Update maxArea = max(6, 10) = 10
• Stack top = 1, height[4] = 2 < heights[stack.peek()] = heights[1] = 1
• Stop popping, push index 4 to stack
• Stack: [-1, 1, 4]

Step 7: Process height = 3 at index 5

• Stack top = 4, height[5] = 3 > heights[stack.peek()] = heights[4] = 2
• Push index 5 to stack
• Stack: [-1, 1, 4, 5]

Step 8: End of array, process remaining elements in stack

• Pop stack: index 5, height = 3, width = 6 - (4) - 1 = 1
• Area = height × width = 3 × 1 = 3
• Update maxArea = max(10, 3) = 10
• Pop stack: index 4, height = 2, width = 6 - (1) - 1 = 4
• Area = height × width = 2 × 4 = 8
• Update maxArea = max(10, 8) = 10
• Pop stack: index 1, height = 1, width = 6 - (-1) - 1 = 6
• Area = height × width = 1 × 6 = 6
• Update maxArea = max(10, 6) = 10

Final result: maxArea = 10, which corresponds to the rectangle formed by heights [5,6] with width 2.

The key insight is that we maintain a stack of indices in increasing order of heights, and whenever we find a smaller height, we calculate areas for all taller bars that can no longer extend to the right. This ensures we consider all possible rectangles efficiently.

public class Solution {
    public int largestRectangleInHistogram(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;
        
        for (int i = 0; i <= heights.length; i++) {
            int currentHeight = (i == heights.length) ? 0 : heights[i];
            
            while (stack.peek() != -1 && 
                   (i == heights.length || heights[stack.peek()] > currentHeight)) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            
            if (i < heights.length) {
                stack.push(i);
            }
        }
        
        return maxArea;
    }
}

6. Java Solution

import java.util.*;

public class LargestRectangleInHistogram {
    
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;
        
        // Process each bar and maintain a stack of indices in increasing order of heights
        for (int i = 0; i <= n; i++) {
            // Use 0 as height for the "virtual" bar after the last element
            int currentHeight = (i == n) ? 0 : heights[i];
            
            // While stack is not empty and current height is less than stack top height
            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                // Pop the stack top and calculate area with popped bar as smallest bar
                int height = heights[stack.pop()];
                // Width is calculated from the new stack top to current position
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            
            // Push current index to stack
            stack.push(i);
        }
        
        return maxArea;
    }
}

This solution uses a stack-based approach to efficiently compute the largest rectangle in a histogram. The key insight is that we maintain a stack of indices where heights are in increasing order, allowing us to calculate areas when we encounter a bar that is shorter than the one at the stack top. The algorithm handles edge cases like empty arrays and uses a virtual bar of height 0 to process remaining elements in the stack.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm processes each bar in the histogram exactly twice - once when pushing to the stack and once when popping from the stack. Although there appears to be nested loops, the key insight is that each element is pushed and popped at most once from the stack, making the amortized time complexity linear.

Space Complexity: O(n)

The space complexity is dominated by the stack, which in the worst case can contain all n elements (when the histogram bars are in strictly increasing order). Additionally, we use O(1) extra space for variables like maxArea and loop counters.

Why these bounds are correct:

1. Time Analysis: While the inner while loop might seem to make the complexity O(n²), it's actually O(n) amortized. Each element is pushed once and popped at most once, so the total number of operations across all elements is 2n.

2. Space Analysis: The stack size never exceeds n elements in any scenario, and we only use a constant amount of additional variables.

Optimality:

This solution is optimal for the problem as it requires examining each bar at least once to determine the maximum rectangle area. The O(n) time complexity matches the information-theoretic lower bound for this problem, making it near-optimal. The solution avoids the need for O(n²) brute force approaches that would check all possible rectangles.

The algorithm efficiently handles the "largest rectangle" constraint by maintaining a monotonic stack that ensures we only compute areas when we can guarantee they are maximal for the current configuration.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty input: An empty histogram should return 0 area. The solution must handle heights.length == 0 gracefully.
• Single element: A histogram with one bar should return the height of that bar as the maximum area.
• Two elements: Must correctly compare areas of individual bars vs combined area.

Duplicate Values and Repeated States

• Duplicate heights: When multiple bars have the same height, the algorithm must correctly calculate areas without overcounting or missing valid rectangles.
• All same heights: A histogram where all bars have identical height should return height * width as the maximum area.

Boundary Conditions

• Zero heights: Bars with zero height should be handled properly - they effectively "cut off" rectangles from being formed.
• Monotonic arrays: Increasing or decreasing height sequences require careful handling of stack operations to avoid index out-of-bounds errors.
• Large input sizes: With up to 10⁵ elements, stack overflow or memory issues could occur if not properly managed.

Common Implementation Mistakes

• Incorrect stack indexing: Using stack.peek() vs stack.pop() in wrong order can lead to incorrect area calculations.
• Missing boundary handling: Not accounting for the leftmost or rightmost bars when calculating rectangle areas.
• Off-by-one errors: Mismanaging the width calculation when a bar is popped from the stack.
• Not resetting stack properly: Failing to clear or reset state between multiple test cases in a batch testing scenario.
• Assuming sorted input: The algorithm must work on unsorted inputs, so any assumption of order can lead to incorrect results.

Additional Considerations

• Integer overflow: When multiplying large heights with wide widths, ensure proper type handling (use long if needed).
• Stack underflow: Ensure stack is never popped when empty, which can be handled by checking stack.isEmpty() before popping.
• Memory allocation: For very large inputs, consider whether the stack's space usage is acceptable in memory-constrained environments.

9. Alternative Approaches

There are several alternative approaches to solving the largest rectangle in histogram problem, each with different trade-offs:

Brute Force Approach: For each bar, calculate the maximum rectangle area that includes that bar by expanding left and right until we hit a shorter bar. This approach has O(n³) time complexity due to nested loops and is inefficient for large inputs.

Divide and Conquer: This approach recursively divides the histogram into halves and finds the maximum rectangle in three possible locations: entirely in the left half, entirely in the right half, or crossing the midpoint. The key insight is that any rectangle crossing the midpoint must include the minimum height bar at the midpoint or one of its adjacent bars. This approach has O(n log n) time complexity but requires more complex implementation with recursion stack overhead.

Stack-based Approach (Alternative): Instead of using a monotonic stack for heights, we can use a stack to maintain indices of bars in increasing order of their heights. When we encounter a bar with smaller height, we pop from the stack and calculate areas using the popped bar's height as the minimum height. This approach also runs in O(n) time but requires careful handling of stack operations.

Dynamic Programming: We can precompute for each bar the maximum width rectangle that includes it, using previously computed values. However, this approach typically results in O(n²) complexity and is more complex to implement correctly.

The stack-based solution chosen in our main approach is preferred because it provides optimal O(n) time complexity with clean, readable implementation that's easier to debug and maintain in an interview setting. The alternative approaches either have worse time complexity or involve more complex logic that increases the chance of implementation errors.

10. Test Cases

public class HistogramTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem description
        int[] heights1 = {2, 1, 5, 6, 2, 3};
        // Expected: 10 (rectangle of height 5 and width 2)
        
        // Test case 2: Empty array
        int[] heights2 = {};
        // Expected: 0
        
        // Test case 3: Single element
        int[] heights3 = {5};
        // Expected: 5
        
        // Test case 4: All same heights
        int[] heights4 = {3, 3, 3, 3};
        // Expected: 12 (rectangle of height 3 and width 4)
        
        // Test case 5: Strictly increasing heights
        int[] heights5 = {1, 2, 3, 4, 5};
        // Expected: 9 (rectangle of height 3 and width 3)
        
        // Test case 6: Strictly decreasing heights
        int[] heights6 = {5, 4, 3, 2, 1};
        // Expected: 9 (rectangle of height 3 and width 3)
        
        // Test case 7: Duplicate heights
        int[] heights7 = {1, 2, 2, 2, 1};
        // Expected: 6 (rectangle of height 2 and width 3)
        
        // Test case 8: Large rectangle at end
        int[] heights8 = {1, 2, 3, 4, 5, 10};
        // Expected: 15 (rectangle of height 5 and width 3)
        
        // Test case 9: Zero heights
        int[] heights9 = {0, 1, 0, 3, 0};
        // Expected: 3 (rectangle of height 3 and width 1)
        
        // Test case 10: Complex mixed pattern
        int[] heights10 = {3, 6, 5, 7, 4, 8, 9, 3, 2};
        // Expected: 15 (rectangle of height 5 and width 3)
    }
}

The test cases cover:

• The canonical example from the problem statement
• Edge cases like empty input and single element arrays
• Boundary conditions with uniform and extreme value patterns
• Duplicate values that can confuse rectangle boundary calculations
• Zero-height bars which require careful handling in area calculation
• Complex mixed patterns that stress the algorithm's rectangle detection capability

Each test case should be run with the implemented solution to verify correctness across various input configurations and ensure robust handling of edge conditions.

11. Final Summary

The core insight is to use a monotonic stack to efficiently track histogram bars that could form the largest rectangle, processing each bar only once to achieve linear time complexity. This solution works by maintaining a stack of indices where bar heights are in increasing order, allowing us to calculate rectangle areas in constant time when we find a smaller height. The stack-based approach is optimal because it avoids the O(n²) brute force method of checking all possible rectangles, and the stack invariant ensures we never reprocess bars unnecessarily. The solution elegantly handles all edge cases including empty inputs, single elements, and various height patterns through careful index management and boundary condition handling.