# Largest Rectangle in histogram





High Level:

Two Methods:

**LeftMost rightMost:**

Traverse through three times.&#x20;

Find longest non-descending sequence left and right.&#x20;

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.
