# Number of Visible People in a Queue
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-visible-people-in-a-queue)
Canonical: https://scaleengineer.com/dsa/problems/number-of-visible-people-in-a-queue
**Data structures:** Array, Stack, Monotonic Stack
**Companies:** [DoorDash](https://scaleengineer.com/companies/doordash), [Expedia](https://scaleengineer.com/companies/expedia), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Rippling](https://scaleengineer.com/companies/rippling), [GE Healthcare](https://scaleengineer.com/companies/ge-healthcare), [Citigroup](https://scaleengineer.com/companies/citigroup)
---
## 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 array_ `answer` _of length_ `n` _where_ `answer[i]` _is the **number of people** the_ `ith` _person can **see** to their right in the queue_.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-visible-people-in-a-queue/image0.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 <= 105`
* `1 <= heights[i] <= 105`
* All the values of `heights` are **unique**.

# Approaches
## Brute Force with Optimization
This approach directly simulates the process for each person. We iterate through each person `i` from left to right. For each person `i`, we then scan all the people `j` to their right to count how many are visible. A key optimization is to stop scanning once we find a person taller than or equal to the current person `i`, as they will block the view of anyone further to the right.
**Time:** O(N^2) in the worst case. The two nested loops give it a quadratic time complexity. For an input where heights are in descending order, the inner loop runs close to N times for each element of the outer loop. · **Space:** O(1) auxiliary space. We only use a few variables to keep track of counts and maximum heights. The output array `answer` is not considered part of the auxiliary space.
**Pros:** The logic is straightforward and directly follows the problem definition.; It's easy to implement.; It has a very low auxiliary space complexity.
**Cons:** The O(N^2) time complexity makes it too slow for large inputs, as specified by the problem constraints (N up to 10^5). It will likely result in a 'Time Limit Exceeded' error.
### Explanation
We initialize an `answer` array of the same size as `heights` to store the results. The main logic consists of two nested loops. The outer loop iterates through each person `i` from `0` to `n-1`. The inner loop iterates through each person `j` to the right of `i`.

To apply the visibility rule `min(heights[i], heights[j]) > max(heights[i+1], ..., heights[j-1])`, we need the maximum height in the interval `(i, j)`. Instead of recalculating this maximum for each `j`, we can maintain a running maximum of the heights encountered so far to the right of `i`. Let's call this `maxHeightOnRight`. For a fixed `i`, as we increment `j`, `maxHeightOnRight` at the beginning of the loop for `j` represents `max(heights[i+1], ..., heights[j-1])`.

If `min(heights[i], heights[j]) > maxHeightOnRight`, person `j` is visible to `i`, and we increment our count. After checking, we update `maxHeightOnRight` with `heights[j]` for the next iteration. A crucial optimization is that if we encounter a person `j` who is taller than or equal to person `i`, then person `i` cannot see anyone beyond `j`. This is because `j` will block the view. So, we can break the inner loop as soon as `heights[j]` is greater than or equal to `heights[i]`.

```java
class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            int count = 0;
            int maxHeightOnRight = 0;
            for (int j = i + 1; j < n; j++) {
                if (Math.min(heights[i], heights[j]) > maxHeightOnRight) {
                    count++;
                }
                if (heights[j] >= heights[i]) {
                    break;
                }
                maxHeightOnRight = Math.max(maxHeightOnRight, heights[j]);
            }
            answer[i] = count;
        }
        return answer;
    }
}
```
### Algorithm
- Create an integer array `answer` of size `n`, initialized to zeros.
- Loop `i` from `0` to `n-1`:
  - Initialize `count = 0`.
  - Initialize `maxHeightOnRight = 0`.
  - Loop `j` from `i + 1` to `n-1`:
    - Check if person `j` is visible from `i`. The condition is `min(heights[i], heights[j]) > maxHeightOnRight`, where `maxHeightOnRight` stores the maximum height of people from `i+1` to `j-1`.
    - If the condition is met, increment `count`.
    - Update `maxHeightOnRight = max(maxHeightOnRight, heights[j])`.
    - If a person `j` is found such that `heights[j] >= heights[i]`, it means `i` cannot see anyone beyond `j`. So, we can break the inner loop.
  - `answer[i] = count`.
- Return `answer`.

## Monotonic Stack
A much more efficient solution can be achieved using a monotonic stack. By processing the people from right to left, we can determine the number of visible people for each person in a single pass. The stack is used to maintain a sequence of people to the right whose heights are in decreasing order. This structure allows for efficient calculation of visibility.
**Time:** O(N). We iterate through the array once. Each element is pushed onto the stack exactly once and popped at most once. Thus, the total time spent on stack operations across all iterations is O(N). · **Space:** O(N). In the worst-case scenario (e.g., a strictly decreasing array of heights like `[5, 4, 3, 2, 1]`), the stack can hold up to `N` elements.
**Pros:** Highly efficient with a linear time complexity of O(N).; It's the optimal solution for the given constraints.
**Cons:** The logic can be less intuitive to come up with compared to the brute-force approach.; It requires extra space for the stack, which can be up to O(N) in the worst case.
### Explanation
This approach iterates through the `heights` array from right to left. A stack is used to keep track of the heights of people encountered so far. The stack will be maintained in a monotonically decreasing order from top to bottom (i.e., `stack.peek()` is the smallest element).

For each person `i` at `heights[i]`, we determine how many people they can see to their right:
1.  We look at the people on the stack. These are people to the right of `i`. As long as the person on top of the stack is shorter than person `i` (`stack.peek() < heights[i]`), person `i` can see them. This is because any person between `i` and the one on the stack must be even shorter (otherwise the one on the stack would have been popped earlier). We pop these shorter people and count them.
2.  After popping all shorter people, if the stack is not empty, the person at the top is the first person to the right of `i` who is taller than or equal to `i`. Person `i` can see this one taller person, but no one beyond them. So, we increment the count by one more.
3.  The total count is then the answer for person `i`.
4.  Finally, we push `heights[i]` onto the stack. This preserves the monotonic property, as all smaller elements have been removed.

This process ensures that each person's height is pushed and popped at most once, leading to an overall linear time complexity.

```java
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] answer = new int[n];
        // The stack will store heights in monotonically decreasing order from top to bottom.
        Deque<Integer> stack = new ArrayDeque<>();
        
        for (int i = n - 1; i >= 0; i--) {
            int currentHeight = heights[i];
            int visibleCount = 0;
            
            // Pop all people from the stack who are shorter than the current person.
            // The current person can see all of them.
            while (!stack.isEmpty() && stack.peek() < currentHeight) {
                stack.pop();
                visibleCount++;
            }
            
            // If there's still a person on the stack, that person is taller
            // than or equal to the current person. The current person can see this one person.
            if (!stack.isEmpty()) {
                visibleCount++;
            }
            
            answer[i] = visibleCount;
            
            // Push the current person's height onto the stack.
            stack.push(currentHeight);
        }
        
        return answer;
    }
}
```
### Algorithm
- Create an integer array `answer` of size `n`.
- Create an empty stack (e.g., `ArrayDeque`) to store heights.
- Loop `i` from `n-1` down to `0`:
  - Initialize `visibleCount = 0`.
  - While the stack is not empty and `stack.peek() < heights[i]`:
    - This means the person on top of the stack is shorter and visible.
    - Pop from the stack.
    - Increment `visibleCount`.
  - If the stack is not empty after the loop, it means there is a person taller than `heights[i]`. This person is also visible.
    - Increment `visibleCount`.
  - Store the result: `answer[i] = visibleCount`.
  - Push `heights[i]` onto the stack to maintain the monotonically decreasing property.
- Return `answer`.

# Solutions
### Java

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

```

### CPP

```cpp
class Solution {
public:
  vector<int> canSeePersonsCount(vector<int> &heights) {
    int n = heights.size();
    vector<int> ans(n);
    stack<int> stk;
    for (int i = n - 1; ~i; --i) {
      while (stk.size() && stk.top() < heights[i]) {
        ++ans[i];
        stk.pop();
      }
      if (stk.size()) {
        ++ans[i];
      }
      stk.push(heights[i]);
    }
    return ans;
  }
};

```

### Python

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

```