# Largest Rectangle

Stack: pop then update.

*-- The question is from Hacker Rank.*

# Question

Given $n$ integers, each representing the height of building $i$ ($1 \le i \le n$), calculate the area of the largest rectangle that can be formed with those buildings.

# Rough Sketch

Maintain the following variables as you process the series of building heights.

- $\textit{largest}$: the area of the largest rectangle until building $i$
- $\textit{stack}$: a stack of building height and the starting building number

Iterate through the buildings

### Case 1: The current building is higher than the previous building

Just push to the stack.

$$\textit{stack} = [(\text{height, starting building no.})] = [(1, 1), (2, 2), (4, 3)]$$

### Case 2: The current building is lower than the previous building

Calculate the area of the rectangle formable with the previous building and update the $\textit{largest}$.

```
largest = 4 * 1 = 4
```

Now that you cannot form a rectangle whose height is greater than 3 due to building 4, you can think of the current state as the following.

Update the stack accordingly.

$$\textit{stack} = [(\text{height, starting building no.})] = [(1, 1), (2, 2), (3, 3)]$$

Return $\textit{largest}$ at the end of the iteration.

(The largest rectangle in the example has an area of 12.)