Number of Visible People in a Queue
01 · Problem
n people stand in a line from left to right, and heights[i] is the height of the person at position i. All heights are distinct.
Each person looks to the right. Person i can see person j (with i < j) when every person strictly between them is shorter than both heights[i] and heights[j]. In particular, a person can always see their immediate right neighbour.
Return an array answer of length n where answer[i] is the number of people that person i can see.
02 · Examples
heights = [10,6,8,5,11,9]
[3,1,2,1,1,0]
Person 0 (height 10) sees persons 1, 2 and 4. Person 1 sees only person 2. Person 2 sees persons 3 and 4. Person 3 sees person 4. Person 4 sees person 5. Person 5 has nobody to the right.
heights = [5,1,2,3,10]
[4,1,1,1,0]
Person 0 sees everyone because each person in between is shorter than both ends. Persons 1, 2 and 3 each see only the next person, who is taller and blocks the rest.
heights = [4,3,2,1]
[1,1,1,0]
In a strictly decreasing line each person sees only the neighbour directly to the right, since that neighbour blocks everyone further away.
03 · Constraints
- 011 <= heights.length <= 105
- 021 <= heights[i] <= 105
- 03All values in heights are distinct
04 · Optimal complexity
- Time
- O(n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.