# 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;
}
};```

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!