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

# Largest Rectangle in histogram

High Level:

Two Methods:

**LeftMost rightMost:**

Traverse through three times. 

Find longest non-descending sequence left and right. 

Calculate middle out for each tile.

**Clearing the debris:**

use a stack of indexes to keep track ascending sequences

*rule of traversal:*

while ascending, add to stack

on descend:

while top of stack is >= cur index:

1. pop the top, that's the height
2. find left bound: if the stack is empty: 0, else its the new top of the stack
3. check cur max against height \* (i - left - 1)
4. add cur index to stack

```java
class Solution {
    public int largestRectangleArea(int[] arr) {
        Deque<Integer> stack = new LinkedList<>(); //store indexes
        int result = 0;
        for(int i = 0; i <= arr.length; i++){
            int curHeight = i == arr.length ? 0 : arr[i];
            
            while(!stack.isEmpty() && arr[stack.peekFirst()] >= curHeight){
                int height = arr[stack.pollFirst()];
                int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
                result = Math.max(result, height * (i - left));
            }
            stack.offerFirst(i);
        }
        return result;
    }
}   
```

Details:

**WHY ASCENDING SEQUENCE?**

ex: 12342&#x20;

&#x20;              ^

&#x20;            cur

once we pop out all heights greater or equal to cur. We are **guaranteed** that cur can extend until the new top index.

**Why pop equal size tiles?**

for cases like 2 2 1:

The first 2 needs to be popped, because the *implicit left bound of each tile is tracked by the index at the top of the stack*. (ref: line 10) Therefore without popping the 2 at index 0, we would get two 2x1 rectangles instead of one 2x2 rectangle.