Number of Visible People in a Queue

Hard Monotonic Stack Monotonic Stack Original on LeetCode

Number of Visible People in a Queue is a hard monotonic stack problem solved with the monotonic stack pattern. The best approach, optimal (monotonic stack from the right), runs in O(n) time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan to the right) up.

Problem

People stand in a queue numbered 0 to n - 1 from left to right, and heights[i] is the height of person i. All heights are different.

Person i can see person j (with i < j) when everyone standing strictly between them is shorter than both of them, that is min(heights[i], heights[j]) > max(heights[i + 1], …, heights[j - 1]).

Return an array answer where answer[i] is the number of people to the right that person i can see.

Examples

Example 1

Input
heights = [8, 3, 5, 1, 9, 2]
Output
[3, 1, 2, 1, 1, 0]
Why
Person 0 (height 8) sees 3, 5 and 9; the 1 behind 5 is hidden by 5, and nobody past 9 is visible. Person 2 (height 5) sees 1 and 9.

Example 2

Input
heights = [2, 4, 6, 8]
Output
[1, 1, 1, 0]
Why
Each person sees only the next one, who is taller and blocks everyone behind.

Example 3

Input
heights = [7, 6, 4, 2]
Output
[1, 1, 1, 0]
Why
Each person sees the shorter next person, but that person is taller than everyone after, so nobody further is visible.

Constraints

  • 1 <= heights.length <= 10^5
  • 1 <= heights[i] <= 10^5
  • All heights are distinct.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (scan to the right)O(n²)O(1)
Optimal (monotonic stack from the right)O(n)O(n)

1Brute force (scan to the right)

TimeO(n²)A tall person at the front may scan the whole rest of the queue, and so may many others.
SpaceO(1)Only counters, besides the output.

For each person, walk to the right while tracking the tallest person passed so far. A person is visible if they are taller than everyone in between; stop as soon as someone at least as tall as the viewer appears, because that person blocks everything behind.

  1. For each i: tallest = 0.
  2. For j = i + 1 … n - 1: if heights[j] > tallest, i sees j (count++); tallest = max(tallest, heights[j]).
  3. If heights[j] > heights[i], stop scanning.
class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            int tallest = 0;
            for (int j = i + 1; j < n; j++) {
                if (heights[j] > tallest) ans[i]++;
                tallest = Math.max(tallest, heights[j]);
                if (heights[j] > heights[i]) break;
            }
        }
        return ans;
    }
}

2Optimal (monotonic stack from the right)

TimeO(n)Each person is pushed once and popped at most once.
SpaceO(n)The stack can hold everyone when heights decrease toward the back.

Walk from the back of the queue to the front, keeping a stack whose heights decrease from bottom to top: the people still visible from the left. For person i, every stack entry shorter than i is visible to i and will be hidden by i for everyone further left, so pop and count them. If the stack is still non-empty, its top is the first taller person, who is also visible. Then push i.

  1. For i = n - 1 down to 0: count = 0.
  2. While stack not empty and top < heights[i]: pop, count++.
  3. If stack not empty, count++ (the first taller person).
  4. ans[i] = count; push heights[i].
class Solution {
    public int[] canSeePersonsCount(int[] heights) {
        int n = heights.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            int count = 0;
            while (!stack.isEmpty() && stack.peek() < heights[i]) {
                stack.pop();
                count++;
            }
            if (!stack.isEmpty()) count++;
            ans[i] = count;
            stack.push(heights[i]);
        }
        return ans;
    }
}

Edge cases to test

  • A single person: they see nobody
  • Strictly increasing heights: everyone sees exactly one person
  • A very tall person at the front who sees a whole staircase of rising heights

Hints

Hint 1

Person i sees person j exactly when everyone strictly between them is shorter than both. Scanning right from i, which people can still be seen?

Hint 2

Process the queue from right to left and keep a stack of the people who are still potentially visible from the left.

Hint 3

Everyone on the stack shorter than heights[i] is seen by i and then hidden forever by i. One more person (the first taller one) is also seen if the stack is not empty.

FAQ

What is the best time complexity for Number of Visible People in a Queue?

Optimal (monotonic stack from the right) runs in O(n) time and O(n) extra space. Each person is pushed once and popped at most once.

Which pattern does Number of Visible People in a Queue use?

It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.

Is there a brute force solution for Number of Visible People in a Queue?

Yes. Brute force (scan to the right) takes O(n²) time and O(1) space. For each person, walk to the right while tracking the tallest person passed so far.

Which edge cases should I test for Number of Visible People in a Queue?

A single person: they see nobody; Strictly increasing heights: everyone sees exactly one person; A very tall person at the front who sees a whole staircase of rising heights.