84. Largest Rectangle in Histogram - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

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:

A Brute Force solution that checks all possible rectangles (O(n^2) time).
An Optimized Stack-Based solution that uses a monotonic stack to achieve O(n) time.
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:

Initialize maxArea = 0.
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.
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:

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.
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.)
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):

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.
If l > r (empty range), return 0 (no area).
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.)
Calculate areaWithMin = heights[minIndex] * (r - l + 1). This is the area of the rectangle spanning the whole range with the smallest bar as height.
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.
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))

Python3

. . . .

Python Code: Stack-Based (O(n))

Python3

. . . .

Python Code: Divide and Conquer (O(n log n) average)

Python3

. . . .

Java Code (All Approaches in one class)

Java

. . . .

All approaches produce the correct result for this example, though their performance will differ on larger inputs.

Complexity Analysis

Let’s summarize the time and space complexities for each approach:

Brute Force Approach:
- Time Complexity: ~O(n²) in the optimized implementation. We use two nested loops and do O(1) work (min height update and area calc) inside, so roughly proportional to $n(n+1)/2 = O(n^2)$ . (A truly naive triple-loop approach would be O(n³), but we avoid that by tracking the minimum on the fly.)
- Space Complexity: O(1) extra space (just a few variables for tracking, no significant extra memory).
Stack-Based Approach:
- Time Complexity: O(n). Each bar is pushed onto the stack once and popped at most once, so the total operations are proportional to 2n in the worst case. This linear complexity holds even for worst-case height patterns, making it very efficient for large inputs.
- Space Complexity: O(n). In the worst case (e.g., increasing heights), the stack could hold all bar indices at once. We also use a few variables for area calculations. Thus, additional space grows linearly with input size.
Divide and Conquer Approach:
- Time Complexity: O(n log n) on average , but O(n²) in the worst case. The average case assumes that the chosen minimum splits the problem roughly in half each time (like median-of-heights pivot behavior), similar to QuickSort. But a pathological case (like an array sorted by height) will lead to very unbalanced splits (one side of recursion of size n-1, then n-2, etc.), resulting in quadratic time. Using a Segment Tree or other range-min query structure can ensure O(n log n) worst-case by finding minima faster, but that adds complexity.
- Space Complexity: O(n) for recursion stack in the worst case (every bar causing a recursive call). No additional arrays are used aside from recursion and some variables, so it’s O(n) auxiliary space (or more precisely O(h) where h is recursion depth, which is O(n) worst-case).

In practice, the stack-based approach is the preferred solution due to its linear time performance and moderate use of memory.

Step-by-Step Walkthrough (Stack Approach)

To further solidify the understanding, let’s walk through the stack-based algorithm on a sample input step by step, keeping track of the stack and areas calculated at each stage. We’ll use the array [2, 1, 5, 6, 2, 3] (Example 1) again:

Initialize an empty stack and maxArea = 0. We use a sentinel value -1 on the stack to represent an imaginary bar of height 0 at index -1 (this simplifies width calculations at boundaries).

i = 0 (height = 2):
Stack = [-1]. The stack is empty (ignoring sentinel) or the top is a sentinel, so we push index 0.
Stack now: [-1, 0] (meaning indices [-1, 0] are in stack; height at 0 is 2).
maxArea = 0 (no area calculated yet).
i = 1 (height = 1):
Compare height 1 with height at stack top (index 0 has height 2). Since 1 < 2, the bar at index 0 can’t extend to i=1.
We pop index 0 from stack. Now stack top becomes -1 (sentinel).
Height = 2 (at popped index). The width of rectangle with this height goes from index 0 to index 0 (because sentinel -1 indicates no taller bar on left). Width = i - (-1) - 1 = 1.
Area = 2 × 1 = 2. Update maxArea = 2 (was 0). (We handled a remaining bar from stack).
Now height 1 is not less than any bar on stack top (stack top is sentinel now), so push index 1.
Stack: [-1, 1] (heights: sentinel, 1).
maxArea = 2.
i = 2 (height = 5):
Compare 5 with height at stack top (index 1 has height 1). 5 >= 1, no popping needed (the current bar is taller, so it can stay on stack).
Push index 2.
Stack: [-1, 1, 2] (heights at these indices: 0 (sentinel), 1, 5).
maxArea = 2.
i = 3 (height = 6):
Compare 6 with height at stack top (index 2 has height 5). 6 >= 5, no pop.
Push index 3.
Stack: [-1, 1, 2, 3] (heights: 0, 1, 5, 6).
maxArea = 2.
i = 4 (height = 2):
Compare 2 with height at stack top (index 3 has height 6). 2 < 6, so pop index 3.
- Popped 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 (previously 2).
  Now compare 2 with height at new stack top (index 2 has height 5). 2 < 5, so pop index 2.
- Popped index = 2, height = 5. New stack top is index 1.
  Width = i - stack_top - 1 = 4 - 1 - 1 = 2.
  Area = 5 × 2 = 10. Update maxArea = 10 (previously 6, now larger).
  Now compare 2 with height at new stack top (index 1 has height 1). 2 >= 1, so stop popping.
  Push index 4.
  Stack: [-1, 1, 4] (heights: 0, 1, 2).
  maxArea = 10.
i = 5 (height = 3):
Compare 3 with height at stack top (index 4 has height 2). 3 >= 2, no pop.
Push index 5.
Stack: [-1, 1, 4, 5] (heights: 0, 1, 2, 3).
maxArea = 10.
End of array (i = n): Now we pop all remaining bars in stack:
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 (since 3 < 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.
Width = 6 - (-1) - 1 = 6.
Area = 1 × 6 = 6. maxArea stays 10.
Stack is now just sentinel. Done.

We have computed all possible candidate rectangles in the process. The largest area found is 10. This matches our expectations and illustrates how the algorithm efficiently handled each bar exactly once, avoiding redundant checks. Importantly, we took care to pop all remaining bars at the end and calculate their areas, and we correctly calculated widths using the indices around the popped bar.

Common Mistakes & Edge Cases

Common Pitfalls to Avoid:

Forgetting to process remaining stack at the end (Stack approach): One of the most frequent mistakes is to finish the loop over bars and forget to clear out the stack. Any indices left in the stack mean those bars never encountered a smaller bar to the right, so they can extend to the end of the histogram. We must pop and calculate areas for them after the main loop. Neglecting this will usually lead to an underestimate of the max area.
Incorrect width calculation in stack method: When popping from the stack, make sure to compute the width correctly. The width goes from the index just after the new top of stack to the index just before the current index (or end of array if cleaning up at the end). Off-by-one errors are common here. Using a sentinel (like -1) helps simplify this logic, because when the stack becomes empty you can treat the width as the full i or n. Double-check formulas like width = rightIndex - leftIndex - 1 to ensure leftIndex and rightIndex are chosen correctly.
Poor choice of pivot in divide-and-conquer: If always choosing the global minimum for the entire range, the algorithm is correct but can be slow in worst cases. While this isn’t exactly a “mistake” in correctness, it is a performance pitfall. Be aware that a sorted input (all increasing or all decreasing heights) will make the divide-and-conquer recurse n times (like a skewed tree), leading to O(n²) time. In an interview or contest, this might time out for large n. One way to mitigate this is to randomize the choice of the splitting bar or use segment trees to optimize min-finding.
Brute force inefficiencies: If you implement brute force with three nested loops (computing min height inside the j loop for each i, k loop inside j), it will be O(n³) and definitely too slow for large inputs. The mistake here is not optimizing the min-height retrieval. As described, you should carry forward the min height as you increment j, or alternatively, consider the “expand around each bar” method (which is another O(n²) strategy where for each bar you expand left and right until a smaller bar is hit). Always double-check the order of growth – with n up to 100k, O(n²) is borderline (10^10 operations worst-case) and likely not feasible, so prefer the O(n) stack solution.
Edge cases with very small or large inputs:
- If there is only one bar (n=1), the answer is simply the height of that bar. Make sure your code handles n=1 (all approaches do naturally, but be careful with indices in divide-and-conquer and stack flush logic).
- If all bars have the same height, say [5,5,5,5], the largest rectangle is the entire histogram (height 5 over width 4 = 20). A mistake here would be if a stack algorithm inadvertently popped equal heights incorrectly. Many implementations choose to pop when the current bar is strictly lower (>) than stack top to handle equal heights by extending the width, but if you pop on >= (as our code does), it still works because you compute areas for equal bars in sequence – just be consistent and understand your choice.
- If there are bars of height 0 (allowed by constraints), these effectively break the histogram into parts (since a height 0 bar can’t contribute to any area). Ensure the algorithms handle 0 gracefully. The stack approach will pop everything when a 0 is encountered, resetting the stack to sentinel (which is correct). The brute force and D&C handle 0 as just another height (a rectangle including a 0 height is 0 area, which won’t be max unless everything is zero). If all bars are 0, the answer is 0.
- Very large number of bars (near 100k) – only the O(n) solution will be efficient enough. The O(n²) will time out and potentially run out of time (and memory if using Python lists heavily). The D&C might also time out or recurse too deep (Python recursion depth limits might be hit if ~100k recursion calls happen for a sorted input). In Java, deep recursion could cause stack overflow. One should be mindful of recursion limits or use an iterative simulation if implementing D&C for very large n.

Summary of edge cases: single element, all elements equal, presence of zeros, strictly increasing or decreasing sequences (worst-case for some algorithms), and empty input (though here length>=1 by constraint). Our implementations consider these cases (e.g., stack uses sentinel so even an all increasing sequence just leaves them and then pops all at end correctly, and the recursion base case handles empty subranges).

Alternative Variations

This histogram rectangle problem is a classic that relates to several variations and other computational problems:

Maximal Rectangle in a Binary Matrix: This is a 2D extension of our problem. You are given a grid of 0s and 1s, and you need to find the largest rectangle consisting entirely of 1s. A common approach for that problem is to reuse the largest rectangle in a histogram solution. You can treat each row of the matrix as the base of a histogram – for each cell, compute the “height” of consecutive 1s up to that row. Then for each row, solve the largest rectangle under that histogram. This effectively applies the histogram algorithm row by row to build up the maximal rectangle. LeetCode problem 85 Maximal Rectangle is exactly this, and it uses the solution of problem 84 as a subroutine.
Trapping Rain Water: This is another well-known problem (LeetCode 42) that, at first glance, is about histograms – it asks how much water can be trapped between the bars. While the goal is different (measuring water instead of area), it’s related in that it uses the concept of boundaries and can be solved with a stack or two-pointer technique. The stack approach for trapping rain water is somewhat analogous – you pop until you find a lower height to form a container. So both problems teach the technique of using a stack to handle “next greater/smaller element” logic.
Container With Most Water: (LeetCode 11) This problem gives two vertical lines and wants the most water between them. It’s not exactly a contiguous histogram requirement (any two lines can form the container), and it’s optimally solved with a two-pointer approach, not a stack. However, conceptually it’s about maximizing area under constraints (here width is the distance between lines and height is the min of the two lines). It’s a one-dimensional two-pointer variant, whereas largest rectangle in histogram is one-dimensional but requires contiguity.
Monotonic Stack Pattern: The stack approach used in this problem is an example of the monotonic stack pattern. Many problems boil down to finding the “next greater element” or “next smaller element” to the left or right of each element. This histogram problem specifically looks for next smaller to left and right. Other problems that use similar ideas include “Sum of Subarray Minimums” (where you find next smaller elements to determine contribution of each element as minimum of subarrays) and “Daily Temperatures” or “Next Greater Element” (where you find next greater to the right). The context is different, but mastering the monotonic stack here will help in those problems too. Essentially, the algorithm we used can be adapted to compute arrays of “previous smaller element index” and “next smaller element index” for each bar, which is a common sub-problem in various tasks.
Segment Tree / Sparse Table Applications: The divide-and-conquer approach hints at another data structure: if we had a structure that can query the minimum in any range quickly (like a Segment Tree or Sparse Table), we could implement a divide-and-conquer that chooses the minimum in O(1) or O(log n) and potentially get O(n log n) guaranteed. Segment trees themselves are built with divide-and-conquer. While this might be overkill for this specific problem (since the O(n) stack solution exists), it’s a useful approach in scenarios where a similar divide-and-conquer is needed but a monotonic stack solution isn’t obvious. It’s also a good exercise in algorithm design and shows the connection between this problem and range queries in arrays.

In summary, Largest Rectangle in Histogram is not an isolated puzzle – it’s deeply connected to a family of algorithmic techniques (monotonic stacks, divide-and-conquer with range queries) and is a building block for more complex problems like finding submatrices or trapping water. Recognizing these connections can help you apply the learned solution in new contexts.

To strengthen your understanding, you can practice the following related LeetCode problems:

85. Maximal Rectangle: Find the largest rectangle of 1’s in a 2D binary matrix. (Uses the histogram logic on each row).
42. Trapping Rain Water: Compute how much water can be trapped between bars of heights (related to histogram silhouette).
11. Container With Most Water: Find two lines that can hold the most water (two-pointer technique, concept of max area).
739. Daily Temperatures: For each day’s temperature, find how many days until a warmer temperature. (Monotonic stack for next greater element).
907. Sum of Subarray Minimums: Find the sum of the minimum values of all subarrays of an array. (Uses a monotonic stack to find spans of influence for each element as a minimum, somewhat analogous to how we find areas for each bar).

84. Largest Rectangle in Histogram - Detailed Explanation

Problem Statement

Hints

Multiple Approaches

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

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

3. Divide and Conquer Approach

Code Implementation

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

Python Code: Stack-Based (O(n))

Python Code: Divide and Conquer (O(n log n) average)

Java Code (All Approaches in one class)

Complexity Analysis

Step-by-Step Walkthrough (Stack Approach)

Common Mistakes & Edge Cases

Alternative Variations

Related Problems for Further Practice