HardArrayStackMonotonic StackUpdated Sep 2026

1944. Number of Visible People in a Queue

Asked at Rippling

Difficulty

Hard

Time

O(n)

Space

O(n)

Pattern

Array

Companies

1

Problem

There are n people in a queue, numbered 0 to n - 1 from left to right. Each person has a unique height, given in the array heights, where heights[i] is the height of person i.

Person i can see person j to their right (i < j) only if every person standing between them is shorter than both of them. In other words, the shorter of the two people must be taller than the tallest person in between.

Return an array answer of length n, where answer[i] is the number of people person i can see to their right. The last person sees nobody, so answer[n-1] is always 0.

Who can person 0 see?

heights10685119012345person 0Green cells are the people person 0 can see: 6, 8 and11.answer312110012345The final answer array: each cell counts the visiblepeople to the right.
Person 0 (height 10) sees 6, 8 and 11, but the 5 between 8 and 11 is shorter than both, so it does not block the view.

Constraints

  • ●n == heights.length
  • ●1 <= n <= 10^5
  • ●1 <= heights[i] <= 10^5
  • ●All values in heights are unique

Examples

Example 1
Inputheights = [10,6,8,5,11,9]
Output[3,1,2,1,1,0]
WhyPerson 0 (height 10) sees 6, 8 and 11 — the 5 in between is shorter than both 10 and 11, so it does not block. Person 1 (height 6) sees only 8, because 8 is taller and blocks everyone after. Person 2 (height 8) sees 5 and 11. Person 3 (height 5) sees 11. Person 4 (height 11) sees 9. Person 5 sees no
Example 2
Inputheights = [5,1,2,3,10]
Output[4,1,1,1,0]
WhyPerson 0 (height 5) sees everyone to the right: 1, 2, 3 are all shorter, and 10 is taller with only shorter people in between. Person 1 (height 1) sees only 2, since 2 is taller and blocks the rest. Person 2 (height 2) sees only 3. Person 3 (height 3) sees only 10. Person 4 sees nobody.

Asked At

1 companies
CompanyDifficulty
RipplingHardView all Rippling questions →

How to Think About It

1

Brute force: for each person, scan rightward counting visible people — O(n^2)

2

Notice that once a taller person blocks the view, all shorter people behind are also hidden

3

Maintain a stack of people in decreasing height order

4

For each person, pop all shorter people from the stack and count them as visible

5

After popping, if stack is not empty, one more person (the next taller) is visible

Optimal Approach

Use a monotonic decreasing stack. Iterate from right to left. For each person, pop all stack elements smaller than them (those people are visible because no one taller blocks). Count those pops. If the stack still has elements after popping, one more taller person is visible. Push the current person onto the stack. This gives O(n) time since each person is pushed and popped at most once.

Monotonic stack from right to left

stack911← topBefore person 2 (height 8): stack holds 9 then 11,decreasing from bottom to top.stack11← topPerson 2 pops 9 (shorter, so visible) and then sees 11on top — 2 visible people total.pop each shorter person → count itif stack not empty → +1 for the taller onepush current person
We scan from the right, keeping a stack of people in decreasing height order. Shorter people get popped and counted; one taller person may remain on top.
ComplexityTime O(n)Space O(n)Each person is pushed onto the stack once and popped at most once, so the total work is linear; the stack can hold up to n people.

What Trips People Up in Real Interviews

1

Clarify what "visible" means — shorter people are counted, taller person at the end is counted too

2

Edge cases: last person always sees 0, descending queue means everyone sees 1

3

The stack stores indices, not heights, to return results in correct order

4

Distinguish between the people popped (all counted) and the top of stack after (one counted)

5

Dry run with [10,6,8,5,11,9] to verify understanding of the two-phase count

Solution Code

O(n) time
class Solution:
    def canSeePersonsCount(self, heights: list[int]) -> list[int]:
        n = len(heights)
        result = [0] * n
        stack = []
        for i in range(n - 1, -1, -1):
            visible = 0
            while stack and stack[-1] < heights[i]:
                stack.pop()
                visible += 1
            if stack:
                visible += 1
            result[i] = visible
            stack.append(heights[i])
        return result

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Number of Visible People in a Queue problem?

Given n people standing in a queue where each person has a unique height, find for each person how many other people can be seen to their right. A person can see another person if they are shorter and all people between them are shorter than both. Return an array where answer[i] is the number of people person i can see.

How do you solve Number of Visible People in a Queue?

The optimal approach runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Number of Visible People in a Queue?

Number of Visible People in a Queue is asked at Rippling. It is a hard difficulty problem.

What are common mistakes on Number of Visible People in a Queue?
  • Clarify what "visible" means — shorter people are counted, taller person at the end is counted too
  • Edge cases: last person always sees 0, descending queue means everyone sees 1
  • The stack stores indices, not heights, to return results in correct order
  • Distinguish between the people popped (all counted) and the top of stack after (one counted)
  • Dry run with [10,6,8,5,11,9] to verify understanding of the two-phase count