Count visible people to the right
Company: Ge
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given an array `heights` of length `n`, where `heights[i]` is the height of the `i`-th person standing in a line from left to right.
For each index `i`, compute how many people to the **right** of `i` are **visible** to person `i`.
### Visibility rule
Person `i` can see person `j` (`j > i`) if **every** person `k` with `i < k < j` is shorter than **both** `i` and `j`:
- `heights[k] < min(heights[i], heights[j])` for all `k` between them.
Equivalently (often easier to reason about): looking from `i` to the right, person `i` can see a sequence of shorter people, and they can also see the first person whose height is **greater than or equal to** `heights[i]` (and then visibility stops beyond that point).
### Input
- Integer array `heights` (size `n`).
### Output
- Integer array `ans` of size `n` where `ans[i]` is the number of visible people to the right of person `i`.
### Example
- Input: `heights = [10, 6, 8, 5, 11, 9]`
- Output: `[3, 1, 2, 1, 1, 0]`
### Constraints
- `1 <= n <= 100000`
- `1 <= heights[i] <= 10^9`
Quick Answer: This question evaluates algorithmic problem-solving with arrays and visibility relations, assessing competency in array traversal, handling of relative ordering constraints, and designing time- and space-efficient approaches.
You are given an array `heights` of length `n`, where `heights[i]` is the height of the `i`-th person standing in a line from left to right.
For each index `i`, compute how many people to the **right** of `i` are **visible** to person `i`.
**Visibility rule:** Person `i` can see person `j` (`j > i`) if and only if every person `k` strictly between them is shorter than **both** endpoints:
`heights[k] < min(heights[i], heights[j])` for all `k` with `i < k < j`.
Return an integer array `ans` of size `n` where `ans[i]` is the number of visible people to the right of person `i`.
**Example:**
- Input: `heights = [10, 6, 8, 5, 11, 9]`
- Output: `[3, 1, 2, 1, 1, 0]`
From index 0 (height 10): sees 6, then 8 (the 6 between is < min(10,8)), then 11 (everything between is < 10), but visibility stops at 11 since 11 >= 10. So 3 people.
Constraints
- 1 <= n <= 100000
- 1 <= heights[i] <= 10^9
Examples
Input: [10, 6, 8, 5, 11, 9]
Expected Output: [3, 1, 2, 1, 1, 0]
Explanation: Index 0 (h=10) sees 6, 8, and 11 (11 >= 10 stops it) -> 3. Index 2 (h=8) sees 5 and 11 -> 2. The last person sees no one to the right -> 0.
Input: []
Expected Output: []
Explanation: Empty line: no people, so the answer array is empty.
Hints
- Process the array from right to left while maintaining a stack of candidate heights.
- From person i, you can see a run of people whose heights strictly increase, plus the first person who is at least as tall as i (that person blocks everyone behind them).
- Pop every height on the stack that is strictly less than heights[i] (each popped person is visible). If the stack is still non-empty afterward, that top person (height >= heights[i]) is also visible — add one more.
- Keep the stack strictly decreasing: before pushing heights[i], also remove any equal heights. This is what makes ties block correctly, e.g. [2,1,1,3] gives 2 (not 3) for index 0 because the second 1 hides the first.