Number of Visible People in a Queue

Leetcode 1944. Number of Visible People in a Queue

Problem

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

We can start from the end of the queue and keep height of persons in a stack. Before moving to the next person, we can check if there is anyone in the stack who is lower than me. We can remove them and add them to my visible person list. Because, I can see people who are of lower hight than myself, right?

Also, I can see people who is infant of me and has a higher height. So, if we do not find anyone smaller than me in the stack and the stack is not empty, that means there is someone in the stack higher than me. So, we will add the visibility counter and stop checking the stack.

Below code is an implementation of this discussion.

C++ Code

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int N = heights.size();
        if(N == 0)
            return {};
        vector<int> ans(N, 0);
        stack<int> st;
        
        //we start from the last person
        for(int i = N - 1; i >= 0; i--){
            int total_infront_of_me = 0;
            /* 
            when someone is in stack,
            we will increse total_infront_of_me by 1
            */
            while(!st.empty()){
                total_infront_of_me++;
                if(st.top() < heights[i]) //If that person's height is smaller than me, we remove that person from stack and continue exploring the stack
                    st.pop();
                else //else we will not remove that person from stack neither explore stack any more. Because, that person's height is greater than me, so, I won't be able to see anyone after him
                    break;     
            }
            //finally, update my total person visibility
            ans[i] = total_infront_of_me;
            st.push(heights[i]);        
        }
        return ans;
    }
};

Conclusion

If you like this post or hate it, please write your opinion in the comment section. For more posts like this, please check below or go to the home page.

Happy Coding! 🙂

Bonus – System Design!

ByteByteGo is by far the best system design resource found on the internet. They are growing like crazy!

We suggest you checkout their course if you really want to dive deep in system design and want to have a killer interview!

Here is the link: ByteByteGo!

Disclaimer: this is a genuine suggestion, but we have some interest too! We get commission if you buy their course. However, there are other courses online which we do not promote. Because we promote only things that are the best in our opinion and those we really feel will be helpful for you.