DSA problem
Number of Visible People in a Queue
There are n people standing in a queue numbered 0 to n - 1 from left to right. You are given an array heights of distinct positive integers where heights[i] is the height of the i-th person. A person at index i can see another person at index j if i < j and min(heights[i], heights[j]) > max(heights[k]) for every k strictly between i and j.
Return an array answer of length n where answer[i] is the number of people the i-th person can see to their right.
The brute force enumerates each pair and checks the "no taller person in between" condition, taking O(n²) time at worst. For n up to 10⁵ we need linear time.
The key observation is that as we scan right-to-left and maintain a monotonic increasing stack of heights to the right of the current index, person i can see exactly:
- every person whose height is shorter than
heights[i](we pop them from the stack — they are all visible toi), - plus, if the stack is still non-empty after popping, one more person — the first one taller than
heights[i]blocksi's view of anyone beyond.
So answer[i] is the number of pops plus (1 if stack is non-empty after the pops, else 0). Each index is pushed and popped at most once, giving an O(n) algorithm overall.
Examples
heights = [10,6,8,5,11,9][3,1,2,1,1,0]heights = [5,1,2,3,10][4,1,1,1,0]heights = [3,1,2][2,1,0]Constraints
- n == heights.length
- 1 <= n <= 10^5
- 1 <= heights[i] <= 10^5
- All the values of heights are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.