Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Each person is looking to the right. For every position, the task is to count how many people are visible before the view is blocked.

The formal visibility rule can sound abstract, but the practical meaning is simple:

  • shorter people in front do not block the view
  • the first taller person is still visible
  • nobody behind that taller person is visible

Because the problem states that heights are distinct, the blocking behavior is very clean. For a person with height h, the visible people to the right are:

  1. every consecutive shorter person that can be “looked over”
  2. plus the first taller person, if one exists

That turns the problem into a skyline question: while moving across the array, how can the algorithm keep only the people who still matter as future blockers?

The key insight: keep a decreasing skyline to the right

The easiest optimal solution scans from right to left and maintains a monotonic decreasing stack of heights.

That stack represents the only people to the right who still matter for future visibility decisions:

  • if a shorter person is in front of a taller person, the shorter person may be visible to someone on the left, but once a new taller person arrives, that shorter person stops being a blocker
  • if a person is shorter than the current height, the current person can see them and then effectively looks past them
  • after all shorter people are removed, the next remaining person on the stack is the first taller blocker, and that person is also visible

So for each height:

  1. pop and count every shorter height from the top of the stack
  2. if the stack is still non-empty, count one more for the first taller person
  3. push the current height onto the stack

That is enough to compute the answer in linear time.

A concrete example

Take the classic input:

[10, 6, 8, 5, 11, 9]

The answer is:

[3, 1, 2, 1, 1, 0]

Why?

  • 10 sees 6, then 8, then 11
  • 6 sees only 8
  • 8 sees 5 and then 11
  • 5 sees only 11
  • 11 sees only 9
  • 9 sees nobody

Notice the pattern: each person sees a run of shorter people and then maybe one final taller blocker. That is exactly what the monotonic stack models.

How to derive this in an interview

A good interview derivation usually goes like this:

Start with the brute-force idea. For each person, walk right until the view is blocked. That is correct, but it can take O(n^2) time in a decreasing array, because many comparisons are repeated.

Then ask what repeated work is happening. The answer is that the algorithm keeps revisiting people who are obviously dominated by someone taller in front of them. Once a taller person exists closer to the left, some shorter people stop mattering as blockers.

That suggests compressing the right side into only the useful blockers. A monotonic decreasing stack does exactly that. It stores a compact skyline of people who are still relevant to anyone further left.

From there the visibility rule becomes mechanical:

  • pop shorter heights because the current person sees them
  • count the remaining top once because the current person also sees the first taller blocker
  • push the current height so it can act as a blocker for people further left

Once stated that way, the O(n) solution is much easier to justify.

Python solution

from typing import List


class VisiblePeopleCounter:
    """Count how many people each person can see to their right."""

    def count_visible_people(self, heights: List[int]) -> List[int]:
        visible_counts = [0] * len(heights)
        decreasing_stack: List[int] = []

        # Walk from right to left so the stack always describes the useful
        # skyline to the right of the current person.
        for index in range(len(heights) - 1, -1, -1):
            current_height = heights[index]
            visible_people = 0

            # Every shorter person on top of the stack is directly visible and
            # cannot block the current person's view beyond this point.
            while decreasing_stack and decreasing_stack[-1] < current_height:
                decreasing_stack.pop()
                visible_people += 1

            # If anyone remains, that person is the first taller blocker and is
            # still visible to the current person.
            if decreasing_stack:
                visible_people += 1

            visible_counts[index] = visible_people
            decreasing_stack.append(current_height)

        return visible_counts


class Solution:
    def canSeePersonsCount(self, heights: List[int]) -> List[int]:
        counter = VisiblePeopleCounter()
        return counter.count_visible_people(heights)

Why this works

The stack invariant is the entire proof.

At the moment the algorithm processes index i, the stack contains a decreasing sequence of heights from people to the right who are still relevant as visible candidates or blockers for someone further left.

When the algorithm pops a shorter height, that person is definitely visible to the current person because there is no taller-or-equal person between them left on the stack to block the view. Popping is also safe because a shorter person cannot block any future person who is at least as tall as the current one; the current person now dominates that shorter height as a nearer blocker.

After all shorter heights are removed, the next remaining stack top, if any, is the first taller person to the right that blocks further visibility. That person is still visible, so the algorithm adds exactly one more.

Each height is pushed once and popped once, so the total time is O(n), and the extra space is O(n) for the stack.

Interview follow-ups

What changes if the interviewer wants a left-to-right solution instead?

There is an equivalent O(n) monotonic-stack solution that scans from left to right. In that version, when a new height arrives, it pops shorter people from the stack and increments their answers because they can see the new person. If someone remains on the stack after the pops, that remaining taller person can also see the new arrival, so that person’s answer is incremented as well.

This version works for the same underlying reason: every person is involved in a push and pop at most once, so the total work stays linear. The tradeoff is that the bookkeeping is a little less intuitive for many people, because the answers are updated for earlier positions while scanning forward. The right-to-left version is usually easier to explain under interview pressure.

What if heights were not guaranteed to be distinct?

The same monotonic-stack pattern still works, but the equality case must be handled deliberately. If equal heights are allowed, an equal-height person usually acts like the first blocking person: they are visible, but anything beyond them is hidden. That means the comparison logic must reflect the exact problem statement for ties.

The key tradeoff is correctness versus convenience. With distinct heights, the comparison is simple because “shorter” and “taller” fully determine what happens. With duplicate heights, the algorithm is still linear, but the pop-versus-stop rule needs to match the tie semantics exactly or the counts will be off by one around equal runs.

What if the interviewer asks for the indices of visible people, not just the counts?

The current solution intentionally keeps only heights because counts are all the problem needs. If the interviewer wants the actual visible indices, the stack should store indices instead of raw heights, and the algorithm should append each popped index to a per-person result list. If a blocker remains after the pops, that index is also added.

That extension is still conceptually straightforward, but the output size now matters. In the worst case, the total number of visible pairs can be O(n^2), so no algorithm can output all pairs in better than quadratic output time. The counting version stays O(n) precisely because it summarizes visibility instead of materializing every visible relationship.

Practical takeaway

This problem looks geometric, but the optimal solution is really about state compression.

Instead of repeatedly scanning the whole suffix for each person, the algorithm keeps only a decreasing skyline of people who still matter. Every shorter person is seen and discarded, and the first taller person is seen and kept as the blocker. That one idea is enough to turn a brute-force visibility check into a clean O(n) monotonic-stack solution.