⚡Flashcard Drill➔
NeetCode #377LC-1944HardStack
← Back to All Problems

#377 · #1944 · Number of Visible People in a Queue(队列中可以看到的人数)

📌 Problem Statement & Constraints

There are n people in a queue, heights[i] is the height of the i-th person. A person can see the next person to the right who is taller, and everyone shorter in between. Return an array where answer[i] is the number of people person i can see to their right. Constraints: 1 <= n <= 10^5, 1 <= heights[i] <= 10^5.

💡 Core Algorithmic Approaches

  1. Scan from right to left with a monotonically decreasing stack of indices.
  2. For each person, pop everyone shorter than them: each popped person is visible, and their own view is already accounted for.
  3. If the stack is still non-empty after popping, the new top is at least as tall and blocks everyone behind it -- but is itself visible, adding one.
  4. Push the current index. Each index is pushed and popped once, giving O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        res = [0] * n
        st = []                            # decreasing heights, indices
        for i in range(n - 1, -1, -1):
            cnt = 0
            while st and heights[st[-1]] < heights[i]:
                cnt += 1                   # visible, and it does not block
                st.pop()
            if st:
                cnt += 1                   # the first taller-or-equal person
            res[i] = cnt
            st.append(i)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the if st: cnt += 1: the person who finally blocks the view is still visible.
  • Using <= in the pop condition: an equal-height person blocks the view, so only strictly shorter people are popped.
  • Scanning left to right: the visibility depends on the taller people to the right, so the scan must go backwards.
  • Trying a nested loop: O(n^2) with n = 10^5.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems