Number of Visible People in a Queue

Number of Visible People in a Queue

What is this problem about?

The Number of Visible People in a Queue problem places people in a queue with different heights. For each person, count how many people to their right they can see. A person at position i can see person j (j > i) if all people between them are shorter than both person[i] and person[j]. This hard coding problem uses a monotonic stack to compute visibility counts efficiently.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, Bloomberg, and many others ask this hard stack problem because it tests the monotonic stack for visibility counting. The standard approach — for each i, scan right — is O(n²). The stack-based O(n) solution is the expected answer at top-tier companies. The array, monotonic stack, and stack interview pattern is the core.

Algorithmic pattern used

Monotonic decreasing stack (process right to left). Process from right to left. For each person i, pop all shorter people from the stack (each popped person is visible to i, plus 1 for the first taller person that stops the pops). The count for person i = number of pops + (1 if stack is non-empty after pops). Push person i onto the stack.

Example explanation

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

• i=5 (9): stack=[]. Count[5]=0. Push 9. Stack=[9].
• i=4 (11): pop 9 (visible, count=1). Stack empty. Count[4]=1. Push 11. Stack=[11].
• i=3 (5): 5<11, no pops. Stack non-empty: count=1. Count[3]=1. Push 5. Stack=[11,5].
• i=2 (8): pop 5 (count=1). 8<11, stop. Stack non-empty: count+=1=2. Count[2]=2. Push 8. Stack=[11,8].
• i=1 (6): no pops (6<8). Stack non-empty: count=1. Count[1]=1. Push 6. Stack=[11,8,6].
• i=0 (10): pop 6(1), pop 8(2). 10<11, stop. Stack non-empty: count=2+1=3. Count[0]=3. Push 10. Result = [3,1,2,1,1,0].

Common mistakes candidates make

• Processing left to right (harder to maintain visibility count).
• Off-by-one: each popped element is visible (+1), plus the first non-popped element (+1 if stack non-empty).
• Using BFS/DFS instead of monotonic stack.
• Not including the taller person that stops the pop sequence as visible.

Interview preparation tip

Visibility counting in queues/buildings is a classic monotonic stack application. The key insight: person i sees person j if no person between them is taller than min(h[i], h[j]). The monotonic stack elegantly captures this: each popped element (shorter than current) is visible from current, and the non-popped top (taller) is the final visible person. Practice "buildings with ocean view," "trapping rain water," and "skyline problem" — they all use monotonic stacks for visibility and height analysis.