Number of Visible People in a Queue

Hard

Rippling

0 views

Topics:

ArraysStacks

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 i^th 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 i^th person can see the j^th 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 i^th 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 <= 10⁵
1 <= heights[i] <= 10⁵
All the values of heights are unique.

Number of Visible People in a Queue

Hard

Rippling

0 views

Topics:

ArraysStacks

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 i^th 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 i^th person can see the j^th 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 i^th 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 <= 10⁵
1 <= heights[i] <= 10⁵
All the values of heights are unique.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `heights` array, and the range of values within it?
Can the `heights` array contain duplicate values, and if so, how should that be handled?
Is an empty input array a possibility, and if so, what should the output be?
Could you clarify the expected behavior when a person sees another person of the exact same height? Should they be counted as visible?
Can you provide a small example to illustrate the problem and the expected output?

Brute Force Solution

Approach

Imagine people standing in a line, and you want to figure out how many people each person can see in front of them. The straightforward but inefficient way is to have each person look at every single person in front of them individually. This is the brute force approach.

Here's how the algorithm would work step-by-step:

Start with the first person in line.
Have that person look at the person directly in front of them. If the second person is taller, the first person can see them. Count that.
Next, have the first person look at the person two spots in front of them. If this third person is taller than everyone in between the first and third person, the first person can see them. Count that.
Continue this process until the first person has looked at everyone in front of them, counting each visible person.
Repeat this entire process for the second person in line, then the third person, and so on, until everyone has had a chance to look at everyone in front of them.
The total count of visible people for each person is the answer.

Code Implementation

def visible_people(heights):
    number_of_people = len(heights)
    visible_counts = [0] * number_of_people

    for current_person_index in range(number_of_people):
        for other_person_index in range(current_person_index + 1, number_of_people):
            is_visible = True
            # Check if the other person is visible

            for intermediate_person_index in range(current_person_index + 1, other_person_index):
                # If any intermediate person is taller, other person is not visible
                if heights[intermediate_person_index] >= heights[other_person_index]:

                    is_visible = False
                    break

            # Increment the visible count if no one blocks the view
            if is_visible:

                visible_counts[current_person_index] += 1

    return visible_counts

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n people in the queue. For each person, it iterates through the remaining people in front of them to determine visibility. In the worst case, the first person checks n-1 people, the second checks n-2, and so on, down to the last person checking 0. This results in a sum of (n-1) + (n-2) + ... + 0, which is equivalent to n*(n-1)/2. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The plain English explanation describes a brute-force approach where each person iterates through the rest of the line. This involves comparing heights and counting visible people for each person. The algorithm doesn't mention the creation of any auxiliary data structures like lists, sets, or dictionaries. Therefore, it only uses a constant amount of extra space, most likely for loop counters and temporary variables for comparisons, which do not scale with the input size N (number of people in the queue).

Optimal Solution

Approach

The key idea is to maintain a decreasing stack to keep track of potentially visible people. We iterate through the queue, and for each person, we pop anyone shorter than them from the stack (because they are blocked).

Here's how the algorithm would work step-by-step:

Think of a stack like a pile where you can only add or remove from the top.
Start with an empty stack.
Go through the queue of people one by one from left to right.
For each person, look at the stack. Remove all the people from the top of the stack that are shorter than the current person. The number of people you remove are all visible to the current person.
Increment the count of visible people.
If there's still someone in the stack, it means the current person can see the tallest person from the stack, so increment the count of visible people.
Add the current person to the top of the stack.
Repeat this process for everyone in the queue.
The final count of visible people from each person is the result.

Code Implementation

def visible_people(heights):
    number_of_people = len(heights)
    visible_counts = [0] * number_of_people
    stack = []

    for i in range(number_of_people):
        while stack and heights[stack[-1]] < heights[i]:
            # Pop shorter people, since they are blocked.
            stack.pop()
            visible_counts[i] += 1

        if stack:
            # Account for visibility of the next tallest person.
            visible_counts[i] += 1

        # Push the current person onto the stack.
        stack.append(i)

    return visible_counts

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – We iterate through the queue of n people once. Inside the loop, while we have a while statement which might appear like a nested loop, the while statement only removes elements from the stack. Each element is added to the stack once and removed at most once. Therefore, the amortized cost of the while loop is O(1). Consequently, the overall time complexity is dominated by the single pass through the queue, resulting in O(n).

Space Complexity

O(N) – The algorithm uses a stack to store the heights of people who are potentially visible. In the worst-case scenario, where the input array is sorted in increasing order, all the people's heights will be added to the stack before anyone is popped. Thus, the stack can grow up to the size of the input array, N, where N is the number of people in the queue. The space required for the stack is therefore proportional to the number of people in the queue. Consequently, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input array	Return an empty array since there are no people to consider.
Input array with only one element	Return an array containing only 0, as a single person can see no one to their right.
Input array with all elements having the same height	Each person can only see the immediate neighbor to the right unless it's the last person, who sees 0.
Input array with heights in strictly increasing order	Each person can see all the people to their right.
Input array with heights in strictly decreasing order	Each person can only see one person to the right, the next one.
Maximum size of the input array (scalability)	The solution should be optimized to avoid quadratic time complexity to handle large input sizes efficiently, ideally using a stack based approach.
Heights with extremely large values (integer overflow)	Ensure that the comparisons and calculations do not lead to integer overflow, potentially using a larger integer type if necessary.
Combination of tall people followed by many shorter people	Stack should efficiently remove shorter people from its base to accurately calculate the number of visible people for the taller ones.