Number of Visible People in a Queue
Asked at Rippling
Problem
Given n people standing in a queue where each person has a unique height, find for each person how many other people can be seen to their right. A person can see another person if they are shorter and all people between them are shorter than both. Return an array where answer[i] is the number of people person i can see.
Asked At
| Company | Difficulty | |
|---|---|---|
| Rippling | HARD | View all Rippling questions → |
How to Think About It
Brute force: for each person, scan rightward counting visible people — O(n^2)
Notice that once a taller person blocks the view, all shorter people behind are also hidden
Maintain a stack of people in decreasing height order
For each person, pop all shorter people from the stack and count them as visible
After popping, if stack is not empty, one more person (the next taller) is visible
Optimal Approach
Use a monotonic decreasing stack. Iterate from right to left. For each person, pop all stack elements smaller than them (those people are visible because no one taller blocks). Count those pops. If the stack still has elements after popping, one more taller person is visible. Push the current person onto the stack. This gives O(n) time since each person is pushed and popped at most once.
What Trips People Up in Real Interviews
Clarify what "visible" means — shorter people are counted, taller person at the end is counted too
Edge cases: last person always sees 0, descending queue means everyone sees 1
The stack stores indices, not heights, to return results in correct order
Distinguish between the people popped (all counted) and the top of stack after (one counted)
Dry run with [10,6,8,5,11,9] to verify understanding of the two-phase count
Solution Code
class Solution:
def canSeePersonsCount(self, heights: list[int]) -> list[int]:
n = len(heights)
result = [0] * n
stack = []
for i in range(n - 1, -1, -1):
visible = 0
while stack and stack[-1] < heights[i]:
stack.pop()
visible += 1
if stack:
visible += 1
result[i] = visible
stack.append(heights[i])
return resultFrequently Asked Questions
What is the Number of Visible People in a Queue problem?
Given n people standing in a queue where each person has a unique height, find for each person how many other people can be seen to their right. A person can see another person if they are shorter and all people between them are shorter than both. Return an array where answer[i] is the number of people person i can see.
How do you solve Number of Visible People in a Queue?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Number of Visible People in a Queue?
Number of Visible People in a Queue is asked at Rippling. It is a hard difficulty problem.
What are common mistakes on Number of Visible People in a Queue?
- Clarify what "visible" means — shorter people are counted, taller person at the end is counted too
- Edge cases: last person always sees 0, descending queue means everyone sees 1
- The stack stores indices, not heights, to return results in correct order
- Distinguish between the people popped (all counted) and the top of stack after (one counted)
- Dry run with [10,6,8,5,11,9] to verify understanding of the two-phase count