1944.Number of Visible People in a Queue

• Link: 1944. Number of Visible People in a Queue - Hard
• Track: NeetCode150

Question

• Example
  • Input: heights = [10,6,8,5,11,9]
  • Output: [3,1,2,1,1,0]
  • Explanation:
    • 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.

Restate the problem

• Given an array heights, where heights[i] is the height of the ith person in a queue
• For each person, return how many people they can see to their right
• A person i can see person j if:
  • i < j
  • and every person between them is shorter than both heights[i] and heights[j]

Edge Case

• Strictly increasing heights, e.g. [1,2,3,4]
• Strictly decreasing heights, e.g. [4,3,2,1]

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Monotonic stack (right to left)	$O(n)$	$O(n)$
Method 2 (TLE)	Brute force (left to right)	$O(n^2)$	$O(1)$

Method 1 - Monotonic stack

Key idea:
Keep the right side as a stack of people from near to far, increasing heights.
Current person pops all shorter people they can see, then sees the first taller/equal person if it exists.
用栈维护右边一条 从近到远、越来越高的人。当前人先弹掉所有自己能看到的更矮的人，再看第一个更高的人。

Approach

• Process people from right to left

• Maintain a monotonic decreasing stack

• Pop all shorter people and count them

• If one taller/equal person remains, count it too

• Push current height into the stack

• stack stores people on the right from near to far, and their heights are increasing.

• stack: 放的是右边一条“从近到远，越来越高”的人。

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$

Code

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        res = [0] * n
        stack = []  # right side: from near to far, heights are increasing
 
        for idx in range(n - 1, -1, -1):
            count = 0
 
            while stack and heights[idx] > stack[-1]:
                stack.pop() # 弹出右边比当前人矮的人，说明当前人可以看到这个人
                count += 1
 
            if stack:
                count += 1
 
            res[idx] = count
            stack.append(heights[idx])
 
        return res

Method 2 - TLE - Brute Force (left to right)

Complexity

• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$
  • not included result

Code

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        res = [0] * n
        
        for i in range(n):
            max_height = 0
            for j in range(i + 1, n):
                if max_height < heights[j]:
                    res[i] += 1
                    max_height = max(max_height, heights[j])
                
                if heights[i] < heights[j]:
                    break
                    
        return res

---

Mistake

• Forget to count the first taller/equal person after popping