Solution: Number of Visible People in a Queue

Explore how to use a monotonic decreasing stack to determine how many people each person can see in a queue. Understand the step-by-step algorithm that iterates from the end of the line, counting visible individuals based on height comparison and stack operations. This lesson helps you apply stacks effectively to solve visibility problems with linear time complexity.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

You are given an array heights representing n people standing in a queue, numbered from 0 to n - 1 from left to right. Each element heights[i] denotes the height of the person at position i. All heights are distinct.

A person at position i can see a person at position j (i < j) to their right if every person between them is shorter than both heights[i] and heights[j].

Formally, person i can see person j if:

$i < j$ and $m i n (h e i g h t s [i], h e i g h t s [j]) > m a x (h e i g h t s [i + 1], h e i g h t s [i + 2], . . ., h e i g h t s [j - 1])$ ...