Number of Visible People in a Queue

hard monotonic stack

Problem

There are n people in a queue, all with distinct heights, listed left to right in heights. Person i can see person j to their right when everyone standing between them is shorter than both of them (formally, min(heights[i], heights[j]) > max of the heights in between).

Return an array answer where answer[i] is the number of people the i-th person can see looking to their right.

Inputheights = [10, 6, 8, 5, 11, 9]

Output[3, 1, 2, 1, 1, 0]

Person 0 (height 10) sees 6, 8 and 11: the 5 hides behind 8, and 11 blocks everyone past it.

heights (comma-separated, distinct)

def can_see_persons_count(heights):
    n = len(heights)
    ans = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and stack[-1] < heights[i]:
            stack.pop()
            ans[i] += 1
        if stack:
            ans[i] += 1
        stack.append(heights[i])
    return ans

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

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

vector<int> canSeePersonsCount(vector<int>& heights) {
    int n = heights.size();
    vector<int> ans(n, 0);
    vector<int> stack;
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.empty() && stack.back() < heights[i]) {
            stack.pop_back();
            ans[i]++;
        }
        if (!stack.empty()) ans[i]++;
        stack.push_back(heights[i]);
    }
    return ans;
}

Explanation

The key insight is to ask the question backwards: instead of "who can person i see?", ask "when person i arrives from the right, who becomes invisible?" Scanning right-to-left with a monotonic decreasing stack answers both at once. The stack holds the people to the right of i who are still visible from position i — and because anyone shorter standing behind someone taller is hidden, those visible heights are strictly increasing toward the right, i.e. the stack is decreasing from bottom to top.

For each person i, pop every stack entry shorter than heights[i]. Each popped person is someone i can see: nothing between them was tall enough to block (or it would still be on the stack), and once i arrives, that shorter person can never be seen by anyone further left — i stands in front of them. That is exactly why each element is pushed once and popped at most once.

After the pops, if the stack is non-empty its top is the first person taller than i to the right. Person i sees that one taller person too — and nobody beyond, because the taller person blocks the view. So ans[i] = pops + 1 when someone taller remains, and just pops when the stack is empty. Finally push heights[i].

Walk through heights = [10, 6, 8, 5, 11, 9]. Person 5 (9): empty stack, sees 0. Person 4 (11): pops 9 (sees it), stack empty, ans[4] = 1. Person 3 (5): no pops, 11 towers above, ans[3] = 1. Person 2 (8): pops 5, then 11 blocks, ans[2] = 2. Person 1 (6): no pops, 8 blocks, ans[1] = 1. Person 0 (10): pops 6 and 8, then 11 blocks, ans[0] = 3. Answer: [3, 1, 2, 1, 1, 0].

Although the inner while loop looks quadratic, each height enters the stack exactly once and leaves at most once, so the total work across all iterations is linear: O(n) time. The stack itself holds at most n heights, giving O(n) extra space (plus the output array).

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