Number of Visible People in a Queue

How it works

We can also solve this by iterating from right to left. For each person, we count how many people they can see by popping shorter people from the stack (each popped person is visible). If someone taller remains on the stack after popping, that person is also visible since nothing blocks the view.

Steps

1. Initialize res array with zeros and an empty stack to store heights.
2. Iterate through heights from right to left:
   • While the stack is not empty and stack[-1] < heights[i], pop and increment res[i].
   • If the stack is not empty after popping, increment res[i] by 1 (the first taller or equal person is visible).
   • Push heights[i] onto the stack.
3. Return res.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Using the Wrong Stack Order

This problem requires a monotonic decreasing stack. Using an increasing stack or getting the comparison direction wrong leads to incorrect visibility counts. When iterating left-to-right, pop elements shorter than the current person; when iterating right-to-left, pop elements shorter than the current person as well.

Forgetting to Count the Blocking Person

When a taller person blocks the view, they are still visible to the current person. After popping all shorter people from the stack, if the stack is not empty, the person at the top is also visible. Forgetting to add 1 for this blocking person is a common mistake.

Confusing What to Store on the Stack

You can store either indices or heights on the stack, but you must be consistent. Storing indices allows you to update the result array directly but requires looking up heights. Storing heights simplifies comparisons but requires a different approach to update results.

Misunderstanding the Visibility Condition

Person i can see person j if there is no one between them who is taller than both. This is not the same as "no one taller than person j" or "no one taller than person i". The blocking condition depends on the minimum of the two heights being compared against the maximum height between them.

from typing import List

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        res = [0] * n
        stack = []

        for i in range(n - 1, -1, -1):
            while stack and stack[-1] < heights[i]:
                stack.pop()
                res[i] += 1

            if stack:
                res[i] += 1
            stack.append(heights[i])

        return res

class Solution {
public:
    vector<int> canSeePersonsCount(vector<int>& heights) {
        int n = heights.size();
        vector<int> res(n, 0);
        stack<int> st;

        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && st.top() < heights[i]) {
                st.pop();
                res[i]++;
            }
            if (!st.empty()) {
                res[i]++;
            }
            st.push(heights[i]);
        }

        return res;
    }
};