Largest poster that fits under a skyline

Stacks and queues Senior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

What does this print?

Python 3.13
heights = [2, 1, 5, 6, 2, 3]
best = 0
for i in range(len(heights)):
    low = heights[i]
    for j in range(i, len(heights)):
        low = min(low, heights[j])
        best = max(best, low * (j - i + 1))
print(best)

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 10

Right: heights 5 and 6 give a 5 by 2 poster.

This O(n²) check gives the answer the stack-based solution must match, and it is how the solution is tested.

Why not the others?
  • B 12. No three neighbours are all at least 4 tall.
  • C 6. A taller single building is beaten by two buildings of height 5 or more.

30-second answer

For each building, the best poster using its full height stretches left and right until a shorter building. A monotonic stack of increasing heights finds both limits: when a shorter building arrives, pop taller ones; the popped building's poster ends here on the right and at the new stack top on the left. Each building is pushed and popped once: O(n) time, and the stack takes O(n) space.

Practise saying it · 90 s. No recording, just a timer

Explain the largest rectangle under a skyline.

Say your answer out loud, then check which of these points you covered:

  • Monotonic increasing stack
  • Pop gives height and both limits
  • Sentinel, O(n)

Deep dive

A sentinel height 0 at the end flushes the stack so every building gets popped.

Checking every pair of ends is O(n²); the stack makes it O(n).

The same routine finds the largest rectangle of 1s in a binary matrix, row by row.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def largest_poster(heights: list[int]) -> int:
    rising: list[int] = []  # indexes with increasing heights
    best = 0
    for i, h in enumerate(heights + [0]):
        while rising and heights[rising[-1]] >= h:
            tall = heights[rising.pop()]
            left = rising[-1] + 1 if rising else 0
            best = max(best, tall * (i - left))
        rising.append(i)
    return best

Common mistakes

  • Computing the width from the popped index instead of the new stack top.
  • Forgetting to flush the remaining buildings at the end.

Senior take & follow-ups

Draw three buildings and walk the pops by hand; the width rule is the part to get right.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you find the largest all-1 rectangle in a grid?

    Show hint

    Build running heights per row and run this routine on each row: O(R·C).

  2. Can you do it with divide and conquer?

    Show hint

    Split at the minimum height: O(n log n) on average, O(n²) worst case.

What each operation costs: Stack · Queue · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.