Number of Visible People in a Queue — DSA

Problem#

People stand in line with heights given by heights. Person i can see person j > i if min(heights[i..j-1]) < min(heights[i], heights[j]) — informally, no one taller stands between them. Return, for each person, how many people to their right they can see.

Examples#

heights = [10,6,8,5,11,9] → [3,1,2,1,1,0]
heights = [5,1,2,3,10] → [4,1,1,1,0]

Constraints#

n == heights.length, 1 <= n <= 10^5, all heights distinct, 1 <= heights[i] <= 10^5.

Approach#

Process right to left with a monotonic decreasing stack. For each person i, count the people they see: every shorter person on the stack is visible (pop and count), then if a taller person remains on the stack, they’re also visible (count one extra).

Solution#

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

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

from typing import List

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

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

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--) {
            while (!st.isEmpty() && st.peek() < heights[i]) {
                st.pop();
                ans[i]++;
            }
            if (!st.isEmpty()) ans[i]++;
            st.push(heights[i]);
        }
        return ans;
    }
}

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

Editorial#

Anyone shorter than i who would otherwise be visible from a later person is blocked once i joins the queue. So i sees the strictly-increasing prefix of the stack (popping each), plus the first taller person if any (the “blocker”). Each person is pushed and popped at most once.

Complexity#

Time: O(n).
Space: O(n).

Concept revision#

Daily Temperatures

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#