Largest Banner Under the Skyline
HardStack
Problem
A street is lined with buildings of width 1 standing side by side; heights[i] is the height of building i. A rectangular banner will be hung flat against the facades: it must cover a run of consecutive buildings, its bottom edge on the ground, and it cannot rise above the lowest building in that run.
Return the largest possible banner area.
Example 1
- Input:
- heights = [2, 6, 5, 1, 4]
- Output:
- 10
Covering buildings 1 and 2 at height 5 gives 2 · 5 = 10.
Example 2
- Input:
- heights = [4, 4, 4]
- Output:
- 12
Constraints
- 1 ≤ heights.length ≤ 10^5
- 0 ≤ heights[i] ≤ 10^4
Hint
Show the first hint
In the best banner, some building in the run is the lowest one and sets the height. Fix that building.
Walkthrough
How to approach it
01Clarify before coding
- Can heights be zero? Yes; a zero building splits the street.
- Is the answer large? Up to 10^5 · 10^4 = 10^9, fine for 64-bit integers and JavaScript numbers.
- Is it enough to return the area? Yes, not its position.
02Brute force
For every pair (l, r), take the minimum height in the range (maintained while extending r) and compute min · (r - l + 1).
Cost: O(n²): 5·10^9 pairs for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.