{x}
blog image

Number of Visible People in a Queue

There are n people standing in a queue, and they numbered from 0 to n - 1 in left to right order. You are given an array heights of distinct integers where heights[i] represents the height of the ith person.

A person can see another person to their right in the queue if everybody in between is shorter than both of them. More formally, the ith person can see the jth person if i < j and min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1]).

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

 

Example 1:

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.

Example 2:

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

 

Constraints:

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

Solution Explanation

This problem can be efficiently solved using a monotonic stack. The core idea is to iterate through the heights array from right to left. For each person, we use the stack to keep track of the indices of people to their right who are potentially visible. The stack maintains a monotonically decreasing order of heights.

Algorithm:

  1. Initialization: Create an ans array of the same size as heights to store the count of visible people for each person. Initialize a stack stk to store indices.

  2. Iteration: Iterate through the heights array from right to left (index i from n-1 to 0).

  3. Stack Processing: For each person at index i:

    • While the stack is not empty and the height of the person at the top of the stack (stk.top()) is less than the height of the current person (heights[i]):
      • Pop the index from the stack.
      • Increment the count of visible people for the person at the popped index (ans[stk.top()]). This is because the current person is taller and blocks the view of the person on the stack.
    • If the stack is not empty after the popping:
      • Increment the count of visible people for the current person (ans[i]). This accounts for the person at the top of the stack who is visible.
    • Push the index i onto the stack.

  4. Return: Return the ans array.

Time Complexity: O(n), where n is the length of the heights array. Each element is pushed and popped from the stack at most once.

Space Complexity: O(n) in the worst case, as the stack might contain all the indices in the array.

Code Explanation (Python):

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        ans = [0] * n
        stk = [] # Monotonic stack storing indices
        for i in range(n - 1, -1, -1):
            while stk and heights[stk[-1]] < heights[i]: # while stack is not empty and top is shorter than current
                ans[stk[-1]] += 1 # increment count for person at top of stack
                stk.pop() # pop top
            if stk: # if stack is not empty
                ans[i] += 1 # add 1 for person at top of stack
            stk.append(i) # push current index onto stack
        return ans

The code in other languages follows the same logic, only differing in syntax and data structure implementations. The use of a Deque (double-ended queue) in Java or a std::stack in C++ provides the necessary stack operations efficiently. The core algorithm remains consistent across all implementations.