Skip to main content
Talentd

Number of Visible People in a Queue - Solution & Explanation

HardArrayStackMonotonic Stack15 min readAsked at: Amazon, Microsoft, Meta +14
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 105
  • 1 <= heights[i] <= 105
  • All the values of heights are unique.

Approach Overview

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 1: Mono Stack Approach

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor ā†’

Approach 2: Brute Force Approach

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.

Code

CJavaScript

C

JavaScript

Complexity

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.

Try this approach in the editor ā†’

Approach 3: Monotonic Stack

We observe that for the i-th person, the people he can see must be strictly increasing in height from left to right.

Therefore, we can traverse the array heights in reverse order, using a stack stk that is monotonically increasing from top to bottom to record the heights of the people we have traversed.

For the i-th person, if the stack is not empty and the top element of the stack is less than heights[i], we increment the count of people the i-th person can see, then pop the top element of the stack, until the stack is empty or the top element of the stack is greater than or equal to heights[i]. If the stack is not empty at this point, it means the top element of the stack is greater than or equal to heights[i], so we increment the count of people the i-th person can see by 1.

Next, we push heights[i] onto the stack and continue to the next person.

After traversing, we return the answer array ans.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array heights.

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Mono Stack Approach

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.

Brute Force Approach

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.

Monotonic Stackā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ScanO(nĀ²)O(1)Good for understanding the visibility rule or when constraints are very small
Monotonic StackO(n)O(n)Optimal solution for large inputs and expected approach in coding interviews

Video Solution

NUMBER OF PEOPLE VISIBLE IN A QUEUE | LEETCODE # 1944 | PYTHON MONOTONIC STACK SOLUTION ā€¢ Cracking FAANG ā€¢ 11,218 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Number of Visible People in a Queue easy or hard?
The problem is labeled Hard on LeetCode because it requires recognizing the monotonic stack pattern. Once the pattern is identified, the implementation is straightforward and runs in linear time.
Number of Visible People in a Queue Python/Java solution
Both Python and Java implementations follow the same monotonic stack logic. Iterate from right to left, pop smaller heights while counting visibility, optionally count one taller blocker, then push the current height. The overall complexity remains O(n).
How to solve Number of Visible People in a Queue in O(n)?
Traverse the array from right to left and maintain a decreasing stack of heights. Pop all shorter heights and count them as visible. If a taller person remains on the stack, they are also visible but block further views. Push the current height to maintain the monotonic property.
What is the best approach for Number of Visible People in a Queue?
The optimal approach uses a monotonic decreasing stack while iterating from right to left. Shorter people are popped because they remain visible but cannot block future visibility. Each element is pushed and popped at most once, giving O(n) time and O(n) space complexity.
Is Number of Visible People in a Queue asked at Google/Amazon/Meta?
This problem represents a common monotonic stack pattern frequently asked in interviews at companies like Amazon, Google, and Meta. Variations involving visibility, next greater elements, and skyline-style problems appear regularly in technical interviews.
What data structure is used in Number of Visible People in a Queue?
A stack is the primary data structure used in the optimal solution. Specifically, a monotonic decreasing stack maintains candidate heights and efficiently determines which people remain visible.
What is the time complexity of Number of Visible People in a Queue?
The brute force approach runs in O(n^2) time because each person scans all people to the right. The optimized monotonic stack approach reduces this to O(n) time since each height is processed once with at most one push and pop operation.

Ready to solve this problem?

Practice Number of Visible People in a Queue with our built-in code editor and test cases.

Practice on FleetCode
Previous

Buildings With an Ocean View

Next

Find Building Where Alice and Bob Can Meet