Problem statement

There are n people in a queue with distinct heights, all facing right. Person i can see person j (where i < j) if everyone strictly between them is shorter than both of them.

Return an array where the i-th entry is the number of people person i can see to their right.

Example 1

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

Example 2

Input: heights = [5,1,2,3,10]
Output: [4,1,1,1,0]

Example 3

Input: heights = [1]
Output: [0]

Constraints

• 1 <= heights.length <= 40
• 1 <= heights[i] <= 1000000
• All heights are distinct.

Hints for Number of Visible People in a Queue

1. Hint 1

   Scan from the right, keeping a stack of heights that are increasing from top to bottom.

2. Hint 2

   Everyone the stack pops is visible — they are shorter than the current person and were the tallest so far.

3. Hint 3

   After popping, the remaining top (if any) is also visible, and it blocks everything beyond it.

How to solve Number of Visible People in a Queue

Scan from the right with a stack of heights increasing from top to bottom; everyone popped by the current person is visible, and the remaining top (if any) is visible too and blocks the rest.

Approach

1. For i from the end: pop while top < heights[i], counting each; add 1 if the stack is non-empty; record the count; push heights[i].

Why it works

The stack holds the people to the right who are not blocked by someone taller between them and i; those shorter than i are seen and then permanently hidden behind i, and the first taller one is seen but blocks everything beyond.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Heights are distinct, so strict comparisons are unambiguous.

Reference solution

Python

def canSeePersonsCount(heights):
    n = len(heights)
    out = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        seen = 0
        while stack and stack[-1] < heights[i]:
            stack.pop()
            seen += 1
        if stack:
            seen += 1
        out[i] = seen
        stack.append(heights[i])
    return out

Java

public static int[] canSeePersonsCount(int[] heights) {
    int n = heights.length;
    int[] out = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = n - 1; i >= 0; i--) {
        int seen = 0;
        while (!stack.isEmpty() && stack.peek() < heights[i]) {
            stack.pop();
            seen++;
        }
        if (!stack.isEmpty()) seen++;
        out[i] = seen;
        stack.push(heights[i]);
    }
    return out;
}

C++

vector<int> canSeePersonsCount(vector<int>& heights) {
    int n = (int) heights.size();
    vector<int> out(n, 0);
    vector<int> stack;
    for (int i = n - 1; i >= 0; i--) {
        int seen = 0;
        while (!stack.empty() && stack.back() < heights[i]) {
            stack.pop_back();
            seen++;
        }
        if (!stack.empty()) seen++;
        out[i] = seen;
        stack.push_back(heights[i]);
    }
    return out;
}

JavaScript

var canSeePersonsCount = function(heights) {
    const n = heights.length;
    const out = [];
    for (let i = 0; i < n; i++) out.push(0);
    const stack = [];
    for (let i = n - 1; i >= 0; i--) {
        let seen = 0;
        while (stack.length > 0 && stack[stack.length - 1] < heights[i]) {
            stack.pop();
            seen++;
        }
        if (stack.length > 0) seen++;
        out[i] = seen;
        stack.push(heights[i]);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard