# Largest Rectangle in Histogram

This page explains Java solution to problem `Largest Rectangle in Histogram`

using `Stack `

data structure.

## Problem Statement

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.

**Example 1:****Input**: [2,1,5,6,2,3]

**Output**: 10

### Input:

Histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

### Output:

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

## Solution

If you have any suggestions in below code, please

create a pull request by clicking here.

```
package com.vc.hard;
import java.util.Stack;
class LargestRectangleInHistogram {
public int largestRectangleArea(int[] heights) {
Stack<Integer> st = new Stack<>();
st.push(-1);
int maxHeight = 0;
for(int i = 0; i < heights.length; i++) {
while(st.peek() != -1 && heights[st.peek()] > heights[i]) {
maxHeight = Math.max(maxHeight, heights[st.pop()] * (i - st.peek() - 1));
}
st.push(i);
}
while(st.peek() != -1) {
maxHeight = Math.max(maxHeight, heights[st.pop()] * (heights.length - st.peek() - 1));
}
return maxHeight;
}
}
```

## Time Complexity

O(N) Where

N is number of elements in input array

## Space Complexity

O(N)