Count visible people to the right
Problem Description
You are given an array heights of length n, where heights[i] represents the height of the i-th person standing in a line from left to right.
For each index i, your task is to compute how many people to the right of person i are visible to them.
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. That is, heights[k] < min(heights[i], heights[j]) for all k between them.
An equivalent way to reason about this: looking from person i to the right, they can see a sequence of shorter people. They can also see the first person whose height is greater than or equal to heights[i]. Visibility stops beyond that point.
Input
- An integer array
heightsof sizen.
Output
- An integer array
ansof sizen, whereans[i]is the number of visible people to the right of personi.
Example
- Input:
heights = [10, 6, 8, 5, 11, 9] - Output:
[3, 1, 2, 1, 1, 0]
Constraints
1 <= n <= 1000001 <= heights[i] <= 10^9
AI interview prep
Core dilemma
Efficiently calculating right-side visibility with a complex 'shorter-in-between' rule, requiring an optimal O(N) solution given large input constraints, rather than a naive O(N^2) approach.
2 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Count visible people to the right
Problem Description
You are given an array heights of length n, where heights[i] represents the height of the i-th person standing in a line from left to right.
For each index i, your task is to compute how many people to the right of person i are visible to them.
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. That is, heights[k] < min(heights[i], heights[j]) for all k between them.
An equivalent way to reason about this: looking from person i to the right, they can see a sequence of shorter people. They can also see the first person whose height is greater than or equal to heights[i]. Visibility stops beyond that point.
Input
- An integer array
heightsof sizen.
Output
- An integer array
ansof sizen, whereans[i]is the number of visible people to the right of personi.
Example
- Input:
heights = [10, 6, 8, 5, 11, 9] - Output:
[3, 1, 2, 1, 1, 0]
Constraints
1 <= n <= 1000001 <= heights[i] <= 10^9