Number of Visible People in a Queue

HardMonotonic Stack🧩 Monotonic Stack LeetCode #1944 ↗Updated Oct 30, 2026

Problem

People stand in a line facing right; heights[i] is the (distinct) height of person i. Person i can see person j > i when everybody standing strictly between them is shorter than both of them. Return an array whose i-th entry is how many people person i can see.

Inputheights = [10,6,8,5,11,9]Output[3,1,2,1,1,0]

Inputheights = [5,1,2,3,10]Output[4,1,1,1,0]

1 ≤ n ≤ 10⁵ · 1 ≤ heights[i] ≤ 10⁵ · all heights distinct

Try it yourself

Java

class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Looking right, person i sees a strictly increasing run of people up to the first one taller than them. Processing from the right with a decreasing stack, the people i pops are exactly that run, plus one more if someone taller remains on the stack.

PatternMonotonic Stack

Instinct Each element needs its nearest bigger or smaller neighbour (next warmer day, span, widest bar) - keep a sorted stack of waiting indices.

Memory hack Tall people block the view - a newcomer kicks out everyone shorter waiting behind, and each kicked-out person just found their answer.

Open the Monotonic Stack guide →

Approaches

Brute ForceCheck Every Pair Directly

Time O(n³)Space O(1) extra

For each pair (i, j) compute the tallest person strictly between them and test that both endpoints are taller than it. This is the visibility rule copied literally.

Java

public int[] canSeePersonsCount(int[] heights) {
    int n = heights.length;
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int tallestBetween = 0;
            for (int m = i + 1; m < j; m++) {
                tallestBetween = Math.max(tallestBetween, heights[m]);
            }
            if (Math.min(heights[i], heights[j]) > tallestBetween) ans[i]++;
        }
    }
    return ans;
}

Obviously correct, useful as a reference, but cubic.

BetterRunning Maximum with Early Stop

Time O(n²)Space O(1) extra

Sweep right from i keeping the tallest person passed so far. Person j is visible exactly when it beats that running maximum. Once someone at least as tall as i appears, they block everything beyond, so stop.

Java

public int[] canSeePersonsCount(int[] heights) {
    int n = heights.length;
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) {
        int tallestSoFar = 0; // tallest person between i and j
        for (int j = i + 1; j < n; j++) {
            if (heights[j] > tallestSoFar) ans[i]++;
            tallestSoFar = Math.max(tallestSoFar, heights[j]);
            if (tallestSoFar >= heights[i]) break; // view is blocked
        }
    }
    return ans;
}

Removes the inner loop, but a decreasing line still costs O(n²).

OptimalRight-to-Left Decreasing Stack

Time O(n)Space O(n)

Scan from the right; the stack holds people still visible from the left, tallest at the bottom. Person i pops everyone shorter — they are all visible to i and now hidden from anyone further left. If the stack is still non-empty, its top is the first taller person, also visible.

Java

public int[] canSeePersonsCount(int[] heights) {
    int n = heights.length;
    int[] ans = new int[n];
    int[] stack = new int[n];
    int top = -1;
    for (int i = n - 1; i >= 0; i--) {
        int seen = 0;
        // shorter people are visible to i and hidden for everyone further left
        while (top >= 0 && stack[top] < heights[i]) {
            top--;
            seen++;
        }
        if (top >= 0) seen++; // the first taller person is visible too
        ans[i] = seen;
        stack[++top] = heights[i];
    }
    return ans;
}

Dry runheights = [10,6,8,5,11,9]

i current person changed

i=5
10

6

8

5

11

9
i
ans=0, st=[9]
i=4
10

6

8

5

11
i
9

pop 9; ans=1, st=[11]
i=3
10

6

8

5
i
11

9

top 11; ans=1
i=2
10

6

8
i
5

11

9

pop 5 +11; ans=2
i=1
10

6
i
8

5

11

9

top 8; ans=1
i=0
10
i
6

8

5

11

9

pop 6,8 +11; ans=3

Each person is pushed and popped once — linear and clean.

Pro tip

Popped people can never be seen again from the left — person i is taller and stands in front of them.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Pair Directly	`O(n³)`	`O(1) extra`
Better	Running Maximum with Early Stop	`O(n²)`	`O(1) extra`
Optimal	Right-to-Left Decreasing Stack	`O(n)`	`O(n)`

Common pitfalls

Counting only people taller than i — shorter ones can be visible too.
Forgetting the extra +1 for the first taller person left on the stack.
Not stopping at the first person at least as tall as i in the O(n²) scan.

Interview tips

Draw a small example and notice the visible people form an increasing run.
State the stack invariant: strictly decreasing heights from bottom to top.
Mention distinct heights; with ties you would have to decide how equals block.

Pattern

Monotonic stack → counting or finding elements “until the next greater one” on one side.

My notes saved in this browser