Number of Visible People in a Queue

Problem Description

There are n people standing in a queue, numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the i-th person. A person can see another person to their right in the queue if everybody in between is shorter than both of them. Return an array answer of length n where answer[i] is the number of people the i-th person can see to their right in the queue.

Key Insights

• A person can only see those to their right if they are taller than those in between.
• The problem can be efficiently solved using a monotonic stack to keep track of the visible heights.
• Each person can "see" until a taller person blocks the view.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will use a monotonic stack to keep track of the indices of the people in the queue as we iterate from right to left. The stack will help us maintain the order of the heights and determine how many people can be seen by each person.

1. Initialize an array answer with zeroes to store the result.
2. Use a stack to keep track of the indices of the heights.
3. Iterate over the heights from right to left:
   • While the stack is not empty and the current height is greater than the height at the index stored at the top of the stack, pop the stack.
   • The number of people that the current person can see is equal to the size of the stack (which contains only those shorter than the current person).
   • Push the current index onto the stack.
4. Return the answer array.

Code Solutions