Largest Rectangle in Histogram

Largest Rectangle in Histogram

1. What is this problem about?

The Largest Rectangle in Histogram coding problem is a classic algorithmic challenge. You are given an array of integers representing the heights of bars in a histogram, where the width of each bar is 1. You need to find the area of the largest rectangle that can be formed within the bounds of this histogram.

2. Why is this asked in interviews?

This is a high-frequency "Hard" question asked by nearly every top-tier tech firm, from Google to Meta. It tests a candidate's ability to use advanced data structures like the Monotonic Stack to achieve a linear time solution. It requires deep logical reasoning to understand how to maintain a stack of "increasing" bars to efficiently calculate the potential area for each height.

3. Algorithmic pattern used

The optimal pattern for this problem is the Monotonic Stack interview pattern. We iterate through the bars and maintain a stack of indices whose heights are in non-decreasing order. When we encounter a bar shorter than the one at the top of the stack, it means the bar at the top has reached its maximum possible width to the right. We pop it and calculate its area using the current index and the index of the new top of the stack as boundaries.

4. Example explanation

Heights: [2, 1, 5, 6, 2, 3].

• Push index 0 (height 2).
• Bar at index 1 (height 1) is shorter than 2. Pop index 0. Area = 2 * (1 - 0) = 2.
• Push index 1 (height 1).
• Push index 2 (height 5).
• Push index 3 (height 6).
• Bar at index 4 (height 2) is shorter than 6. Pop index 3. Area = 6 * (4 - 2 - 1) = 6.
• Pop index 2 (height 5). Area = 5 * (4 - 1 - 1) = 10.
• ... continue through the array. The largest area found in this example would be 10.

5. Common mistakes candidates make

Many candidates try a brute-force O(N²) solution by checking every pair of bars, which is too slow. Another common mistake is failing to handle the bars remaining on the stack after the main loop finishes (often solved by appending a 0 to the end of the heights array). Incorrectly calculating the width of the rectangle when popping from the stack is also a frequent source of bugs.

6. Interview preparation tip

Mastering "Stack, Monotonic Stack interview pattern" questions is essential for high-level interviews. Practice visualizing the stack as a "boundary" finder. Each pop event tells you that the current element is the right boundary and the element under the popped one is the left boundary for the popped height.