Code Implementation

class Solution:
    def canSeePersonsCount(self, heights):
        n = len(heights)
        res = [0] * n
        stack = []
        for i in range(n - 1, -1, -1):
            count = 0
            while stack and heights[i] > stack[-1]:
                stack.pop()
                count += 1
            if stack:
                count += 1
            res[i] = count
            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) {
            int count = 0;
            while (!st.empty() && heights[i] > st.top()) {
                st.pop();
                count++;
            }
            if (!st.empty()) count++;
            res[i] = count;
            st.push(heights[i]);
        }
        return res;
    }
};
      

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

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

Problem Description

You are given an array heights representing the heights of people standing in a queue from left to right. For each person, you need to count how many people standing to their right are "visible" to them. A person is visible if everyone between them is shorter, and the visible person must be the first taller or equal person (if any), or any strictly shorter person before that.

• For each index i, count the number of people to the right of i that the person at i can "see".
• A person at index i can see another at index j > i if every person between i and j is shorter than heights[i], and heights[j] is taller or equal to any person between.
• Return an array of the same length as heights with the number of visible people for each index.

Thought Process

At first glance, you might think to check, for every person, all people to their right and count how many are visible by checking the heights in between. This leads to a brute-force approach with nested loops. However, this is inefficient for large arrays.

On further thought, the problem is similar to "Next Greater Element" and can be solved efficiently using a stack. The key insight is that once a taller person is found, you can't see anyone beyond them unless they're taller still. By processing from right to left and using a stack to keep track of potential visible people, we can efficiently count visible persons for each index.

Solution Approach

• We process the heights array from right to left (from the end to the start).
• We use a stack to keep track of the people to the right of the current person.
• For each person at index i:
  • We count and pop all people in the stack who are shorter than the current person. Each pop represents a visible person.
  • If there is someone left in the stack (taller than the current person), they are also visible since the current person can see until their view is blocked.
  • We then push the current person's height onto the stack for future comparisons.
• This ensures each person is only pushed and popped from the stack once, making the algorithm efficient.

Example Walkthrough

Let's consider heights = [10, 6, 8, 5, 11, 9]:

1. Start from the rightmost (index 5, height 9): The stack is empty, so 0 visible. Push 9.
2. Index 4 (height 11): Stack top is 9 (shorter), pop it (visible). Stack is now empty, so only 1 visible. Push 11.
3. Index 3 (height 5): Stack top is 11 (taller), so 1 visible. Push 5.
4. Index 2 (height 8): Stack top is 5 (shorter), pop it (visible). Next stack top is 11 (taller), so 1 more visible. Total 2 visible. Push 8.
5. Index 1 (height 6): Stack top is 8 (taller), so 1 visible. Push 6.
6. Index 0 (height 10): Stack top is 6 (shorter), pop it (visible). Next stack top is 8 (shorter), pop it (visible). Next stack top is 11 (taller), so 1 more visible. Total 3 visible. Push 10.

The result is [3, 1, 2, 1, 1, 0].

Time and Space Complexity

• Brute-force approach: For each person, check every person to their right, leading to O(n^2) time complexity.
• Optimized stack-based approach: Each person is pushed and popped at most once from the stack, so the time complexity is O(n).
• The space complexity for the stack is O(n) in the worst case.

Summary

By recognizing the similarity to "Next Greater Element" problems, we efficiently solved the "Number of Visible People in a Queue" using a stack and a right-to-left traversal. The stack allows us to count visible people for each index in linear time, making the solution both elegant and efficient for large inputs.