We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Visible People in a Queue

Number: 1305

Difficulty: Hard

Paid? No

Companies: Google, Amazon, Meta, Meesho, Rippling, TikTok, DoorDash, ServiceNow, GE Healthcare, Oracle, Expedia

Problem Description

Given an array of distinct integers representing the heights of people standing in a queue (from left to right), determine for each person the number of people to their right that they can see. A person can see another person if every person in between is shorter than both the current person and the person being seen.

Key Insights

  • The problem requires determining the visibility count for each person based on height comparisons.
  • A monotonic stack is an effective tool to “simulate” the view from each person.
  • By iterating from right-to-left, we can efficiently maintain a stack containing potential visible persons.
  • For each current person, pop all shorter persons from the stack (they are visible) and if the stack is not empty afterward, it means the next taller person is still visible.
  • The use of a monotonic stack allows the solution to run in O(n) time by processing each element only once.

Space and Time Complexity

Time Complexity: O(n) – each element is pushed and popped at most once. Space Complexity: O(n) – in the worst-case scenario, the stack can hold all n elements.

Solution

We solve this problem by iterating through the queue from right to left while maintaining a monotonic stack. The stack stores the heights of people in a decreasing order (from top to bottom). For each person, we perform the following steps:

  1. Initialize a count for visible persons.
  2. While the stack is not empty and the current person's height is greater than the height on the top of the stack, we pop the stack. Each popped element represents a person that the current person can see.
  3. If the stack remains non-empty after the popping process, the current person can also see the next taller person (the one currently at the top of the stack).
  4. Store the computed count in the result array and push the current person's height onto the stack. This approach guarantees that each person’s visibility count is computed efficiently in a single pass using a monotonic stack.

Code Solutions

# Python solution using a monotonic stack

def canSeePersonsCount(heights):
    n = len(heights)  # Total number of people in the queue
    answer = [0] * n  # Initialize the answer array with zeros
    stack = []  # Stack to keep track of heights
    
    # Iterate from rightmost person to leftmost person
    for i in range(n - 1, -1, -1):
        count = 0  # Count for the number of people the current person can see
        
        # Pop all people shorter than the current person as they are visible
        while stack and heights[i] > stack[-1]:
            stack.pop()
            count += 1  # Each popped person is visible from the current person's view
        
        # If the stack is not empty, the current person can see one more person (taller than them) 
        if stack:
            count += 1
        
        answer[i] = count  # Save the computed count for the current person
        stack.append(heights[i])  # Push the current person's height onto the stack
    
    return answer

# Example usage:
# heights = [10,6,8,5,11,9] should output [3,1,2,1,1,0]
print(canSeePersonsCount([10,6,8,5,11,9]))
← Back to All Questions