Count Visible People to the Right
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
People stand from left to right with distinct heights given by `heights`. Person `i` can see person `j` to the right when every person strictly between them is shorter than both endpoints. Return an array containing, for each person, the number of people visible to their right.
```cpp
class Solution {
public:
vector<int> canSeePersonsCount(vector<int>& heights);
};
```
### Examples
**Example 1:**
```text
heights = [8,3,6,10]
Output: [3,1,1,0]
Explanation: Height 8 sees 3, then 6 over 3, then 10 over both smaller entries.
```
**Example 2:**
```text
heights = [9,7,5]
Output: [1,1,0]
Explanation: Each person sees only the immediate next person.
```
### Constraints
- `1 <= heights.length <= 10^5`.
- Heights are unique integers in `[1,10^5]`.
### Clarifying Questions
Immediate neighbors are always visible. Visibility is only toward the right.
```hint Inspect the structure
After encountering a person taller than the observer, can any later person remain visible?
```
### Reasoning checkpoints
- Apply the strict intervening-height rule to every counted pair, including adjacent people and the final person.
- Justify why no visible person is omitted and no person hidden by an intervening height is counted.
### Optional extensions
How would permitting repeated heights affect visibility and your approach?
Overview: Count Visible People to the Right. Distinct heights describe a left-to-right queue. Person i sees person j to the right exactly when every intervening height is strictly smaller than both endpoints. Return the number of people each person can see to the right.