Number of Visible People in a Queue

Hard

#1773Time: O(N^2) in the worst case. The two nested loops give it a quadratic time complexity. For an input where heights are in descending order, the inner loop runs close to N times for each element of the outer loop.Space: O(1) auxiliary space. We only use a few variables to keep track of counts and maximum heights. The output array `answer` is not considered part of the auxiliary space.6 companies

Data structures

Array Stack Monotonic Stack

Companies

DoorDash Expedia ServiceNow Rippling

Prompt

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 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:

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 <= 10⁵
1 <= heights[i] <= 10⁵
All the values of heights are unique.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process for each person. We iterate through each person i from left to right. For each person i, we then scan all the people j to their right to count how many are visible. A key optimization is to stop scanning once we find a person taller than or equal to the current person i, as they will block the view of anyone further to the right.

Algorithm

Create an integer array answer of size n, initialized to zeros.
Loop i from 0 to n-1:
- Initialize count = 0.
- Initialize maxHeightOnRight = 0.
- Loop j from i + 1 to n-1:
  - Check if person j is visible from i. The condition is min(heights[i], heights[j]) > maxHeightOnRight, where maxHeightOnRight stores the maximum height of people from i+1 to j-1.
  - If the condition is met, increment count.
  - Update maxHeightOnRight = max(maxHeightOnRight, heights[j]).
  - If a person j is found such that heights[j] >= heights[i], it means i cannot see anyone beyond j. So, we can break the inner loop.
- answer[i] = count.
Return answer.

Walkthrough

We initialize an answer array of the same size as heights to store the results. The main logic consists of two nested loops. The outer loop iterates through each person i from 0 to n-1. The inner loop iterates through each person j to the right of i.

To apply the visibility rule min(heights[i], heights[j]) > max(heights[i+1], ..., heights[j-1]), we need the maximum height in the interval (i, j). Instead of recalculating this maximum for each j, we can maintain a running maximum of the heights encountered so far to the right of i. Let's call this maxHeightOnRight. For a fixed i, as we increment j, maxHeightOnRight at the beginning of the loop for j represents max(heights[i+1], ..., heights[j-1]).

If min(heights[i], heights[j]) > maxHeightOnRight, person j is visible to i, and we increment our count. After checking, we update maxHeightOnRight with heights[j] for the next iteration. A crucial optimization is that if we encounter a person j who is taller than or equal to person i, then person i cannot see anyone beyond j. This is because j will block the view. So, we can break the inner loop as soon as heights[j] is greater than or equal to heights[i].

1class Solution {2    public int[] canSeePersonsCount(int[] heights) {3        int n = heights.length;4        int[] answer = new int[n];5        for (int i = 0; i < n; i++) {6            int count = 0;7            int maxHeightOnRight = 0;8            for (int j = i + 1; j < n; j++) {9                if (Math.min(heights[i], heights[j]) > maxHeightOnRight) {10                    count++;11                }12                if (heights[j] >= heights[i]) {13                    break;14                }15                maxHeightOnRight = Math.max(maxHeightOnRight, heights[j]);16            }17            answer[i] = count;18        }19        return answer;20    }21}

Complexity

Time

O(N^2) in the worst case. The two nested loops give it a quadratic time complexity. For an input where heights are in descending order, the inner loop runs close to N times for each element of the outer loop.

Space

O(1) auxiliary space. We only use a few variables to keep track of counts and maximum heights. The output array `answer` is not considered part of the auxiliary space.

Trade-offs

Pros

The logic is straightforward and directly follows the problem definition.
It's easy to implement.
It has a very low auxiliary space complexity.

Cons

The O(N^2) time complexity makes it too slow for large inputs, as specified by the problem constraints (N up to 10^5). It will likely result in a 'Time Limit Exceeded' error.

A much more efficient solution can be achieved using a monotonic stack. By processing the people from right to left, we can determine the number of visible people for each person in a single pass. The stack is used to maintain a sequence of people to the right whose heights are in decreasing order. This structure allows for efficient calculation of visibility.

Algorithm

Create an integer array answer of size n.
Create an empty stack (e.g., ArrayDeque) to store heights.
Loop i from n-1 down to 0:
- Initialize visibleCount = 0.
- While the stack is not empty and stack.peek() < heights[i]:
  - This means the person on top of the stack is shorter and visible.
  - Pop from the stack.
  - Increment visibleCount.
- If the stack is not empty after the loop, it means there is a person taller than heights[i]. This person is also visible.
  - Increment visibleCount.
- Store the result: answer[i] = visibleCount.
- Push heights[i] onto the stack to maintain the monotonically decreasing property.
Return answer.

Walkthrough

This approach iterates through the heights array from right to left. A stack is used to keep track of the heights of people encountered so far. The stack will be maintained in a monotonically decreasing order from top to bottom (i.e., stack.peek() is the smallest element).

For each person i at heights[i], we determine how many people they can see to their right:

We look at the people on the stack. These are people to the right of i. As long as the person on top of the stack is shorter than person i (stack.peek() < heights[i]), person i can see them. This is because any person between i and the one on the stack must be even shorter (otherwise the one on the stack would have been popped earlier). We pop these shorter people and count them.
After popping all shorter people, if the stack is not empty, the person at the top is the first person to the right of i who is taller than or equal to i. Person i can see this one taller person, but no one beyond them. So, we increment the count by one more.
The total count is then the answer for person i.
Finally, we push heights[i] onto the stack. This preserves the monotonic property, as all smaller elements have been removed.

This process ensures that each person's height is pushed and popped at most once, leading to an overall linear time complexity.

1import java.util.ArrayDeque;2import java.util.Deque;3 4class Solution {5    public int[] canSeePersonsCount(int[] heights) {6        int n = heights.length;7        int[] answer = new int[n];8        // The stack will store heights in monotonically decreasing order from top to bottom.9        Deque<Integer> stack = new ArrayDeque<>();10        11        for (int i = n - 1; i >= 0; i--) {12            int currentHeight = heights[i];13            int visibleCount = 0;14            15            // Pop all people from the stack who are shorter than the current person.16            // The current person can see all of them.17            while (!stack.isEmpty() && stack.peek() < currentHeight) {18                stack.pop();19                visibleCount++;20            }21            22            // If there's still a person on the stack, that person is taller23            // than or equal to the current person. The current person can see this one person.24            if (!stack.isEmpty()) {25                visibleCount++;26            }27            28            answer[i] = visibleCount;29            30            // Push the current person's height onto the stack.31            stack.push(currentHeight);32        }33        34        return answer;35    }36}

Complexity

Time

O(N). We iterate through the array once. Each element is pushed onto the stack exactly once and popped at most once. Thus, the total time spent on stack operations across all iterations is O(N).

Space

O(N). In the worst-case scenario (e.g., a strictly decreasing array of heights like `[5, 4, 3, 2, 1]`), the stack can hold up to `N` elements.

Trade-offs

Pros

Highly efficient with a linear time complexity of O(N).
It's the optimal solution for the given constraints.

Cons

The logic can be less intuitive to come up with compared to the brute-force approach.
It requires extra space for the stack, which can be up to O(N) in the worst case.

Solutions

Solution

1class Solution {2public3  int[] canSeePersonsCount(int[] heights) {4    int n = heights.length;5    int[] ans = new int[n];6    Deque<Integer> stk = new ArrayDeque<>();7    for (int i = n - 1; i >= 0; --i) {8      while (!stk.isEmpty() && stk.peek() < heights[i]) {9        stk.pop();10        ++ans[i];11      }12      if (!stk.isEmpty()) {13        ++ans[i];14      }15      stk.push(heights[i]);16    }17    return ans;18  }19}

1class Solution {2public:3  vector<int> canSeePersonsCount(vector<int> &heights) {4    int n = heights.size();5    vector<int> ans(n);6    stack<int> stk;7    for (int i = n - 1; ~i; --i) {8      while (stk.size() && stk.top() < heights[i]) {9        ++ans[i];10        stk.pop();11      }12      if (stk.size()) {13        ++ans[i];14      }15      stk.push(heights[i]);16    }17    return ans;18  }19};

1class Solution:2    def canSeePersonsCount(self, heights: List[int]) -> List[int]: n = len(heights) ans = [0] * n stk = [] for i in range(n - 1, - 1, - 1): while stk and stk[- 1] < heights[i]: ans[i] += 1 stk . pop() if stk: ans[i] += 1 stk . append(heights[i]) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem