1944. Number of Visible People in a Queue - Explanation

Problem Link

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 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 = [3,1,5,8,6]

Output: [2,1,1,1,0]

Explanation:
Person 0 can see person 2 and 3.
Person 1 can see person 2.
Person 2 can see person 3.
Person 3 can see person 4.
Person 4 can see no one since nobody is to the right of them.

Constraints:

• n == heights.length
• 1 <= n, heights[i] <= 100,000
• All the values of heights are unique.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        n = len(heights)
        res = []

        for i in range(n):
            maxi = cnt = 0
            for j in range(i + 1, n):
                if min(heights[i], heights[j]) > maxi:
                    cnt += 1
                maxi = max(maxi, heights[j])

            res.append(cnt)

        return res

Time & Space Complexity

• Time complexity: $O(n ^ 2)$
• Space complexity: $O(n)$ for the output array.

---

2. Stack - I

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

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

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Stack - II

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

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

            if stack:
                res[i] += 1
            stack.append(heights[i])

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$