# 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.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/deque/largest-rectangle-in-histogram.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.