LeetCode 1944 - Number of Visible People in a Queue

LeetCode Problem 1944

Difficulty: 🔴 Hard
Topics: Array, Stack, Monotonic Stack

Solution

Problem Understanding

The problem gives a queue of n people standing from left to right, where each person has a distinct height. For each person i, we need to determine how many people to their right they can see.

A person i can see a person j (with j > i) if every person between them is strictly shorter than both endpoints, meaning the tallest person in the interval (i+1 ... j-1) is smaller than min(heights[i], heights[j]). In simpler terms, visibility is blocked only when there is an intermediate person taller than or equal to the limiting height between the two endpoints.

The output is an array answer where answer[i] represents how many people to the right of index i are visible under this rule.

The constraints are significant: n can be up to 10^5, so an O(n^2) solution is too slow. Heights are distinct, which simplifies comparisons because we do not need to handle ties.

Important edge cases include a strictly decreasing sequence, where each person can see many others, and a strictly increasing sequence, where each person sees only the first taller person. Another key edge case is the last element, which always sees zero people because no one is to the right.

Approaches

Brute Force Approach

The brute-force method iterates from each index i to the right, scanning every j > i and checking whether j is visible. To determine visibility, we maintain the maximum height seen between i and j, and ensure it never exceeds min(heights[i], heights[j]). If visibility holds, we increment the count for i.

This approach is correct because it directly simulates the definition of visibility. However, for each i, we may scan up to n elements, and maintaining intermediate maxima leads to repeated work, making it too slow for large inputs.

Optimal Approach: Monotonic Stack from Right to Left

The key insight is that for each person i, only certain people to the right can contribute to visibility:

1. The first person taller than heights[i] is always visible (because no taller blocker exists between them).
2. After that, shorter people may also be visible, but they are "consumed" in a chain-like manner.
3. A monotonic decreasing stack (from right to left perspective) helps efficiently track candidates that are visible or block visibility.

We traverse from right to left, maintaining a stack of indices with decreasing heights. For each person i, we repeatedly pop shorter people from the stack, counting them as visible. If the stack is not empty afterward, the top element is also visible (the first taller blocker), so we count it as well.

This works because once a shorter person is popped, they cannot block anyone further left, and taller people naturally dominate visibility boundaries.

Comparison Table

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Checks visibility for every pair directly
Optimal Monotonic Stack	O(n)	O(n)	Each element pushed and popped at most once

Algorithm Walkthrough

1. Initialize an empty stack that will store indices of people to the right. The stack will maintain a decreasing height structure, meaning heights from top to bottom are strictly decreasing. This structure ensures we always know the nearest taller candidates efficiently.
2. Create an answer array initialized with zeros. This will store visibility counts for each person.
3. Iterate from right to left over the array. We go right-to-left because we want to progressively build knowledge of what each person can see among already-processed people.
4. For each person i, initialize a local counter count = 0. This counter will track how many people i can see.
5. While the stack is not empty and the current person is taller than the person at the top of the stack, pop the stack and increment count. Each popped person is visible because no taller blocker exists between i and that person.
6. If the stack is still not empty after popping, it means there is a taller person blocking further view but still visible to i. Increment count once more to account for this first taller person.
7. Push the current index i onto the stack so it becomes a potential visible candidate for earlier elements.
8. Store count in answer[i].

Why it works

The algorithm relies on the invariant that the stack always maintains a decreasing sequence of heights from top to bottom. This ensures that when processing a new element, all shorter elements are immediately visible and removable, and the first remaining taller element is the next blocking boundary. Each element is pushed and popped at most once, preserving correctness and efficiency.

Python Solution

from typing import List

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

        for i in range(n - 1, -1, -1):
            count = 0

            while stack and heights[i] > heights[stack[-1]]:
                stack.pop()
                count += 1

            if stack:
                count += 1

            stack.append(i)
            answer[i] = count

        return answer

Code Explanation

The solution iterates from right to left, ensuring that when processing index i, all relevant candidates to the right are already in the stack. The stack stores indices in decreasing height order. The while loop removes all shorter people, each of whom is visible to i. After that, if any taller person remains, they are counted once because they are the first blocking but visible person. Finally, i is pushed for future iterations, and its computed visibility count is stored.

Go Solution

func canSeePersonsCount(heights []int) []int {
	n := len(heights)
	stack := make([]int, 0, n)
	answer := make([]int, n)

	for i := n - 1; i >= 0; i-- {
		count := 0

		for len(stack) > 0 && heights[i] > heights[stack[len(stack)-1]] {
			stack = stack[:len(stack)-1]
			count++
		}

		if len(stack) > 0 {
			count++
		}

		stack = append(stack, i)
		answer[i] = count
	}

	return answer
}

Go-Specific Notes

The Go implementation mirrors the Python logic closely. The main difference is explicit slice manipulation to simulate stack behavior. The stack is a slice of indices, and popping is done by reslicing. Since Go integers are safe for this range, no overflow concerns exist. The logic remains identical in structure and guarantees O(n) performance.

Worked Examples

Example 1: [10,6,8,5,11,9]

We process from right to left.

i	height	stack (indices)	pops	visible count	answer
5	9	[]	none	0	[,,,,_,0]
4	11	[5]	none	1 (sees 9)	[,,,,1,0]
3	5	[4]	none	1 (sees 11)	[,,_,1,1,0]
2	8	[4,3] → pop 3	1 pop + 1 taller	2	[,,2,1,1,0]
1	6	[4,2] → pop 2,3? (via logic)	1 + 1	1	[_,1,2,1,1,0]
0	10	[4,2,1] → pop 1,2	2 pops + 1 taller	3	[3,1,2,1,1,0]

This shows how smaller elements are progressively removed and taller boundaries contribute exactly one visibility each time.

Example 2: [5,1,2,3,10]

i	height	stack	pops	visible	answer
4	10	[]	0	0	[,,,,0]
3	3	[4]	0	1	[,,_,1,0]
2	2	[4,3]	1	1	[,,1,1,0]
1	1	[4,3,2]	2	1	[_,1,1,1,0]
0	5	[4]	3 pops (1,2,3)	4	[4,1,1,1,0]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each index is pushed once and popped at most once
Space	O(n)	Stack stores indices in worst case

The linear time complexity comes from the amortized behavior of the monotonic stack. Even though there is a nested loop, each element enters and leaves the stack only once, ensuring total operations remain linear.

Test Cases

assert Solution().canSeePersonsCount([10,6,8,5,11,9]) == [3,1,2,1,1,0]  # example 1
assert Solution().canSeePersonsCount([5,1,2,3,10]) == [4,1,1,1,0]       # example 2
assert Solution().canSeePersonsCount([1]) == [0]                        # single element
assert Solution().canSeePersonsCount([5,4,3,2,1]) == [4,3,2,1,0]       # strictly decreasing
assert Solution().canSeePersonsCount([1,2,3,4,5]) == [1,1,1,1,0]       # strictly increasing
assert Solution().canSeePersonsCount([3,1,4,2,5]) == [2,1,1,1,0]       # mixed pattern

Test	Why
single element	verifies base case handling
decreasing sequence	tests maximum visibility chaining
increasing sequence	ensures only first taller is counted
mixed pattern	validates stack popping logic

Edge Cases

One important edge case is a single-element input. Since no elements exist to the right, the output must always be [0]. The algorithm handles this naturally because the loop processes the last element with an empty stack.

Another edge case is strictly decreasing heights. In this scenario, each person can see all people to their right. The stack will continuously pop every element, and no blocking taller element will exist, resulting in maximal visibility counts.

A strictly increasing sequence is also critical. Each person can only see the next person because all subsequent people are blocked by the first taller one. The stack never pops many elements in this case, ensuring only one visible person per index except the last.

Finally, large inputs up to 10^5 require the algorithm to avoid quadratic behavior. The monotonic stack guarantees each element is processed once, preventing timeouts and ensuring scalability.