Number of Visible People in a Queue — Monotonic Stack Right-to-Left

Problem Statement#

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

A person can see another person to their right in the queue if everyone in between is shorter than both of them. Formally, person i can see person j (i < j) if min(heights[i], heights[j]) > max(heights[i+1], ..., heights[j-1]).

Return an array answer of length n where answer[i] is the number of people the i-th person can see to their right in the queue.

Constraints:

• n == heights.length
• 1 <= n <= 10^5
• 1 <= heights[i] <= 10^5
• All heights[i] are distinct.

Input:  heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
- Person 0 (height 10) sees 6, 8, 11 (sees 11 then blocked).
- Person 1 (height 6) sees 8 only.
- Person 2 (height 8) sees 5 then 11.
- Person 3 (height 5) sees 11.
- Person 4 (height 11) sees 9.
- Person 5 sees nobody.

Input:  heights = [5,1,2,3,10]
Output: [4,1,1,1,0]
Explanation: Person 0 (height 5) sees 1, 2, 3, 10 — each one is the new max so far.

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

Why This Problem Matters#

LeetCode 1944 Number of Visible People in a Queue is rated Hard but is conceptually a clean monotonic stack problem. It is asked at Amazon, Google, and Meta to test whether candidates can adapt the "next greater element" pattern to a counting variant.

Real-world analogies:

• Forest tree visibility: looking down a row of trees from the side.
• Skyline visibility from a viewpoint: how many buildings are visible from the left.
• Network ACK chains: each node ACKs only nodes whose heights are visible.

If you can solve LC 1944, you have generalized the monotonic stack pattern beyond the standard "next greater element" template — a key skill for harder problems.

The Core Insight#

Person i sees:

1. Every monotonically increasing height to its right, until a person taller than heights[i] appears.
2. The taller person itself (if one exists).

Equivalently: scanning from right to left, maintain a monotonically decreasing stack of heights (top is the smallest). For person i:

• Pop everyone shorter than heights[i] — each pop counts as one visible person (these are the increasing heights person i can see).
• If the stack is still non-empty, heights[i] can also see the next taller person on top of the stack — count one more.
• Push heights[i].

The total work is O(n) because each element is pushed and popped at most once.

Visual Dry Run#

Input: heights = [10, 6, 8, 5, 11, 9]. Scan right-to-left.

Result: [3, 1, 2, 1, 1, 0]. ✓

Solution (Optimal)#

# Python — monotonic stack right-to-left, O(n) time, O(n) space
def canSeePersonsCount(heights: list[int]) -> list[int]:
    n = len(heights)
    answer = [0] * n
    stack = []  # decreasing from bottom to top
 
    for i in range(n - 1, -1, -1):
        count = 0
        while stack and stack[-1] < heights[i]:
            stack.pop()
            count += 1
        if stack:
            count += 1  # the taller blocker
        answer[i] = count
        stack.append(heights[i])
 
    return answer

// JavaScript — monotonic stack right-to-left, O(n) time, O(n) space
function canSeePersonsCount(heights) {
    const n = heights.length;
    const answer = new Array(n).fill(0);
    const stack = [];
 
    for (let i = n - 1; i >= 0; i--) {
        let count = 0;
        while (stack.length && stack[stack.length - 1] < heights[i]) {
            stack.pop();
            count++;
        }
        if (stack.length) count++;
        answer[i] = count;
        stack.push(heights[i]);
    }
 
    return answer;
}

# Brute force for contrast, O(n^2)
def canSeePersonsCountBrute(heights: list[int]) -> list[int]:
    n = len(heights)
    answer = [0] * n
    for i in range(n):
        max_in_between = 0
        for j in range(i + 1, n):
            if heights[j] > max_in_between:
                answer[i] += 1
                max_in_between = heights[j]
            if heights[j] >= heights[i]:
                break
    return answer

Complexity:

Common Mistakes#

1. Scanning left-to-right. It is possible but harder; right-to-left makes the pattern crisp because the stack at index i represents future people.

2. Forgetting to count the taller blocker. After popping, if the stack is non-empty, the new top is taller than heights[i] and is also visible. Many candidates count only the popped heights and miss this.

3. Off-by-one when stack is empty after popping. If the stack is empty, person i cannot see anyone taller — do not add the extra 1.

4. Using <= instead of <. The problem says heights are distinct, so <= works in this specific problem, but for variants with duplicates the comparison matters.

5. Resetting count outside the loop. Each person needs a fresh count; reset at the start of every iteration.

Interview Tips#

• Identify the pattern explicitly: "This is a variant of next greater element. I will scan right-to-left with a monotonic decreasing stack."
• Walk through the visibility rule on a small example before coding. Many candidates miscount the blocker.
• After coding, narrate the amortized analysis: "Each height is pushed once and popped at most once, so total work is O(n)."
• If the interviewer asks for visibility on both sides, run two passes — left-to-right and right-to-left — and sum the results.

Follow-up Questions#

1. Visibility in both directions. Run the same algorithm in both directions and combine.
2. Skyscraper problem. Given a row of buildings, return how many are visible from the left — same template.
3. Visibility with obstacles of variable transparency. Each person blocks visibility by a fraction; needs different accounting.
4. 2D variant — rooftop visibility on a grid. Generalizes to topographic prominence problems.
5. Stream version. Compute answer[i] online as new heights arrive at the right of the queue.

Key Takeaways#

• Number of Visible People is a counting variant of the next greater element pattern; use a monotonic decreasing stack.
• Scan right-to-left so the stack always holds future people; pop everyone shorter and add one extra if a taller blocker remains.
• Time is O(n) due to amortized pop counting; space is O(n) for the stack.
• The "+1 for the taller blocker" is the part most candidates miss — verbalize it during the interview.
• The pattern generalizes to skyline / skyscraper visibility, two-direction visibility, and many "see until blocked" problems.
• Compared to brute force O(n^2), the stack achieves a clean linear-time solution well within constraints up to 10^5.