# Largest Rectangle in Histogram

Given an array of integers A of size N. A represents a histogram i.e A[i] denotes height of
the ith histogram’s bar. Width of each bar is 1.

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

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

Find the area of largest rectangle in the histogram.

Input Format

```The only argument given is the integer array A.
```
Output Format

```Return the area of largest rectangle in the histogram.
```
For Example

```Input 1:
A = [2, 1, 5, 6, 2, 3]
Output 1:
10
Explanation 1:
The largest rectangle is shown in the shaded area, which has area = 10 unit.```
Method:

Maintain a stack that keeps track of the indices of elements that are increasing, when we see an element that is smaller than the top of the stack, we can start calculating the areas. The difficulty is in determining the left bound, after we pop the top of the stack, the left bound can be determined by the current top + 1, because current top is smaller or equal to the element we popped, thus current top + 1 must be greater than or equal to the element we popped.

6 2 5 4 5 (0)

for example, when we are popping 4, the previous 5 is not in the stack because it was already popped, thus the next element in the stack is 2 (index 1), so the left bound is 1 + 1 = 2

Solution:

Time: O(n)
Space: O(n)

```public class Solution {
public int largestRectangleArea(ArrayList<Integer> A) {
// 6 2 5 4 5
// index stack
Deque<Integer> stack = new ArrayDeque<>();
int area = 0;