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.
This approach uses a stack to maintain a decreasing sequence of heights from right to left. As you iterate the list in reverse, you can calculate how many people each person can see, helped by the stack.
We iterate over the list of heights from right to left while maintaining a stack in which we store indices of the heights in decreasing order. When processing the current person, we pop from the stack as long as the current person's height is greater than the height at the top of the stack, incrementing the number of visible people for the current person. After processing, we add the current index to the stack.
Time Complexity: O(n), as each height is pushed and popped from the stack at most once.
Space Complexity: O(n), due to the use of the stack to store indices.
This is a straightforward approach that checks each pair of people in the queue to determine whether they can see each other. We loop over each person and then loop over every subsequent person to the right to check visibility.
We loop through each person in the array and, for each one, look ahead to see how many people they can view. For each pair, if the next person's height is greater than or equal to the current person's, count them and stop further checks as no subsequent person can be viewed beyond this point.
C
JavaScript
Time Complexity: O(n^2), as you potentially look at each pair of people in the heights list.
Space Complexity: O(1), when not considering the output array.
| Approach | Complexity |
|---|---|
| Mono Stack Approach | Time Complexity: O(n), as each height is pushed and popped from the stack at most once. |
| Brute Force Approach | Time Complexity: O(n^2), as you potentially look at each pair of people in the heights list. |
| 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 |
NUMBER OF PEOPLE VISIBLE IN A QUEUE | LEETCODE # 1944 | PYTHON MONOTONIC STACK SOLUTION • Cracking FAANG • 10,434 views views
Watch 9 more video solutions →Practice Number of Visible People in a Queue with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor