Table of Contents

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 `i`

person.^{th}

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`

person can see the ^{th}`j`

person if ^{th}`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`

^{5}`1 <= heights[i] <= 10`

^{5}- 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! 🙂