#1944

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Number of Visible People in a Queue

Compute how many people each person in a queue can see to their right using efficient stack-based state management.

Problem Statement

Given an array heights of distinct integers representing the heights of people standing in a left-to-right queue, determine how many people each person can see to their right. A person can see another if all individuals in between are shorter than both of them.

Return an array answer where answer[i] is the number of people the ith person can see in the queue to their right. Implement a solution using stack-based state management to efficiently handle this visibility tracking.

Examples

Example 1

Input: heights = [10,6,8,5,11,9]

Output: [3,1,2,1,1,0]

Person 0 can see person 1, 2, and 4. Person 1 can see person 2. Person 2 can see person 3 and 4. Person 3 can see person 4. Person 4 can see person 5. Person 5 can see no one since nobody is to the right of them.

Example 2

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

Output: [4,1,1,1,0]

Example details omitted.

Constraints

n == heights.length
1 <= n <= 105
1 <= heights[i] <= 105
All the values of heights are unique.

Solution Approach

Use Monotonic Stack

Iterate from right to left and maintain a stack of people heights. Pop elements shorter than the current height while counting them as visible. Push the current person onto the stack after counting.

Count Visible People

For each person, the number of people popped from the stack plus one (if the stack is not empty) represents how many people they can see. This captures both consecutive shorter people and the first taller person to the right.

Optimize for Linear Time

Ensure each person is pushed and popped at most once to keep O(n) time complexity. This avoids quadratic behavior and leverages stack state for accurate visibility calculation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each person is pushed and popped at most once. Space complexity is O(n) for the stack storing intermediate heights during processing.

What Interviewers Usually Probe

Consider edge cases where tallest person is at the end of the queue.
Ask about naive O(n^2) approach versus stack optimization.
Probe how stack state helps count visible people efficiently.

Common Pitfalls or Variants

Common pitfalls

Forgetting to count the first taller person after popping shorter ones.
Confusing index order when iterating from right to left.
Failing to maintain monotonic stack leading to incorrect visibility counts.

Follow-up variants

Compute visible people to the left using similar stack logic.
Handle queues with non-unique heights using modified comparison rules.
Extend to 2D grids to count visible people in multiple directions.

FAQ

What pattern does 'Number of Visible People in a Queue' follow?

It follows a stack-based state management pattern where a monotonic stack tracks visibility to the right.

Can this problem be solved in O(n^2) time?

Yes, by checking every person to the right of each individual, but it is inefficient compared to the stack approach.

Why use a monotonic stack for this problem?

It efficiently counts visible people by maintaining order and popping shorter heights, reducing redundant comparisons.

How does GhostInterview help with this problem?

It guides implementation of the stack approach, prevents common pitfalls, and ensures linear time complexity.

What edge cases should I watch for?

Watch for tallest people at the end and consecutive increasing or decreasing heights, as these affect visibility counts.

terminal

Solution

Solution 1: Monotonic Stack

We observe that for the $i$-th person, the people he can see must be strictly increasing in height from left to right.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        ans = [0] * n
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and stk[-1] < heights[i]:
                ans[i] += 1
                stk.pop()
            if stk:
                ans[i] += 1
            stk.append(heights[i])
        return ans

Continue Practicing

#1996 the number of weak characters in the game #1856 maximum subarray min product #1793 maximum score of a good subarray