Number of Visible People in a Queue
Hard · Stack & Strings · Array · Stack · Monotonic Stack
Problem
n people stand in a line, numbered 0 to n - 1 from left to right, and everyone looks to the right. Their heights are given in heights, and all heights are distinct.
Person i can see person j (with i max(heights[i+1], ..., heights[j-1]). Two neighbors always see each other.
Return an array answer where answer[i] is how many people person i can see to their right.
Examples
Input: heights = [10,6,8,5,11,9] Output: [3,1,2,1,1,0]
Person 0 (10) sees 6, 8 and 11; 11 blocks the rest. Person 1 (6) sees only 8. Person 2 (8) sees 5 and 11. Person 3 sees 11, person 4 sees 9, and the last person sees nobody.
Input: heights = [5,1,2,3,10] Output: [4,1,1,1,0]
Person 0 sees 1, 2, 3 and 10, each taller than everyone before them. Persons 1, 2 and 3 each see only their neighbor.
Input: heights = [7] Output: [0]
Nobody stands to the right.
Constraints
- 1 <= n <= 10^5
- 1 <= heights[i] <= 10^5
- all values in heights are distinct
Approaches
- Baseline: scan right from each person — time O(n²), space O(1) beyond the output
Follow-up
What if heights could repeat, and a person of equal height also blocks the view? Then the pop condition becomes stack[-1] <= h for popping, but an equal person is still seen and blocks, so it counts once like a taller one. Getting ties right is the usual trap when moving a monotonic stack between problems.
Related problems
Start free on Cariara · Coding problems · System design studio
