Abstract / Summary

Count how many people in a line can see someone in front of them based on their heights.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 70% (80k+ submissions).

Typical patterns to solve this problem:

• Array
• Monotonic Stack
• Stack

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes, for each person in a line, how many people to the left are visible according to the rule that a person can see another if every intermediate person is not taller than the one being observed. The algorithm augments the original height list with a sentinel value, then processes the array from left to right while maintaining a monotonic stack of indices representing a decreasing height sequence. Visibility counts are updated in-place, and the final result excludes the sentinel.

Key Steps and Corresponding Code

The algorithm begins by inserting a sentinel that is taller than any possible height. This guarantees that the stack is never empty during processing and eliminates the need for explicit boundary checks.

heights.insert(0, +inf)          # sentinel on the left

A list named taller is created to serve as a stack that holds indices of people whose heights form a strictly decreasing sequence when viewed from left to right. The stack is seeded with the index of the sentinel.

taller = [0]                     # stack starts with sentinel index

The size of the augmented list is stored, and a result list visible is allocated with the same length, initialized to zero. Pre-allocating the result array avoids repeated resizing during the loop.

size = len(heights)
visible = [0] * size

The main loop iterates over each original person, starting at index 1 to skip the sentinel. For each current height, the algorithm repeatedly pops indices from the stack while the height at the top of the stack is less than or equal to current. Each pop corresponds to a person who is shorter or equal in height to the current person; that popped person can now see the current one, so its visibility count is incremented.

for i in range(1, size):
    current = heights[i]
    while heights[taller[-1]] <= current:
        gnome = taller.pop()
        visible[gnome] += 1

After all shorter or equal neighbors have been removed, the person at the new top of the stack is taller than the current one. That taller neighbor can see the current person, so its visibility count is also incremented.

    visible[taller[-1]] += 1

Finally, the current index is pushed onto the stack, preserving the decreasing height invariant for subsequent iterations.

    taller.append(i)

When the loop finishes, the sentinel’s count is discarded, and the remaining entries constitute the answer.

return visible[1:]               # drop sentinel entry

Edge Cases Handled

When the input list is empty, the sentinel insertion creates a list of length 1. The loop body is never entered because the range starts at 1 and ends at 1, leaving visible as [0]. Slicing visible[1:] yields an empty list, which correctly represents that no persons are present.

If all heights are strictly decreasing, the while-condition never triggers, so each new person simply sees the immediate taller neighbor on the left. The stack grows to contain every index, and each visibility increment occurs only in the line that adds the current person’s contribution to the taller neighbor.

Conversely, when heights are strictly increasing, each new height causes the while-loop to pop all previously stored indices. Each popped index receives a visibility increment for seeing the new taller person, and the sentinel receives an increment for each pop as well. The stack collapses back to contain only the sentinel and the current index, ensuring correct visibility counts for a monotonic rise.

Equal heights are treated as “not taller,” so the while-condition <= removes indices with the same height as the current person. This matches the rule that a person of equal height does not block the view, allowing the earlier equal-height person to see the later one.

Performance Optimizations

The use of a monotonic stack eliminates the need for nested loops that would otherwise examine every pair of persons. Each index is pushed onto the stack exactly once and popped at most once, guaranteeing that the total number of stack operations is linear in the number of persons. This amortized linear behavior is a key optimization for large inputs.

Pre-allocating the visible list with the final required size avoids dynamic array growth during the loop, reducing allocation overhead. Updating visibility counts directly in the result array avoids auxiliary data structures.

Inserting the sentinel at the beginning of the list simplifies boundary handling, allowing the algorithm to reference taller[-1] without additional checks for an empty stack. This small constant-time adjustment contributes to a cleaner inner loop and avoids conditional branches that could degrade branch prediction.

Overall, the combination of a sentinel, a monotonic stack, and in-place result updates yields an implementation that processes the input in a single pass with minimal auxiliary memory and low constant factors.

Imagine a long row of people standing in a line, each with a different height. This piece of code helps figure out how many people each person can see standing to their right.

To start, a pretend giant is placed at the very beginning of the line. The giant is so tall that everyone can see it. A list is used to keep track of the people who are still waiting to see who is standing behind them. This list works like a stack of blocks where the newest one is always at the top.

The program walks down the line one person at a time and looks at whoever is currently at the top of the stack. If the person in line is taller than the person at the top of the stack, it means the shorter person can see the taller one. The shorter person is then removed from the stack because they have finished looking to their right. This happens over and over again until someone taller is found.

As the program moves along, it carefully counts every time a person can see someone else. Once everyone in the line has been checked, the list of counts for those real people is finished and ready to be used.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Python	Java					TS
	WalkCCC	C++			Python	Java
	leetcode.ca	C++			Python	Java	Go		C	Rust	TS
	Progiez	C++			Python	Java
github	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	fartem			Ruby
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	muhammadfarhankt						Go
	suxrobGM							C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
muhammadfarhankt	Go
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality