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

Code