> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/largest-rectangle-in-histogram.md).

# 84. Largest Rectangle in Histogram

### Description

Given *n* non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

![](https://assets.leetcode.com/uploads/2018/10/12/histogram.png)\
Above is a histogram where width of each bar is 1, given height = `[2,1,5,6,2,3]`.

![](https://assets.leetcode.com/uploads/2018/10/12/histogram_area.png)\
The largest rectangle is shown in the shaded area, which has area = `10` unit.

### Constraints

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/largest-rectangle-under-histogram/)
* [Leetcode](https://leetcode.com/problems/largest-rectangle-in-histogram/)
* [ProgramCreek](https://www.programcreek.com/2014/05/leetcode-largest-rectangle-in-histogram-java/)
* [YouTube](https://youtu.be/ZmnqCZp9bBs)

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** \[2, 1, 5, 6, 2, 3]

**Output:** 10
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n^2). Every possible pair is considered.
 * Space complexity : O(1). No extra space is used.
 */

 public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minheight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minheight = Math.min(minheight, heights[j]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(n). nn numbers are pushed and popped.
 * Space complexity : O(n). Stack is used.
 */

class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights == null || heights.length == 0) return 0;
        
        Stack<Integer> stack = new Stack<>();
        int i = 0, area = 0;
        
        while(i < heights.length) {
            if(stack.isEmpty() || heights[stack.peek()] <= heights[i]) {
                stack.add(i++);
            } else {
                area = Math.max(area, calculateArea(stack, heights, i));
            }
        }
        
        while(!stack.isEmpty()) {
            area = Math.max(area, calculateArea(stack, heights, i));
        }
        
        return area;
    }

    private int calculateArea(Stack<Integer> stack, int[] heights, int i) {
        int top = stack.pop();
        int height = heights[top];
        int weight = (stack.isEmpty())? i: (i-stack.peek()-1);
        return height * weight;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*