Number of Visible People in a Queue
Problem Description
There are n people standing in a queue, and they 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 ith 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 ith person can see the jth 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 ith person can see to their right in the queue.
Example 1:
Input: heights = [10,6,8,5,11,9]
Output: [3,1,2,1,1,0]
Explanation:
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.Person 5 can see no one since nobody is to the right of them.
Example 2:
Input: heights = [5,1,2,3,10]
Output: [4,1,1,1,0]
Constraints:
- n == heights.length
- 1 <= n <= 105
- 1 <= heights[i] <= 105
- All the values of
heightsare unique.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
The simplest way to solve this problem is to use a double loop. For each person in the queue, we can look at each subsequent person and determine if they're visible. A person is visible if all the people between them and the current person in the focus are shorter. Once we find a taller person, all subsequent people are not visible.
Algorithm:
- Initialize an array
resultto store the number of visible people for each person in the queue. - For each person in the queue located at index
i, look at each subsequent personj(wherej > i). - If the person at
jis taller than the person ati, they are visible, and we can break out of the loop since no one beyond them can be visible to personi. - Continue counting visible people for person
iuntil a taller person is encountered. - Repeat for all people in the queue.
Code:
- Time Complexity: O(n^2), where n is the number of people in the queue. We use a double loop to check visibility.
- Space Complexity: O(1) extra space, apart from the output array
result.
2. Monotonic Stack
Intuition:
To reduce the time complexity, we can use a stack to maintain a list of indices. This stack helps us efficiently track the tallest visible people as we traverse the queue from right to left. By using a stack, we can keep removing shorter people who are no longer visible whenever we encounter a taller person farther in the queue.
Algorithm:
- Initialize a stack to keep indices and an array
resultto store answer. - Traverse the queue from right to left.
- For each person encountered:
- Pop persons from the stack while the current person is taller, since they won't be visible anymore.
- Count the popped persons as visible.
- If the stack isn't empty, it means there's a person who is taller than the current one, making them visible as well.
- Push the current person's index onto the stack.
- Repeat until the whole queue is processed.
Code:
- Time Complexity: O(n), where n is the number of people in the queue. Each person is pushed and popped from the stack at most once.
- Space Complexity: O(n), for the stack that keeps track of indices.