Number of Visible People in a Queue — LeetCode 1944 Python Solution

The problem

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.

Example

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.

Python solution

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

Complexity

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 1944. Number of Visible People in a Queue is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Related problems