AlgoMaster Logo

Number of Visible People in a Queue

hardFrequency6 min readUpdated June 23, 2026

Understanding the Problem

People stand 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. Every person between positions i and j must be shorter than both person i and person j.

Two observations drive every approach below. 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, the people that person i can see form a sequence of strictly decreasing heights, followed by at most one person who is taller than person i.

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

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.

The two observations above let us scan more directly. As person i scans to the right, they keep seeing people as long as those people are shorter than heights[i]. The first person who is as tall or taller is the last visible one, since that person blocks the view of everyone behind them. So for each person, we scan right, count everyone shorter than heights[i] that is also taller than everyone in between, add one more if we reach a taller person, then stop.

Algorithm

  1. Create a result array answer of length n, initialized to zeros.
  2. For each person i from 0 to n-1:
    • Track the maximum height seen between i and the current person j.
    • For each person j from i+1 to n-1:
      • If the maximum height between i and j (exclusive of endpoints) is less than min(heights[i], heights[j]), person i can see person j. Increment answer[i].
      • If heights[j] >= heights[i], stop scanning. This person blocks the view of everyone behind.
  3. Return answer.

Example Walkthrough

1i=0, height=10: scan right to find visible people
0
i
10
1
6
j
2
8
3
5
4
11
5
9
1/6

Code

The brute force repeats work: each person scans rightward through the array and revisits the same shorter people that earlier persons already scanned past. The next approach processes people so that each one is pushed and popped at most once, bringing the total work down to linear.

Approach 2: Monotonic Stack (Optimal)

Intuition

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.

A monotonic decreasing stack captures this "decreasing sequence followed by a taller blocker" pattern directly. Processing people from right to left, we maintain a stack of heights in decreasing order. For each person i:

  1. Pop everyone from the stack who is shorter than heights[i]. Each popped person is someone that person i can see (they form that decreasing sequence).
  2. If the stack is still non-empty after popping, the top element is the first person taller than i, so person i can also see that person.
  3. Push heights[i] onto the stack.

Algorithm

  1. Create a result array answer of length n, initialized to zeros.
  2. Create an empty stack.
  3. Iterate from right to left (from n-1 down to 0):
    • 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.
    • 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.
    • Push heights[i] onto the stack.
  4. Return answer.

Example Walkthrough

1Start from right. i=5, height=9. Stack empty, answer[5]=0
0
10
1
6
2
8
3
5
4
11
5
9
i=5
1/7

Code