Number of Visible People in a Queue: Monotonic Stack

June 6, 20267 min read

leetcodeproblemhardarraysstacks

LeetCode's Number of Visible People in a Queue (problem 1944) is a hard-rated monotonic stack problem that tests whether you can count visible elements rather than just find the next greater one. If you have solved Daily Temperatures or Next Greater Element, this problem builds directly on that foundation, but with a twist in the counting logic.

The problem

You are given an array heights representing the heights of people standing in a queue from left to right. Person i can see person j (where j > i) if every person between them is strictly shorter than both heights[i] and heights[j]. Return an array where each entry is the number of people that person i can see to their right.

Input:  heights = [10, 6, 8, 5, 11, 9]
Output: [3, 1, 2, 1, 1, 0]

Person 0 (height 10) can see person 1 (height 6), person 2 (height 8), and person 4 (height 11). Person 3 (height 5) is hidden behind person 2 (height 8) because 8 is not shorter than both 10 and 5. Person 5 (height 9) is hidden behind person 4 (height 11). So the answer for person 0 is 3.

heights = [10, 6, 8, 5, 11, 9]. Green dashed lines show who person 0 can see (persons 1, 2, and 4). Person 3 (h=5) is hidden behind person 2 (h=8). Person 4 (h=11) blocks the view of person 5.

The brute force

The direct approach: for each person, scan right and track the maximum height seen so far. A person at index j is visible from index i if no one between them is as tall as or taller than both heights[i] and heights[j].

def can_see_brute(heights):
    n = len(heights)
    result = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if all(heights[k] < heights[j] and heights[k] < heights[i]
                   for k in range(i + 1, j)):
                result[i] += 1
            if heights[j] >= heights[i]:
                break
    return result

This is O(n^2) in the worst case, and the inner loop checking "all people between" can make it even worse. For arrays up to 100,000 elements, we need something better.

The key observation is that visibility follows a monotonic pattern. When you look right from any person, you see a sequence of people with increasing heights until you hit someone taller than you (who blocks your view entirely). This "increasing heights until blocked" structure is exactly what a monotonic decreasing stack captures.

The key insight: monotonic stack from the right

Process people from right to left. Maintain a stack in decreasing order (tallest at the bottom). For each person at index i:

Pop all shorter people from the stack. Each popped person is someone that person i can see, because they are shorter and nothing blocks the line of sight (the stack keeps things in decreasing order, so popped people form an increasing sequence as seen from person i).
If the stack is not empty after popping, the person on top is also visible. This is the first person who is at least as tall as person i, and they block the view of anyone behind them.
The count is the number of pops plus 1 if the stack is still not empty.
Push the current person onto the stack.

Why does processing right to left work? Because each person needs to know what is to their right. By the time we process person i, everyone to their right is already represented in the stack. The decreasing order of the stack means shorter people are on top, which is exactly the order person i would see them before a taller person blocks the rest.

The stack stores heights (or indices) in decreasing order from bottom to top. When you pop shorter people, you are counting the visible people in order of increasing distance. The first person still on the stack after popping is the "blocker" who is also visible but ends the line of sight.

Step-by-step walkthrough

Let's trace through heights = [10, 6, 8, 5, 11, 9] processing from right to left. The array is shown on the left with the current index highlighted. The stack is on the right. Green numbers below the array are the answers filled in so far.

Step 1: i=5, h=9. Stack is empty. No one to see. count=0. Push 9.

Last person in line. No one to the right. Push 9 onto the stack. result[5] = 0.

Step 2: i=4, h=11. Pop 9 (shorter). Stack empty after pop. count=1. Push 11.

11 > 9, so pop 9 (person 5 is visible). Stack is now empty, so no taller blocker. count = 1. result[4] = 1.

Step 3: i=3, h=5. 5 < 11 (top). No pops. Stack not empty, +1. count=1. Push 5.

5 is shorter than the top (11). No pops. But the stack is not empty, meaning person 3 can see person 4 (the first taller person blocking the view). count = 0 + 1 = 1. result[3] = 1.

Step 4: i=2, h=8. Pop 5 (shorter). 8 < 11 (top), stop. Stack not empty, +1. count=2. Push 8.

8 > 5, so pop 5 (person 3 is visible). 8 < 11 (top), stop popping. Stack not empty, so person 4 (h=11) is also visible. count = 1 + 1 = 2. result[2] = 2.

Step 5: i=1, h=6. 6 < 8 (top). No pops. Stack not empty, +1. count=1. Push 6.

6 is shorter than the top (8). No pops. Stack not empty, so person 2 (h=8) is visible. count = 0 + 1 = 1. result[1] = 1.

Step 6: i=0, h=10. Pop 6, pop 8. 10 < 11 (top), stop. Stack not empty, +1. count=3. Push 10.

10 > 6, pop (person 1 visible). 10 > 8, pop (person 2 visible). 10 < 11, stop. Stack not empty, person 4 also visible. count = 2 + 1 = 3. result[0] = 3. Final answer: [3, 1, 2, 1, 1, 0].

Notice a few things:

The stack stays decreasing. Every time we push, the new value is less than or equal to whatever is already on top. Taller people sit at the bottom.
Each person is pushed once and popped at most once. That is the O(n) guarantee, even though some steps pop multiple elements.
Step 6 is the interesting one. Person 0 (height 10) pops both person 1 (height 6) and person 2 (height 8) because they are both shorter. Then person 4 (height 11) remains on the stack, and person 0 can see them too. That gives count = 2 + 1 = 3.
The "+1 if stack not empty" rule is what makes this problem different from a standard next-greater-element. You are not just finding the next taller person. You are counting everyone visible along the way.

Practice monotonic stack problems with spaced repetition

The code

def canSeePersonsCount(heights):
    n = len(heights)
    result = [0] * n
    stack = []

    for i in range(n - 1, -1, -1):
        count = 0
        while stack and heights[i] > stack[-1]:
            stack.pop()
            count += 1
        if stack:
            count += 1
        result[i] = count
        stack.append(heights[i])

    return result

Breaking it down:

Initialize result to all zeros and create an empty stack.
Walk through the array from right to left.
While the stack is not empty and the current person is taller than the top: pop the top and increment count. Each popped person is visible.
If the stack is still not empty after popping, increment count by 1. The person on top is the first one at least as tall, and they are also visible.
Record count as the answer for the current index.
Push the current height onto the stack.

The while loop can pop multiple elements in a single iteration of the outer loop, but across the entire algorithm, each element is pushed and popped at most once.

Complexity analysis

Time: O(n). Each of the n heights is pushed onto the stack exactly once and popped at most once. The while loop does at most n pops total across all iterations. So the total work is O(n).

Space: O(n). In the worst case (a strictly increasing array like [1, 2, 3, 4, 5]), nothing gets popped and the stack holds all n elements.

Approach	Time	Space
Brute force	O(n^2)	O(1)
Monotonic stack	O(n)	O(n)

Drill stack-based counting patterns

Building blocks

1. Monotonic stack (decreasing)

The core pattern maintains a stack where each new element is smaller than or equal to the top. When you encounter a larger element, pop until the invariant is restored:

stack = []
for i in range(n - 1, -1, -1):
    while stack and heights[i] > stack[-1]:
        stack.pop()
    stack.append(heights[i])

This is the same decreasing stack used in problems like Stock Span and Next Greater Element (right-to-left variant). The only thing that changes between problems is what you compute during the pops.

2. Right-to-left processing with visibility counting

The counting logic is what sets this problem apart. Instead of just finding the next greater element, you count all the elements you pop (visible shorter people) and add 1 if the stack is still not empty (the first taller-or-equal blocker is also visible):

count = 0
while stack and heights[i] > stack[-1]:
    stack.pop()
    count += 1
if stack:
    count += 1
result[i] = count

This "count pops + check if blocker exists" pattern appears whenever you need to count how many elements are visible or reachable before being blocked.

Edge cases

Before submitting, verify your solution handles:

Strictly increasing like [1, 2, 3, 4, 5]: each person sees only the next person (who is taller and blocks the view). Answer: [1, 1, 1, 1, 0].
Strictly decreasing like [5, 4, 3, 2, 1]: each person sees everyone to their right (no one blocks). Answer: [4, 3, 2, 1, 0].
All same height like [3, 3, 3, 3]: each person can only see the immediate next person (equal height blocks the view). Answer: [1, 1, 1, 0].
Two elements [5, 3]: answer is [1, 0]. [3, 5]: answer is [1, 0]. In both cases, person 0 sees person 1.
Single element [7]: answer is [0].

The monotonic stack solution handles all of these without special cases.

From understanding to recall

You have seen how the right-to-left decreasing stack counts visible people by tracking pops and checking for a remaining blocker. The algorithm is clean, but it has a few pieces that are easy to mix up under pressure: the direction of iteration (right to left), the comparison direction (pop when current is taller), and the "+1 if stack not empty" logic that counts the blocker.

These are not conceptual issues. They are recall issues. You understand the algorithm, but three weeks from now, you might iterate left to right by habit, or forget to count the blocker, or pop on the wrong comparison. Spaced repetition fixes this by having you write the solution from scratch at increasing intervals until it sticks.

Daily Temperatures - the classic monotonic stack "next greater element" problem
Largest Rectangle in Histogram - another monotonic stack problem with bar heights
Stack Patterns - overview of monotonic stacks and other stack techniques

CodeBricks breaks the monotonic stack pattern into its reusable pieces and drills them individually. You type the pop-and-count loop from scratch each time, building the muscle memory so that when you see Number of Visible People in a Queue in an interview, the code flows without hesitation.

Start drilling stack patterns today