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 arrayanswer of lengthn whereanswer[i]_is thenumber of people the _ith person cansee to their right in the queue.

Examples

Example 1

![](https://assets.leetcode.com/uploads/2021/05/29/queue-plane.jpg)

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

Method 1 – Monotonic Stack

Intuition

To count how many people each person can see to their right, process the queue from right to left using a stack. The stack keeps track of people who are visible and not blocked by a taller person. Each time a person is taller than the stack top, they can see the person and all people the stack top could see.

Approach

1. Initialize an empty stack and an answer array of zeros.
2. Iterate from right to left. For each person, pop from the stack while the current person is taller, incrementing the count for each pop.
3. If the stack is not empty after popping, increment the count by 1 (can see the next taller person).
4. Push the current person onto the stack.
5. Return the answer array.

Code

C++

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> ans(n);
        stack<int> st;
        for (int i = n-1; i >= 0; --i) {
            int cnt = 0;
            while (!st.empty() && heights[i] > heights[st.top()]) {
                cnt++;
                st.pop();
            }
            if (!st.empty()) cnt++;
            ans[i] = cnt;
            st.push(i);
        }
        return ans;
    }
};

Go

func canSeePersonsCount(heights []int) []int {
    n := len(heights)
    ans := make([]int, n)
    st := []int{}
    for i := n-1; i >= 0; i-- {
        cnt := 0
        for len(st) > 0 && heights[i] > heights[st[len(st)-1]] {
            cnt++
            st = st[:len(st)-1]
        }
        if len(st) > 0 { cnt++ }
        ans[i] = cnt
        st = append(st, i)
    }
    return ans
}

Java

class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] ans = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = n-1; i >= 0; i--) {
            int cnt = 0;
            while (!st.isEmpty() && heights[i] > heights[st.peek()]) {
                cnt++;
                st.pop();
            }
            if (!st.isEmpty()) cnt++;
            ans[i] = cnt;
            st.push(i);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun canSeePersonsCount(heights: IntArray): IntArray {
        val n = heights.size
        val ans = IntArray(n)
        val st = ArrayDeque<Int>()
        for (i in n-1 downTo 0) {
            var cnt = 0
            while (st.isNotEmpty() && heights[i] > heights[st.last()]) {
                cnt++
                st.removeLast()
            }
            if (st.isNotEmpty()) cnt++
            ans[i] = cnt
            st.addLast(i)
        }
        return ans
    }
}

Python

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

Rust

impl Solution {
    pub fn can_see_persons_count(heights: Vec<i32>) -> Vec<i32> {
        let n = heights.len();
        let mut ans = vec![0; n];
        let mut st = Vec::new();
        for i in (0..n).rev() {
            let mut cnt = 0;
            while let Some(&j) = st.last() {
                if heights[i] > heights[j] {
                    cnt += 1;
                    st.pop();
                } else {
                    break;
                }
            }
            if !st.is_empty() { cnt += 1; }
            ans[i] = cnt;
            st.push(i);
        }
        ans
    }
}

TypeScript

class Solution {
    canSeePersonsCount(heights: number[]): number[] {
        const n = heights.length
        const ans = new Array(n).fill(0)
        const st: number[] = []
        for (let i = n-1; i >= 0; i--) {
            let cnt = 0
            while (st.length && heights[i] > heights[st[st.length-1]]) {
                cnt++
                st.pop()
            }
            if (st.length) cnt++
            ans[i] = cnt
            st.push(i)
        }
        return ans
    }
}

Complexity

• ⏰ Time complexity: O(n), where n is the number of people in the queue.
• 🧺 Space complexity: O(n), for the stack and answer array.