1944. Visible People

Number of Visible People in a Queue

A very fun hard problem. I'll admit the math formula initially caught me off balance.

What Does It Mean to See Someone at your Right?

According to definition: in a queue of $n$ people,

for indices $i$ and $j$ with $0 \leq i < j < n$,

person $i$ can see person $j$ only if everyone between them is shorter than both of them.

In math: $\min(heights[i], heights[j]) > \max_{i < k < j}(heights[k])$

What the Formula Reveals

For any $0 \leq i < j < n - 1$: if person $j + 1$ is not taller than person $j$,

person $i$ and person $j + 1$ will never satisfy that math formula above.

Person $i$ can't see person $j + 1$.

At this point, don't you feel monotonicity 😀?

Combined with a right-to-left traversal: when person $j + 1$ is processed,

person $j$ comes next, and person $i$ comes later.

Person $j + 1$ is immediately eliminated as a candidate that any left-side person could see.

Eliminating candidates in last-in-first-out order. A stack style.

The Mechanics

Pop Move 🍿

Each time person $j$ is processed, compare stack top with person $j$.

As long as the person at stack top is shorter than person $j$, pop this person off,

and increment person $j$'s rightward visibility count by one.

Under this pop logic, everyone between the popped person and person $j$ is shorter than both.

When to stop popping? Stop when the person at stack top is not shorter than person $j$.

Watch Out Details ㊙️

Once we reach the point where the person at stack top is not shorter than person $j$,

there's a subtle detail to handle carefully.

(1). First, the person at stack top can definitely be seen by person $j$, regardless of whether they're taller or the same height.

Math formula from the start supports this. Increment person $j$'s rightward visibility count by one.

(2). Here's the tricky part: if the person at stack top is taller than person $j$,

people to the left of person $j$ still have a chance to see this person at stack top,

since math formula can still be satisfied.

But if the person at stack top is the same height as person $j$,

no one to the left of person $j$ can see this person at stack top,

because math formula can no longer be satisfied.

So that equally tall stack top person must be popped immediately.

In short:

both cases we increment person $j$'s rightward visibility count by one,

but only when the person at stack top equals person $j$'s height do we also pop stack.

Don't mix them up. After handling these pops, push person $j$ onto stack.

C++

#include <stack>
#include <vector>
using namespace std;

vector<int> countVisibilities(vector<int>& heights) // LeetCode Q.1944.
{
    stack<int> stack; // A stack of heights.

    vector<int> visibilities(heights.size(), 0);

    for (int idx = heights.size() - 1; idx >= 0; idx--) {
        int height = heights[idx];

        while (!stack.empty() && stack.top() < height) {
            stack.pop();
            visibilities[idx]++;
        }

        if (!stack.empty()) {
            visibilities[idx]++;

            if (stack.top() == height)
                stack.pop();
        }

        stack.push(height);
    }

    return visibilities;
}

Python

def count_visibilities(heights: list[int]) -> list[int]:  # LeetCode Q.1944.
    stack = []
    visibilities = [0] * len(heights)

    for idx in range(len(heights) - 1, -1, -1):  # Backward iteration.
        height = heights[idx]
        
        while stack and stack[-1] < height:  # People on my left side can't see them.
            stack.pop(-1)
            visibilities[idx] += 1  # I can see unblocked shorter people.

        if stack:  # I can always see my next non-shorter person (if exists).
            visibilities[idx] += 1

            if stack[-1] == height:  # People on my left side can't see this person.
                stack.pop(-1)
        
        stack.append(height)

    return visibilities

Time complexity: $O(n)$ — each person is pushed once and popped at most once.

Space complexity: $O(n)$ — in the worst case, everyone is shorter than people to their right and stays in stack.