Number of Visible People in a Queue
Last Updated: April 1, 2026
Understanding the Problem
Think of people standing in a line, all facing right. Person i looks to the right and can see person j if nobody standing between them is tall enough to block the view. Specifically, every person between positions i and j must be shorter than both person i and person j.
There are two important observations. First, if person i encounters someone taller than themselves while looking right, that tall person is the last one they can see. Nobody behind a taller person is visible because the taller person blocks the view. Second, person i can see a sequence of people with decreasing heights, followed by at most one person who is taller than themselves.
So the core question becomes: for each person, how many people form a "visible chain" to their right before a taller person blocks everything?
Key Constraints:
1 <= n <= 10^5→ With up to 100,000 people, we need O(n log n) or better. An O(n^2) brute force that checks all pairs would hit 10 billion operations in the worst case.1 <= heights[i] <= 10^5→ All heights are positive integers. No zeros or negatives to worry about.- All heights are unique → This is critical. No two people have the same height, which simplifies the visibility logic. We never have to worry about ties.
Approach 1: Brute Force
Intuition
The simplest approach is to do exactly what the problem says. For each person i, scan every person j to the right and check whether all people between i and j are shorter than both heights[i] and heights[j]. If so, person i can see person j.
But we can simplify this a bit. As person i scans to the right, they keep seeing people as long as those people are shorter than heights[i]. The moment they hit someone as tall or taller, that person is the last visible one. Why? Because that taller person blocks the view of everyone behind them. So for each person, we just scan right, count everyone shorter, and add one more if we find someone taller (then stop).
Algorithm
- Create a result array
answerof lengthn, initialized to zeros. - For each person
ifrom0ton-1:
a. Track the maximum height seen between i and the current person j.
b. For each person j from i+1 to n-1:
- If the maximum height between
iandj(exclusive of endpoints) is less thanmin(heights[i], heights[j]), personican see personj. Incrementanswer[i]. - If
heights[j] >= heights[i], stop scanning. This person blocks the view of everyone behind.
- Return
answer.
Example Walkthrough
Code
- Time Complexity: O(n^2). For each person, we potentially scan all people to their right. In the worst case (strictly decreasing heights), every person scans all the way to the end.
- Space Complexity: O(1). We only use the output array and a few variables. The output array is required by the problem.
For each person, we're scanning rightward through the array and potentially revisiting the same shorter people that earlier persons already scanned past. What if we could process people in a way that each person is visited at most a constant number of times total?
Approach 2: Monotonic Stack (Optimal)
Intuition
Here is the key insight. When person i looks right, they see a sequence of people with strictly decreasing heights (because any taller person would have blocked the shorter ones behind it). At the end of this decreasing sequence, they might also see one person who is taller than themselves, which blocks everything beyond.
This "decreasing sequence followed by a taller blocker" pattern is exactly what a monotonic decreasing stack captures. If we process people from right to left, we maintain a stack of heights in decreasing order. For each person i:
- Pop everyone from the stack who is shorter than
heights[i]. Each popped person is someone that personican see (they form that decreasing sequence). - If the stack is still non-empty after popping, the top element is the first person taller than
i, so personican also see that person. - Push
heights[i]onto the stack.
The monotonic stack maintains the invariant that heights are in decreasing order from bottom to top. This mirrors the visibility rule perfectly. When person i looks right, the people they can see are exactly those in a decreasing sequence (the popped elements) plus the first person who breaks that sequence by being taller (the stack top after popping).
The reason we process right to left is that the stack naturally accumulates people to the right of the current person. When we pop shorter people, we're saying "person i can see these shorter people, and they'll never be visible to anyone further left because person i now blocks them." This is why each element enters and leaves the stack exactly once, giving us linear time.
Algorithm
- Create a result array
answerof lengthn, initialized to zeros. - Create an empty stack.
- Iterate from right to left (from
n-1down to0):
a. While the stack is not empty and the top of the stack is less than heights[i], pop from the stack and increment answer[i]. Each pop represents a shorter person that person i can see.
b. If the stack is still not empty, increment answer[i] by 1. The stack top is the first taller person, and person i can see them too.
c. Push heights[i] onto the stack.
- Return
answer.
Example Walkthrough
Code
- Time Complexity: O(n). Each of the n heights is pushed onto the stack exactly once and popped at most once. The total number of push and pop operations across all iterations is at most 2n.
- Space Complexity: O(n). The stack can hold up to n elements in the worst case (when heights are strictly increasing from left to right).