# Largest Rectangle in Histogram
**Difficulty:** HARD
[External](https://leetcode.com/problems/largest-rectangle-in-histogram)
Canonical: https://scaleengineer.com/dsa/problems/largest-rectangle-in-histogram
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [DoorDash](https://scaleengineer.com/companies/doordash), [Flipkart](https://scaleengineer.com/companies/flipkart), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Myntra](https://scaleengineer.com/companies/myntra), [Roblox](https://scaleengineer.com/companies/roblox), [Uber](https://scaleengineer.com/companies/uber), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [tcs](https://scaleengineer.com/companies/tcs), [Capital One](https://scaleengineer.com/companies/capital-one), [MAQ Software](https://scaleengineer.com/companies/maq-software), [Zynga](https://scaleengineer.com/companies/zynga), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [Zepto](https://scaleengineer.com/companies/zepto), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [oyo](https://scaleengineer.com/companies/oyo), [Zomato](https://scaleengineer.com/companies/zomato)
---
## Problem
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_.

**Example 1:**

![](https://assets.glich.co/dsa/largest-rectangle-in-histogram/image0.jpg) 

**Input:** heights = [2,1,5,6,2,3]
**Output:** 10
**Explanation:** The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

**Example 2:**

![](https://assets.glich.co/dsa/largest-rectangle-in-histogram/image1.jpg) 

**Input:** heights = [2,4]
**Output:** 4

**Constraints:**

* `1 <= heights.length <= 105`
* `0 <= heights[i] <= 104`

# Approaches
## Brute Force Approach
The most straightforward approach is to consider every possible rectangle. We can iterate through all possible pairs of bars and treat them as the left and right boundaries of a rectangle. For each pair, we find the minimum height within that range and calculate the area. The maximum area found among all pairs is the result.
**Time:** O(n^2) · **Space:** O(1)
**Pros:** Simple to understand and implement.; Requires no extra space.
**Cons:** Inefficient for large inputs due to its quadratic time complexity.; Leads to 'Time Limit Exceeded' on most online judges.
### Explanation
This method iterates through each bar of the histogram and considers it as the bar of minimum height for a potential largest rectangle. For each bar `i` with height `h = heights[i]`, we need to find the maximum possible width. This width is determined by extending to the left and right from bar `i` as long as the bars encountered are taller than or equal to `h`.

The algorithm proceeds as follows:
1. Initialize a variable `maxArea` to 0.
2. Iterate through the `heights` array with an index `i` from 0 to `n-1`, where `n` is the number of bars.
3. For each bar `i`, we expand outwards to find the boundaries of the largest rectangle that has `heights[i]` as its height.
   - Find the left boundary: Start a pointer `l` from `i` and move left (`l--`) as long as `l >= 0` and `heights[l] >= heights[i]`.
   - Find the right boundary: Start a pointer `r` from `i` and move right (`r++`) as long as `r < n` and `heights[r] >= heights[i]`.
4. The width of this rectangle is `r - l - 1`.
5. Calculate the area: `area = heights[i] * (r - l - 1)`.
6. Update `maxArea = max(maxArea, area)`.
7. After iterating through all bars, `maxArea` will hold the area of the largest rectangle.

```java
public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        int n = heights.length;
        for (int i = 0; i < n; i++) {
            int left = i;
            while (left - 1 >= 0 && heights[left - 1] >= heights[i]) {
                left--;
            }
            int right = i;
            while (right + 1 < n && heights[right + 1] >= heights[i]) {
                right++;
            }
            int width = right - left + 1;
            maxArea = Math.max(maxArea, heights[i] * width);
        }
        return maxArea;
    }
}
```
### Algorithm
- Initialize `maxArea = 0`.
- Iterate through each bar `i` from `0` to `n-1`.
- For each bar `i`, treat it as the minimum height of a potential rectangle.
- Expand to the left from `i` to find the first bar shorter than `heights[i]`. This determines the left boundary.
- Expand to the right from `i` to find the first bar shorter than `heights[i]`. This determines the right boundary.
- Calculate the width using the left and right boundaries.
- Calculate the area: `heights[i] * width`.
- Update `maxArea` with the maximum area found so far.
- Return `maxArea`.

## Divide and Conquer Approach
A more optimized approach uses the divide and conquer paradigm. The idea is that the largest rectangle in the histogram must be in one of three places:
1.  Entirely in the left half of the histogram.
2.  Entirely in the right half of the histogram.
3.  Crossing the middle of the histogram.

We can recursively find the largest rectangle for the first two cases. The third case, the rectangle crossing the middle, can be found in linear time by expanding from the middle. The overall maximum is the largest of these three values.
**Time:** O(n log n) on average, O(n^2) in the worst case. · **Space:** O(log n) on average, O(n) in the worst case (due to recursion stack).
**Pros:** More efficient than brute force on average.; Demonstrates a classic algorithmic paradigm.
**Cons:** Performance degrades to O(n^2) in the worst-case scenario (e.g., a sorted array).; The recursion depth can be O(n) in the worst case, potentially leading to a stack overflow.
### Explanation
This approach recursively breaks the problem down into smaller subproblems.

The `calculateArea(heights, start, end)` function works as follows:
1. **Base Case:** If `start > end`, it means the segment is empty, so we return 0.
2. **Divide:** Find the index `minIndex` of the shortest bar in the current segment `[start, end]`.
3. **Conquer:** The largest rectangle in the current segment `[start, end]` is the maximum of three possibilities:
   a. The rectangle formed by using the shortest bar `heights[minIndex]` as the height, spanning the entire width of the current segment. Its area is `heights[minIndex] * (end - start + 1)`.
   b. The largest rectangle that lies completely to the left of the shortest bar. This is found by a recursive call: `calculateArea(heights, start, minIndex - 1)`.
   c. The largest rectangle that lies completely to the right of the shortest bar. This is found by another recursive call: `calculateArea(heights, minIndex + 1, end)`.
4. **Combine:** The result for the current segment is the maximum of these three calculated areas.

The initial call would be `calculateArea(heights, 0, heights.length - 1)`.

```java
public class Solution {
    public int largestRectangleArea(int[] heights) {
        return calculateArea(heights, 0, heights.length - 1);
    }

    private int calculateArea(int[] heights, int start, int end) {
        if (start > end) {
            return 0;
        }
        int minIndex = start;
        for (int i = start; i <= end; i++) {
            if (heights[i] < heights[minIndex]) {
                minIndex = i;
            }
        }
        int areaWithMin = heights[minIndex] * (end - start + 1);
        int leftArea = calculateArea(heights, start, minIndex - 1);
        int rightArea = calculateArea(heights, minIndex + 1, end);

        return Math.max(areaWithMin, Math.max(leftArea, rightArea));
    }
}
```
The performance of this approach depends heavily on the position of the minimum element in each segment. If the minimum is always near the center, the problem is split into two roughly equal halves, leading to O(n log n) time. However, if the minimum is always at an edge (e.g., for a sorted array), the subproblems are unbalanced, degrading the performance to O(n^2).
### Algorithm
- Define a recursive function `calculateArea(heights, start, end)`.
- If `start > end`, return 0 (base case).
- Find the index `minIndex` of the minimum height bar in the range `[start, end]`.
- Calculate the area of the rectangle using the minimum bar's height and the full width of the range: `area1 = heights[minIndex] * (end - start + 1)`.
- Recursively call `calculateArea` for the left part: `leftArea = calculateArea(heights, start, minIndex - 1)`.
- Recursively call `calculateArea` for the right part: `rightArea = calculateArea(heights, minIndex + 1, end)`.
- Return the maximum of `area1`, `leftArea`, and `rightArea`.

## Optimal Approach using Monotonic Stack
The most efficient solution uses a monotonic stack. The core idea is to find, for each bar, the first bar to its left and the first bar to its right that are shorter. These are called the 'Previous Less Element' (PLE) and 'Next Less Element' (NLE). The width of the largest rectangle using the current bar as the minimum height is then `(index of NLE) - (index of PLE) - 1`. A monotonic stack (specifically, a monotonically increasing stack of indices) can find these boundaries for all bars in a single pass.
**Time:** O(n) · **Space:** O(n)
**Pros:** Most efficient solution with linear time complexity.; Processes each bar only a constant number of times (pushed and popped once).
**Cons:** Can be less intuitive to understand compared to the brute-force approach.; Requires extra space for the stack.
### Explanation
This approach iterates through the bars and uses a stack to keep track of the indices of bars in increasing order of their heights. When we encounter a bar that is shorter than the bar at the top of the stack, we know we've found the right boundary (the 'Next Less Element') for the bar at the top.

The algorithm works as follows:
1. Initialize an empty stack (to store indices) and `maxArea = 0`.
2. We iterate through the `heights` array, including a virtual bar of height 0 at the end. This final bar ensures that all bars remaining in the stack are processed.
3. For each bar `i` (from 0 to `n`):
   a. While the stack is not empty and the height of the bar at the index on top of the stack is greater than the current bar's height (`heights[i]`, or 0 if `i == n`):
      i. Pop the index `top` from the stack. This is the bar for which we are calculating the maximum area.
      ii. The height of the rectangle is `h = heights[top]`.
      iii. The right boundary is the current index `i`.
      iv. The left boundary is the index of the element now at the top of the stack. If the stack is empty, the left boundary is effectively -1.
      v. The width is `w = stack.isEmpty() ? i : i - stack.peek() - 1`.
      vi. Update `maxArea = Math.max(maxArea, h * w)`.
   b. Push the current index `i` onto the stack.
4. After the loop finishes, `maxArea` will hold the result.

By processing bars this way, every bar `heights[top]` is popped when we find its 'Next Less Element' (`heights[i]`). Its 'Previous Less Element' is the element that was below it in the stack. This allows us to calculate the area for each bar as the minimum height in O(1) time after finding its boundaries.

```java
import java.util.Stack;

public class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            // Use a virtual bar of height 0 at the end to pop all remaining bars from the stack
            int currentHeight = (i == n) ? 0 : heights[i];

            while (!stack.isEmpty() && heights[stack.peek()] > currentHeight) {
                int topIndex = stack.pop();
                int height = heights[topIndex];
                // If stack is empty, it means the popped bar can extend all the way to the left
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }

        return maxArea;
    }
}
```
### Algorithm
- Initialize an empty stack and `maxArea = 0`.
- Append a virtual bar of height 0 to the end of the `heights` array. This helps to clear the stack at the end.
- Iterate through the bars (including the virtual one) with index `i`.
- While the stack is not empty and the height of the bar at the index on top of the stack is greater than the current bar's height:
  - Pop an index `top` from the stack.
  - The height of the rectangle is `heights[top]`.
  - The width is `i` if the stack is empty, otherwise `i - stack.peek() - 1`.
  - Calculate the area and update `maxArea`.
- Push the current index `i` onto the stack.
- Return `maxArea`.

# Solutions
### CSharp

```csharp
using System ; using System.Collections.Generic ; using System.Linq ; public class Solution { public int LargestRectangleArea ( int [] height ) { var stack = new Stack < int >(); var result = 0 ; var i = 0 ; while ( i < height . Length || stack . Any ()) { if (! stack . Any () || ( i < height . Length && height [ stack . Peek ()] < height [ i ])) { stack . Push ( i ); ++ i ; } else { var previousIndex = stack . Pop (); var area = height [ previousIndex ] * ( stack . Any () ? ( i - stack . Peek () - 1 ) : i ); result = Math . Max ( result , area ); } } return result ; } }
```

### Java

```java
class Solution { public int largestRectangleArea ( int [] heights ) { int res = 0 , n = heights . length ; Deque < Integer > stk = new ArrayDeque <>(); int [] left = new int [ n ]; int [] right = new int [ n ]; Arrays . fill ( right , n ); for ( int i = 0 ; i < n ; ++ i ) { while (! stk . isEmpty () && heights [ stk . peek ()] >= heights [ i ]) { right [ stk . pop ()] = i ; } left [ i ] = stk . isEmpty () ? - 1 : stk . peek (); stk . push ( i ); } for ( int i = 0 ; i < n ; ++ i ) { res = Math . max ( res , heights [ i ] * ( right [ i ] - left [ i ] - 1 )); } return res ; } }
```

### Python

```python
''' 枚举每根柱子的高度 h 作为矩形的高度，向左右两边找第一个高度 小于(<) h 的下标 left_i, right_i 那么此时矩形面积为 h * (right_i - left_i - 1)，求最大值即可。 ''' class Solution : def largestRectangleArea ( self , heights : List [ int ]) -> int : n = len ( heights ) stk = [] left = [ - 1 ] * n right = [ n ] * n for i , h in enumerate ( heights ): while stk and heights [ stk [ - 1 ]] >= h : right [ stk [ - 1 ]] = i stk . pop () if stk : left [ i ] = stk [ - 1 ] # same as below: stk[-1] in 'i - stack[-1] - 1' stk . append ( i ) # valid for one element input [3] return max ( h * ( right [ i ] - left [ i ] - 1 ) for i , h in enumerate ( heights )) ############ class Solution : def largestRectangleArea ( self , heights : List [ int ]) -> int : if not heights : return 0 heights . append ( - 1 ) # make for loop running stack = [] ans = 0 for i in range ( 0 , len ( heights )): while stack and heights [ i ] < heights [ stack [ - 1 ]]: currentLowestBarIndex = stack . pop () h = heights [ currentLowestBarIndex ] # stack[-1] is after pop(). why not i-currentLowestBarIndex? # because not working for tie case in the stack, # eg. for input=[4,2,0,3,2,5], expected=6 but output=5 # 向左右两边找第一个高度 小于(<) h 的下标 left_i, right_i # 如果是左右两边都是 大于 h 的下标，那么宽度是 right-left+1 # 但是这里是 小于 h的下标，right-left+1 情况 向左向右 都拓展一个index，多了两个，+1 -2 得 -1 w = i - stack [ - 1 ] - 1 if stack else i ans = max ( ans , h * w ) stack . append ( i ) heights . pop () # restore, pop -1 return ans
```

### CPP

```cpp
class Solution { public: int largestRectangleArea ( vector < int >& heights ) { int res = 0 , n = heights . size (); stack < int > stk ; vector < int > left ( n , - 1 ); vector < int > right ( n , n ); for ( int i = 0 ; i < n ; ++ i ) { while ( ! stk . empty () && heights [ stk . top ()] >= heights [ i ]) { right [ stk . top ()] = i ; stk . pop (); } if ( ! stk . empty ()) left [ i ] = stk . top (); stk . push ( i ); } for ( int i = 0 ; i < n ; ++ i ) res = max ( res , heights [ i ] * ( right [ i ] - left [ i ] - 1 )); return res ; } };
```