Number of Visible People in a Queue
There are n people standing in a queue, 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 i^th 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 i^th person can see the j^th 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 i^th person can see to their right in the queue.
Example 1
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # 10 6 8 5 11 9
Input
heights = [10,6,8,5,11,9]Output
[3,1,2,1,1,0]Person 0 can see people 1, 2, and 4; person 1 can see person 2; person 2 can see people 3 and 4; person 3 can see person 4; person 4 can see person 5; and person 5 can see no one.
Example 2
#
#
#
#
#
# #
# #
# # #
# # # #
# # # # #
5 1 2 3 10Input
heights = [5,1,2,3,10]Output
[4,1,1,1,0]Each person can see the listed number of people to their right according to the visibility rule.
Constraints
- n == heights.length
- 1 <= n <= 10^5
- 1 <= heights[i] <= 10^5
- All the values of heights are unique.
Asked at 17 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.