Visible Heads in a Queue
HardStack
Problem
People stand in a single-file queue, all facing the front, which is the right end of the array. heights[i] is the height of person i; all heights are distinct.
Person i can see person j > i if everyone standing strictly between them is shorter than both of them. Return, for each person, how many people they can see in front of them.
Example 1
- Input:
- heights = [7, 3, 5, 2, 8, 4]
- Output:
- [3, 1, 2, 1, 1, 0]
Person 0 (7) sees 3, 5 and 8; 2 is hidden behind 5, and 4 is hidden behind 8. Person 2 (5) sees 2 and 8.
Example 2
- Input:
- heights = [5, 1, 2, 3, 10]
- Output:
- [4, 1, 1, 1, 0]
Constraints
- 1 ≤ heights.length ≤ 10^5
- 1 ≤ heights[i] ≤ 10^5
- All heights are distinct
Hint
Show the first hint
Which people in front of person i are candidates at all? Think about who blocks whom.
Walkthrough
How to approach it
01Clarify before coding
- Are heights distinct? Yes, so there are no ties to resolve.
- Can someone see past a taller person? No: a person between them that is taller than either blocks the view.
- Is the adjacent person always visible? Yes, there is nobody in between.
02Brute force
For each i, walk right keeping the tallest person seen so far; j is visible when every person between is shorter than both i and j. Stop once someone taller than i appears.
Cost: O(n²) in the worst case (e.g. a very tall person at the back): 5·10^9 steps 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.