Solution: Number of Visible People in a Queue

Statement

You are given an array heights representing n people standing in a queue, numbered from 0 to n - 1 from left to right. Each element heights[i] denotes the height of the person at position i. All heights are distinct.

A person at position i can see a person at position j (i < j) to their right if every person between them is shorter than both heights[i] and heights[j].

Formally, person i can see person j if:

• $i < j$ and $min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1])$

Your task is to return an array answer of length n, where answer[i] is the number of people that person i can see to their right in the queue.

Constraints:

• $1 \leq$ n $\leq 1000$

• $1 \leq$ heights[i] $\leq 1000$

• All elements in heights are unique.

Solution

Each person in the queue can only see those standing to their right. Their line of sight extends as long as the people ahead are shorter than themselves. The moment they encounter a taller or equal-height person, their view is blocked beyond that point, but this taller or equal-height person is still visible.

To determine how many people each individual in a queue can see in front of them, we use a monotonic decreasing stack. The fundamental idea is that a person can see another person ahead only if all individuals in between are shorter. We iterate through the queue in reverse (from the end to the start), maintaining a stack that strictly holds heights in decreasing order. For each person, we pop from the stack as long as the height at the top is shorter than the current person’s height—with each pop, we increment the count of visible people by one, because shorter individuals are directly visible and do not obstruct the view. Once we encounter a taller or equal-height person, we stop popping and count that individual as visible too, as they are the last person in sight before the view is blocked. After visibility is counted, we push the current person’s height onto the stack. This push operation, following the popping of all shorter people, naturally restores the decreasing order of the stack—no explicit reordering is needed.

The steps of the algorithm are as follows:

1. Initialize an empty stack to maintain the decreasing order of heights.

2. Initialize an answer array of the same length as heights, filled with 0, to store the number of visible people for each position.

3. Traverse the heights array from right to left, and for each person at index i:

   1. While the stack is not empty and the top of the stack (stack.peek()) is shorter than the current person (heights[i]):

      1. Pop the top of the stack (this person is visible to i).

      2. Increment answer[i] by 1.

   2. After popping shorter people, if the stack is not empty, it means:

      1. There is still a taller or equal person at the top.

      2. This person is also visible, so increment answer[i] by 1.

   3. Push heights[i] onto the stack for future comparisons.

4. Return the answer array after the traversal is complete.

Let’s look at the following illustration to get a better understanding of the solution: