> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/stacks-and-queues/largest-rectangle-in-histogram.md).

# Largest Rectangle in Histogram

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.

\
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.png)

\
The largest rectangle is shown in the shaded area, which has area = `10` unit.

![](https://assets.leetcode.com/uploads/2018/10/12/histogram_area.png)

**Example:**

```
Input: [2,1,5,6,2,3]
Output: 10
```

```java
class Solution {
    public int largestRectangleArea(int[] h) {
        int n = h.length;
        Stack<Integer> st = new Stack<>();
        int[] left = new int[n];
        int[] right = new int[n];
        // finding closest smaller element on left
        for (int i = 0; i < n; i++) {
            while (st.size() != 0 && h[st.peek()] >= h[i]) {
                st.pop();
            }
            if (st.size() == 0)
                left[i] = -1;
            else
                left[i] = st.peek();
            st.push(i);
        }
        st.clear();
        // finding closest smaller element on right
        for (int i = n - 1; i >= 0; i--) {
            while (st.size() != 0 && h[st.peek()] >= h[i]) {
                st.pop();
            }
            if (st.size() == 0)
                right[i] = n;
            else
                right[i] = st.peek();
            st.push(i);
        }
        int max = 0;
        for (int i = 0; i < n; i++) {
            max = Math.max(max, h[i] * (right[i] - left[i] - 1));
        }
        return max;
    }
}
```