84. Largest Rectangle in Histogram - Detailed Explanation

Problem Statement

Given an array of non-negative integers representing the heights of bars in a histogram (with each bar having a width of 1 unit), find the area of the largest rectangle that can fit entirely under the histogram. In other words, we want to choose a contiguous subset of bars and consider the rectangle spanning from the ground to the minimum height of those bars – among all such rectangles, find the one with maximum area.

• Example 1: heights = [2, 1, 5, 6, 2, 3]
  Output: 10
  Explanation: The largest rectangle can be formed using the bars of height 5 and 6. The rectangle spans those two bars, giving an area of 5 (height) × 2 (width) = 10.
  Illustration: In this histogram, the largest rectangle (shaded in red with area 10) spans the bars of heights 5 and 6. No other contiguous set of bars yields a larger area – for example, using the shorter bar of height 1 across the whole width would only give area 1×6=6, and the single tallest bar of height 6 gives area 6×1=6.

• Example 2: heights = [2, 4]
  Output: 4
  Explanation: The largest rectangle has area 4. In this case, either taking the single bar of height 4 (area 4×1=4) or taking both bars together (minimum height 2 over width 2 gives 2×2=4) yields area 4. So 4 is the maximum possible.

• Example 3: heights = [2, 1, 2]
  Output: 3
  Explanation: The largest rectangle here uses the middle bar of height 1 extended across all three positions (since all bars are at least height 1). This forms an area of 1 (height) × 3 (width) = 3. Other rectangles, like using just one of the height-2 bars (area 2) or the two height-2 bars with the shorter bar limiting height to 1 (area 1×2=2), are smaller.

Constraints:

• 1 <= heights.length <= 10^5 (up to 100,000 bars)
• 0 <= heights[i] <= 10^4 (bar heights range from 0 to 10,000)

These constraints mean an efficient solution is needed for large input sizes. A simple brute-force checking of all possible rectangles (which could be on the order of n^2 or n^3 operations) may be too slow for the upper limits.

Hints

• Think in terms of the smallest bar: Any rectangle spanning a range of bars is limited in height by the shortest bar in that range. This means the maximum area of a rectangle between two indices is always determined by the minimum height in that span. For example, in [2,1,5], any rectangle covering the whole range is bounded by the smallest height (1). Using this insight, consider strategies that focus on these “limiting” bars.

• Brute force strategy: One straightforward approach is to consider every possible pair of bars as the bounds of a rectangle and compute the area. However, checking all pairs and finding the minimum height each time is inefficient. Can you optimize the brute force by not re-scanning the minimum height from scratch for overlapping intervals?

• Stack and “next smaller” elements: A more clever approach is to use a monotonic stack. Try to maintain a stack of indices of bars in increasing order of height. When a new bar is lower than the bar at the top of the stack, it means the bar at the top can’t extend further to the right. At that moment, you can calculate the area of the rectangle with that bar as the smallest height. Using a stack helps you find how far each bar can extend to the left and right without encountering a smaller bar.

• Divide and conquer: Another perspective is to use recursion: find the shortest bar in the entire histogram – this bar defines a possible rectangle spanning the whole width. Then, the problem splits into two subproblems (to the left of this bar and to the right). The largest rectangle will be either the one spanning the full width using the smallest bar, or it lies entirely in the left part, or entirely in the right part. This recursive approach can avoid some unnecessary checks by narrowing the problem, but be mindful of its performance in the worst case (e.g. if the smallest bar is always at one end).

• Use of auxiliary structures: The stack approach can also be viewed in terms of precomputing for each bar:

  • left[i]: how far to the left this bar can extend (index of the previous smaller bar + 1).
  • right[i]: how far to the right it can extend (index of the next smaller bar – 1).
    If you can efficiently find these for each bar (using a stack), then the area using bar i as the smallest height is simply heights[i] * (right[i] - left[i] + 1).

Multiple Approaches

We will discuss three approaches to solve this problem, in increasing order of efficiency:

1. A Brute Force solution that checks all possible rectangles (O(n^2) time).

2. An Optimized Stack-Based solution that uses a monotonic stack to achieve O(n) time.

3. A Divide and Conquer solution that uses recursion (average O(n log n) time).

Each approach will be explained with step-by-step reasoning and examples.

1. Brute Force Approach (O(n^2))

Idea: The brute force solution directly follows the problem definition: consider every possible rectangle formed by contiguous bars and find its area, keeping track of the maximum. One way to do this is to fix a starting index i and an ending index j for the rectangle, and then find the minimum bar height in that range to compute the area. A naive implementation of this idea leads to three nested loops (for i, j, and scanning the min height in between), which would be O(n^3). We can improve it slightly by maintaining the minimum height as we expand j – that way, for each fixed i we only use two loops (the inner loop reuses the previous minimum height calculation when moving j forward). This brings the complexity down to O(n^2), which is still heavy but better than O(n^3).

Step-by-step Algorithm:

1. Initialize maxArea = 0.
2. Loop i from 0 to n-1 (start index of the rectangle):
   a. Set minHeight to a large value (infinity) initially for this starting index.
   b. Loop j from i to n-1 (end index of the rectangle):

   • Update minHeight = min(minHeight, heights[j]) as we move the end index.

   • Compute the area of the rectangle spanning bars i through j with height = minHeight. This area is minHeight * (j - i + 1).

   • Update maxArea if this area is larger.

3. The value in maxArea after these loops will be the largest rectangle area.

Using the Example 3 ([2,1,2]) to illustrate:

• Start with i=0: as j goes 0→2, minHeight will go 2 → 1 (once we include the bar of height 1). The largest area for i=0 comes when j=2 (minHeight=1 over width 3 gives area 3).

• i=1: starting at the middle bar (height 1), extending j to 2 yields minHeight=1 over width 2 (area 2).

• i=2: just the last bar (height 2, area 2).
  The overall max encountered is 3, which matches the expected answer.

This brute force method correctly checks every possibility, but its time complexity is O(n²) in the optimized form (and O(n³) without the min-height optimization), which can be too slow when n = 100k. Space complexity is O(1) (we only use a few variables).

2. Optimized Stack-Based Approach (O(n))

Idea: This approach uses a monotonic stack to achieve linear time. The stack will store indices of bars, maintaining the invariant that their heights are in increasing order on the stack. The key observation is that if we have a bar that is lower than the bar on top of the stack, then the bar on the stack can’t extend any further to the right (because the current bar is a boundary that is lower). At that moment, we can pop the taller bar from the stack and compute the area of the rectangle where that popped bar is the smallest height. By doing this for every bar (pushing when the trend is increasing, popping and calculating area when we see a decrease), we ensure every bar’s maximal rectangle is accounted for exactly once.

Step-by-step Algorithm:

1. Initialize an empty stack (or stack with a sentinel index -1 to simplify calculations) and maxArea = 0. The stack will hold indices of bars in increasing height order.
2. Traverse the array of heights with index i from 0 to n-1:

   • While the stack is not empty (or top is not the sentinel -1) and the current bar’s height is less than the height of the bar at the stack’s top index, it means the stack’s top bar can’t extend to i. Pop the top index t from the stack, treat heights[t] as the height of a potential largest rectangle. The width of this rectangle extends from the index after the new top of stack to index i-1.

     • After popping index t, let the new top of stack be t'. Then t' is the index of the previous smaller bar to the left of t. The current index i is the first smaller bar to the right of t. Therefore, the width of the rectangle with height heights[t] is (i - t' - 1). Compute area = heights[t] * (width) and update maxArea.

   • Push the current index i onto the stack. (By popping out any taller bars, we maintain the increasing height order in the stack.)

3. After processing all bars, there may be some indices left in the stack. These correspond to bars that extend to the end of the histogram. Pop all remaining indices in the stack, and for each popped index t, calculate the area where heights[t] is the smallest height. If the stack becomes empty after popping, it means the bar t could extend all the way to the left end, so take width = n; otherwise use the same width formula as earlier (using the index after the new top as left boundary, and n-1 as right boundary). Update maxArea accordingly.

This algorithm ensures each bar is pushed and popped at most once, making the time complexity O(n). The space complexity is O(n) for the stack storage.

To understand this clearly, let’s do a walkthrough for Example 1 ([2, 1, 5, 6, 2, 3]) using the stack approach:

• Initial state: stack = empty (or [-1] as sentinel to mark left boundary), maxArea = 0. We’ll use -1 as a sentinel index representing a boundary before start.

• i = 0 (height 2): Stack is empty (just sentinel). Push index 0.
  Stack now: [-1, 0] (heights: [_, 2]). maxArea still 0.

• i = 1 (height 1): Current height (1) is less than height at stack top (which is 2 at index 0).
  Pop index 0 from stack. Now stack top is sentinel -1, which indicates no bar to the left.
  The popped bar’s height = 2. Width = i - (new_stack_top) - 1 = 1 - (-1) - 1 = 1.
  Area = 2 × 1 = 2. Update maxArea = 2.
  Now push index 1.
  Stack: [-1, 1] (heights: [_, 1] where 1 is height at index 1).

• i = 2 (height 5): Current height (5) is greater than height at stack top (which is 1 at index 1), so no popping.
  Push index 2.
  Stack: [-1, 1, 2] (heights at these indices: [_, 1, 5]). maxArea = 2 (unchanged).

• i = 3 (height 6): Current height (6) is >= height at stack top (5 at index 2), so no pop.
  Push index 3.
  Stack: [-1, 1, 2, 3] (heights: [_, 1, 5, 6]). maxArea = 2.

• i = 4 (height 2): Current height (2) is less than height at stack top (6 at index 3). Start popping:

  • Pop index 3. Height = 6. New stack top is index 2. Width = i - stack_top - 1 = 4 - 2 - 1 = 1. Area = 6 × 1 = 6. Update maxArea = 6 (was 2).
  • Now compare current height 2 with new stack top’s height (5 at index 2). 2 < 5, so pop index 2 as well. Height = 5. New stack top is index 1. Width = 4 - 1 - 1 = 2. Area = 5 × 2 = 10. Update maxArea = 10 (was 6, now bigger).
  • Now compare current height 2 with new stack top’s height (1 at index 1). 2 >= 1, so stop popping.
    Push index 4.
    Stack: [-1, 1, 4] (heights: [_, 1, 2]). maxArea = 10.

• i = 5 (height 3): Current height (3) is >= height at stack top (2 at index 4), so no pop.
  Push index 5.
  Stack: [-1, 1, 4, 5] (heights: [_, 1, 2, 3]). maxArea = 10.

• End of array reached. Now pop any remaining bars:

  • Pop index 5: height = 3. New stack top = 4. Width = n - stack_top - 1 = 6 - 4 - 1 = 1. Area = 3 × 1 = 3. maxArea stays 10.
  • Pop index 4: height = 2. New stack top = 1. Width = 6 - 1 - 1 = 4. Area = 2 × 4 = 8. maxArea stays 10.
  • Pop index 1: height = 1. New stack top = -1 (sentinel). Width = 6 - (-1) - 1 = 6. Area = 1 × 6 = 6. maxArea stays 10.
  • Stack is now just sentinel, done.

The maximum area found is 10, which matches the expected result. Notice that each index was pushed and popped at most once, and we calculated areas for rectangles only at the moments necessary (when a bar could extend no further). This efficiency is why the stack solution runs in linear time.

3. Divide and Conquer Approach

Idea: This approach is based on the observation that the largest rectangle either spans the entire width using the shortest bar, or it lies entirely to the left or entirely to the right of the shortest bar. Specifically, if you find the index of the minimum height bar in the histogram, that bar (being the limiting height) defines one potential rectangle covering the whole range. Any other rectangle with greater area must lie on one side of this bar (because including this shortest bar limits the height). This leads to a recursive solution:

• Find the index of the minimum height bar in the current range.
• Compute the area using that bar as the height (height * width_of_range).
• Recursively compute the largest rectangle in the sub-array to the left of that bar, and likewise for the sub-array to the right of that bar.
• The maximum of these three values will be the answer for that range.

Step-by-step Algorithm (Recursively):

1. Define a recursive function that takes a subarray range (start index l and end index r) and returns the largest rectangle area in that range.

2. If l > r (empty range), return 0 (no area).

3. Find minIndex, the index of the smallest height bar in heights[l...r]. (Scanning this range to find the min is O(n) for that range.)

4. Calculate areaWithMin = heights[minIndex] * (r - l + 1). This is the area of the rectangle spanning the whole range with the smallest bar as height.

5. Recursively compute leftArea = largestRectangleArea(l, minIndex - 1) for the subarray to the left of the smallest bar, and rightArea = largestRectangleArea(minIndex + 1, r) for the subarray to the right.

6. Return the maximum of areaWithMin, leftArea, and rightArea.

For example, in Example 1 [2,1,5,6,2,3]:

• The minimum bar in the whole array is 1 at index 1. areaWithMin = 1 * 6 = 6.

• Now solve left side [2] (index 0 alone, area = 2) and right side [5,6,2,3].

• On the right side, in [5,6,2,3] the minimum is 2 at index 4. areaWithMin_right = 2 * 4 = 8. Solve left [5,6] (min=5, area spanning both = 5*2=10) and right [3] (area=3). The right side’s max becomes 10.

• Compare left side (2), right side (10), and whole-range (6): we get 10 as the answer.

This divide-and-conquer strategy typically has a time complexity of O(n log n) on average, since each recursive step splits the range and finding the min is O(n) for the range (similar to QuickSort’s average behavior). However, in the worst case (like an already sorted increasing or decreasing height array), the smallest bar might always be at one end, causing the recursion to split off an empty side and process n-1 bars on the other side each time. In that scenario, the complexity can degrade to O(n^2) (similar to QuickSort’s worst case). To mitigate this, one can use advanced data structures like a Segment Tree or Sparse Table to find the minimum in a range faster than O(n), improving worst-case performance. But implementing those goes beyond a beginner solution – the plain recursive approach is easier to understand. The space complexity is O(n) for the recursion stack in the worst case (and additional O(n) if using a segment tree).

Code Implementation

Python Code: Brute Force (O(n^2))