1944. Number of Visible People in a Queue

Problem Description

In this problem, we have n people standing in a queue, with each person having a distinct height. They are indexed from 0 to n - 1, starting from left to right. The goal is to determine for each person, how many other people in the queue they can see to their right.

The ability of one person to see another depends on the heights of others standing between them. Specifically, a person standing at position i can see a person at position j (where j > i) if everyone in between them is shorter than both person i and person j. In order words, the height of person i and person j must exceed the height of all individuals standing in positions i+1 to j-1.

Our task is to return an array answer, where answer[i] is the number of people that person i can see to their right in the queue based on the described visibility condition.

Intuition

The key to solving this problem is to use a structure called a monotonic stack. This kind of stack preserves an order (either increasing or decreasing) as we process the elements.

Given that we want to find the number of people a person can see to the right before someone taller blocks the rest, the stack will help us keep track of potential candidates in decreasing height as we iterate from right to left through the queue.

Here's how we derive the solution:

We iterate from the end of the array heights to the beginning. This back-to-front iteration lets us approach the problem from the perspective of the person looking to the right, ensuring we've already handled all individuals potentially visible to them.
We use a stack to store the heights of people that are currently "visible" to the person at position i. Since we're looking for people that a person can see to the right, we keep removing shorter individuals from the stack until we find someone taller or the stack is empty.
As we remove these shorter individuals from the stack, we count them, as they contribute to the number of people the current person can see.
If there is someone taller on the stack after we've popped all shorter individuals, this means the current person can see one additional person (the taller one) who then blocks the view further. Therefore, we increment the count by one more in this case.
Finally, we have to add the current person's height to the stack because they may be visible to the next person we process (they are now the new "taller" individual that could potentially block others from view to the right).

By using the monotonic stack approach we avoid re-scanning parts of the array that we have already processed, hence significantly reducing the time complexity of the operation compared to checking all pairs of persons for visibility.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The key to this problem is effectively tracking and incrementing our visibility count for each person as we iterate through the queue. Here's the step-by-step explanation of how the provided Python solution accomplishes this:

Initialization: We declare an empty list called stk meant to function as a stack. This stack will maintain indices of persons in a monotonically decreasing order according to their heights, meaning that each person's height on the stack is smaller than the one below them. We also create a list called ans of the same length as the heights array, initialized with zeroes. ans[i] will be used to store the number of people person i can see.
Iterating Through The Queue: The loop for i in range(n - 1, -1, -1): goes through each person starting from the end of the queue (n - 1) and moves towards the first person (0), backward one index at a time. This reverse iteration aligns with the direction of visibility (rightwards).
Pop Shorter People Off The Stack: Inside the loop, we have a while loop while stk and stk[-1] < heights[i]: which continues to pop elements from the stack if the top of the stack (the last element stk[-1]) is shorter than the current person's height (heights[i]). For each pop, we increment ans[i] because each of these popped persons is directly visible to the current person.
Handle The Next Tallest Person: After removing all shorter people, if the stack is not empty if stk:, it means that there is at least one person taller than the current person remaining on the stack. This taller person is the one who blocks the current person's view of anybody else to their right. Therefore, ans[i] is incremented by 1.
Update The Stack: Finally, we append the current person's height heights[i] to the stack. They will now be the potential "blocker" for people to their left, just as we are calculating for them with respect to those to their right.
Return The Answer: When the loop completes, we have filled ans with the visibility counts for all persons and we return this list.

Code Snippet

The algorithm is compactly implemented as follows:

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        ans = [0] * n
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and stk[-1] < heights[i]:
                ans[i] += 1
                stk.pop()
            if stk:
                ans[i] += 1
            stk.append(heights[i])
        return ans

This solution is efficient due to the monotonic stack which helps in keeping track of people that can potentially be seen without scanning the entire list for each person. As each person is processed, only a relevant subset of the people they can see is considered, thereby optimizing the visibility count update.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Consider a queue with 5 people having the following distinct heights: [5, 3, 8, 3, 1]. We'll go through the steps to figure out how many people each person can see to their right in the queue.

Initialization: Initialize an empty stack called stk and an answer array called ans with the same length as the heights array and all elements set to 0: ans = [0, 0, 0, 0, 0].
Iterating in reverse: Start from the end of the queue with person 4 (height 1). Since the stack is empty, there is no one taller that blocks the view, so the stack becomes stk = [1].
Move to person 3 (height 3). Since height 1 (on the stack) is less than height 3, we pop 1 from the stack and increment ans[3] by 1 (one person is visible). After popping, since the stack is empty, we don't increment ans[3] further and push height 3 onto the stack, so stk = [3].
At person 2 (height 8), person 3 (on the stack, height 3) is shorter, so we pop it and increment ans[2]. The stack is now empty again, and we push height 8, making stk = [8].
For person 1 with height 3, height 8 on the stack is taller, so we don't pop anyone from the stack, but increment ans[1] by 1 to indicate visibility of that one taller person blocking further view. We push height 3 onto the stack, so stk = [8, 3].
Finally, for person 0 with height 5, since height 3 is shorter (on the stack), we pop it and increment ans[0]. Height 8 is taller, so we increment ans[0] again and don't pop it. We push height 5 onto the stack, resulting in stk = [8, 5].
Return the Answer: The filled answer array represents the count of visible people for each person in the original queue order: ans = [2, 1, 1, 1, 0].

To summarize, we processed each person from right to left, maintaining a stack that helped us quickly determine who each person can see by only considering those who are relevant (taller) for the visibility condition. The answer array now holds for each person the count of people they can see to their right.

Solution Implementation

1class Solution:
2    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
3        # The number of people whose height can be seen by each person.
4        number_of_people = len(heights)
5        # Initialize an array to hold the count of people that can be seen for each person.
6        visible_count = [0] * number_of_people
7        # Initialize an empty list to use as a stack.
8        stack = []
9      
10        # Iterate through the list of heights in reverse order.
11        for index in range(number_of_people - 1, -1, -1):
12            # While stack is not empty and the height at the top of the stack is less
13            # than the current height, increment the count of visible people for
14            # the current height and remove the top height from the stack.
15            while stack and stack[-1] < heights[index]:
16                visible_count[index] += 1
17                stack.pop()
18          
19            # If the stack is not empty after the above while loop, it means the current person
20            # can see at least one other person who is taller. Increment the count by 1.
21            if stack:
22                visible_count[index] += 1
23          
24            # Add the current height to the stack.
25            stack.append(heights[index])
26      
27        # Return the list of counts for each person.
28        return visible_count
29

1class Solution {
2    public int[] canSeePersonsCount(int[] heights) {
3        // Initialize the number of people in the array
4        int n = heights.length;
5      
6        // Initialize the answer array where the result will be stored
7        int[] answer = new int[n];
8      
9        // Initialize a stack that will keep track of the heights as we move backwards
10        Deque<Integer> stack = new ArrayDeque<>();
11      
12        // Iterate over the heights array from end to start
13        for (int i = n - 1; i >= 0; --i) {
14            // Pop elements from the stack while the top element is less than the current height
15            // because the current person can see over the shorter person(s) behind.
16            while (!stack.isEmpty() && stack.peek() < heights[i]) {
17                stack.pop();
18                ++answer[i]; // Increment the count of people the current person can see
19            }
20          
21            // If there's still someone in the stack, increment the count by one
22            // because the current person can see at least one person who is taller.
23            if (!stack.isEmpty()) {
24                ++answer[i];
25            }
26          
27            // Push the current height onto the stack
28            stack.push(heights[i]);
29        }
30      
31        // Return the populated answer array
32        return answer;
33    }
34}
35

1#include <vector>
2#include <stack>
3using namespace std;
4
5class Solution {
6public:
7    vector<int> canSeePersonsCount(vector<int>& heights) {
8        int count = heights.size();  // Get the number of people in the line
9        vector<int> visibleCounts(count);  // Initialize a vector to store the counts of visible people
10        stack<int> heightStack;  // Stack to keep track of the heights of people
11      
12        // Start from the end of the line to calculate visible counts for each person
13        for (int i = count - 1; i >= 0; --i) {
14            // Pop people from stack who are shorter than the current person
15            // as current person can see over them
16            while (!heightStack.empty() && heightStack.top() < heights[i]) {
17                ++visibleCounts[i];  // Increment count of people this person can see
18                heightStack.pop();  // Remove the shorter person from consideration
19            }
20          
21            // If the stack is not empty after popping shorter people, increment count by 1
22            // This means the current person can see the next taller person
23            if (!heightStack.empty()) {
24                ++visibleCounts[i];
25            }
26          
27            // Push the current person's height into the stack
28            heightStack.push(heights[i]);
29        }
30      
31        return visibleCounts;  // Return the answer with counts of how many people each person can see
32    }
33};
34

1function canSeePersonsCount(heights: number[]): number[] {
2    const numHeights = heights.length;
3    const answer = new Array(numHeights).fill(0);
4    const stack: number[] = [];
5
6    // Iterate from the end of the heights array
7    for (let i = numHeights - 1; i >= 0; --i) {
8        // While there is a height in the stack smaller than the current height,
9        // pop it and increment the count for the current position
10        while (stack.length && stack[stack.length - 1] < heights[i]) {
11            answer[i]++;
12            stack.pop();
13        }
14
15        // If the stack is not empty after popping smaller elements, it means there
16        // is at least one higher person that the current person can see, so increment
17        // the count for the current position
18        if (stack.length) {
19            answer[i]++;
20        }
21
22        // Push the current height onto the stack
23        stack.push(heights[i]);
24    }
25
26    return answer;
27}
28

Time and Space Complexity

Time Complexity

The code iterates through the list of heights in reverse using a loop, resulting in O(n) where n is the length of the heights list. However, for each element, it potentially performs multiple comparisons and pop operations on the stack until a higher height is found or the stack is empty. In the worst-case scenario, each element will be pushed to and popped from the stack once, leading to an amortized time complexity of O(n). Thus, the overall time complexity is O(n).

Space Complexity

The space complexity is determined by the additional space used by the stack and the ans list. The ans list is the same size as the heights list, resulting in O(n) space complexity. The stack can also grow up to n in size in the worst case when heights are in ascending order, which also contributes O(n) space usage. The combined space complexity taking into account both the ans list and the stack is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: