MANG Problem #26: Largest Rectangle in Histogram (Hard)

1. Problem Statement

Mental Model

Breaking down a complex problem into its most efficient algorithmic primitive.

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Input: heights = [2,1,5,6,2,3]
Output: 10 (The rectangle is formed by bars 5 and 6 with height 5 and width 2).

2. Approach: Monotonic Increasing Stack

A rectangle's area is determined by the shortest bar in that range. For every bar, we want to find how far it can extend to the left and right before hitting a bar shorter than itself.

The Goal: Find the index of the first smaller element to the left (L) and the first smaller element to the right (R).
Width: R - L - 1.
Area: heights[curr] * width.
Optimization: Instead of two passes, we use a stack to track indices of bars in increasing order. When we see a bar smaller than the top of the stack, we know the "Right boundary" for the top bar has been found.

3. Java Implementation

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1); // Sentinel for left boundary
    int maxArea = 0;

    for (int i = 0; i < n; i++) {
        // While current height is smaller than top of stack
        while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
            int currentHeight = heights[stack.pop()];
            int currentWidth = i - stack.peek() - 1;
            maxArea = Math.max(maxArea, currentHeight * currentWidth);
        }
        stack.push(i);
    }

    // Process remaining bars in stack
    while (stack.peek() != -1) {
        int currentHeight = heights[stack.pop()];
        int currentWidth = n - stack.peek() - 1;
        maxArea = Math.max(maxArea, currentHeight * currentWidth);
    }
    return maxArea;
}

4. 5-Minute "Video-Style" Walkthrough

The "Aha!" Moment: For any bar H, the largest rectangle using H as its height is limited by the first bars to its left and right that are shorter than H.
The Stack Logic: We push indices onto the stack as long as heights are increasing. As soon as we see a "drop" in height, we know the rectangle for the taller bars "ends" here.
The Width Formula: If the stack top is i and the previous element in the stack is j, and we are currently at index k, the width for bar i is k - j - 1.

5. Interview Discussion

Interviewer: "Why use -1 in the stack?"
You: "It acts as a sentinel representing the virtual wall at index -1. This simplifies the width calculation when a bar can extend all the way to the start of the histogram."
Interviewer: "What is the time complexity?"
You: "O(N). Every index is pushed and popped exactly once."

5. Verbal Interview Script (Staff Tier)

Interviewer: "Walk me through your optimization strategy for this problem."

You: "When approaching this type of challenge, my primary objective is to identify the underlying Monotonicity or Optimal Substructure that allow us to bypass a naive brute-force search. In my implementation of 'MANG Problem #26: Largest Rectangle in Histogram (Hard)', I focused on reducing the time complexity by leveraging a Dynamic Programming state transition. This allows us to handle input sizes that would typically cause a standard O(N^2) approach to fail. Furthermore, I prioritized memory efficiency by optimizing the DP state to use only a 1D array. This ensures that the application remains performant even under heavy garbage collection pressure in a high-concurrency Java environment."

6. Staff-Level Interview Follow-Ups

Once you provide the optimized solution, a senior interviewer at Google or Meta will likely push you further. Here is how to handle the most common follow-ups:

Follow-up 1: "How does this scale to a Distributed System?"

If the input data is too large to fit on a single machine (e.g., billions of records), we would move from a single-node algorithm to a MapReduce or Spark-based approach. We would shard the data based on a consistent hash of the keys and perform local aggregations before a global shuffle and merge phase, similar to the logic used in External Merge Sort.

Follow-up 2: "What are the Concurrency implications?"

In a multi-threaded Java environment, we must ensure that our state (e.g., the DP table or the frequency map) is thread-safe. While we could use synchronized blocks, a higher-performance approach would be to use AtomicVariables or ConcurrentHashMap. For problems involving shared arrays, I would consider a Work-Stealing pattern where each thread processes an independent segment of the data to minimize lock contention.

7. Performance Nuances (The Java Perspective)

Autoboxing Overhead: When using HashMap<Integer, Integer>, Java performs autoboxing which creates thousands of Integer objects on the heap. In a performance-critical system, I would use a primitive-specialized library like fastutil or Trove to use Int2IntMap, significantly reducing GC pauses.
Recursion Depth: As discussed in the code, recursive solutions are elegant but risky for deep inputs. I always ensure the recursion depth is bounded, or I rewrite the logic to be Iterative using an explicit stack on the heap to avoid StackOverflowError.

Key Takeaways

Interviewer: "Why use -1 in the stack?"
You: "It acts as a sentinel representing the virtual wall at index -1. This simplifies the width calculation when a bar can extend all the way to the start of the histogram."
Interviewer: "What is the time complexity?"