< Back





1944. Number of Visible People in a Queue

This is a tough question because of the minor gotcha. This question requires a monotonically
decreasing stack. Whenever the current element is greater than the top of the stack, we pop. Each
element represents height, and we need to return how many people can be seen from the element at
certain index with their height. The gotcha is that if there's someone tall in the middle, the
people after are unseen by the tall person in the front.

A monotonically decreasing stack where we just subtract indices from each other isn't going to
suffice. Instead, we need to do a greedy calculation. When we add an element to the stack, if the
next element is shorter, we increment the number of people seen by the person at the top of the
stack. When we pop someone off of the stack, we go ahead and add to their number of people seen
because they can see the person taller than them about to be added to the stack.

The solution is as follows:


  class Solution:
      def canSeePersonsCount(self, heights: List[int]) -> List[int]:
          n = len(heights)
          stack, ans = [], [0] * n

          for i in range(n):
              while stack and heights[stack[-1]] < heights[i]:
                  ans[stack.pop()] += 1

              if stack:
                  ans[stack[-1]] += 1

              stack.append(i)

          return ans


_ Time Complexity:

  O(n) - We iterate through the list once.

_ Space Complexity:

  O(n) - We maintain a monotonically decreasing stack.