Hard

Number of Visible People in a Queue

LAB

For each person, return how many people to their right are visible before a taller or equal-height person blocks the view.

EXAMPLES

Example 1

Input
{
  "heights": [
    10,
    6,
    8,
    5,
    11,
    9
  ]
}

Output
[
  3,
  1,
  2,
  1,
  1,
  0
]

FUNCTION SHAPE

heights: intArray→intArray

SOLUTION NOTE

NG template with a twist. When we pop, that person can see current person. The "if stack" handles when stack top is taller but can still see current person.

Reveal reference solution +

pythonREFERENCE

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

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

    return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗