Watch 10 video solutions for Number of Visible People in a Queue, a hard level problem involving Array, Stack, Monotonic Stack. This walkthrough by Cracking FAANG has 10,434 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There are n people standing in a queue, and they 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 ith person.
A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).
Return an array answer of length n where answer[i] is the number of people the ith person can see to their right in the queue.
Example 1:
Input: heights = [10,6,8,5,11,9] Output: [3,1,2,1,1,0] Explanation: Person 0 can see person 1, 2, and 4. Person 1 can see person 2. Person 2 can see person 3 and 4. Person 3 can see person 4. Person 4 can see person 5. Person 5 can see no one since nobody is to the right of them.
Example 2:
Input: heights = [5,1,2,3,10] Output: [4,1,1,1,0]
Constraints:
n == heights.length1 <= n <= 1051 <= heights[i] <= 105heights are unique.Problem Overview: You are given an array heights representing people standing in a queue from left to right. For each person, count how many people to their right are visible. A person can see another person if everyone between them is shorter than both. The task is to compute this visibility count for every index.
Approach 1: Brute Force Scan (O(n2) time, O(1) space)
The direct approach checks visibility for each person by scanning everyone to the right. Track the tallest height encountered while moving right. A person becomes visible if their height is greater than all previously scanned people between them and the current observer. If you encounter someone taller than the current person, they are visible but block all further visibility, so the scan stops. This approach uses simple iteration over the array and works fine for small inputs but becomes slow for large queues because every index may scan almost the entire remaining array.
Approach 2: Monotonic Stack (O(n) time, O(n) space)
The optimal solution processes the queue from right to left using a decreasing stack. The stack stores heights of people that may still be visible for someone further left. For each person, repeatedly pop shorter people from the stack. Each popped person is visible because the current person can see over them. If the stack still contains a taller person after popping, that person is also visible but blocks everyone behind them. Push the current height onto the stack so it can act as a blocker for earlier people. Each height is pushed and popped at most once, which gives linear time complexity.
This pattern is a classic monotonic stack use case. The stack maintains a decreasing sequence of heights so visibility decisions become local operations instead of repeated scans. The key insight is that once a shorter person is popped, they will never affect visibility for anyone further left because the current person already dominates them.
Recommended for interviews: Interviewers expect the monotonic stack solution. The brute force version demonstrates that you understand the visibility rule and blocking condition, but it does not scale. Recognizing that repeated right-side scans can be replaced by a decreasing stack shows stronger algorithmic thinking and familiarity with stack-based array patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Scan | O(n²) | O(1) | Good for understanding the visibility rule or when constraints are very small |
| Monotonic Stack | O(n) | O(n) | Optimal solution for large inputs and expected approach in coding interviews |