Abstract / Summary

Given an obstacle array, for each position find the longest subsequence of obstacles that can be removed to make the sequence non-decreasing up to that point.

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 63% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Binary Indexed Tree
• Binary Search

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 position in an input array of obstacle heights, the length of the longest non-decreasing subsequence that ends at that position. It processes the obstacles sequentially, maintaining a compact representation of candidate subsequence tails and emitting the result for each element as it is examined.

Core Logic

The algorithm revolves around a single mutable list, last, which stores the smallest possible tail value for a subsequence of a given length. The invariant is that last is strictly increasing: the element at index k is the minimal last obstacle height among all non-decreasing subsequences of length k + 1 seen so far.

last = []   # smallest last element for sequences of length n
            # last[n+1] will always be >= than last[n]

For each obstacle o the code determines where o fits into the current last structure. The standard library routine bisect_right performs a binary search to locate the insertion point that preserves the non-decreasing order.

pos = bisect_right(last, o)

The position returned by bisect_right is zero-based and directly corresponds to the length of the longest subsequence that can be extended by o. Adding one yields the required one-based length, which is emitted immediately with a generator yield.

yield pos + 1      # one-based results

After emitting the result, the algorithm updates last. If the insertion point equals the current length of last, the obstacle extends the longest subsequence found so far, and the value is appended. Otherwise, the existing entry at pos is replaced with the smaller tail value o, preserving the invariant that each entry remains the minimal possible tail for its length.

if pos == len(last):
    last.append(o)          # an even longer sequence
else:
    last[pos] = o           # lower last element

Edge Cases Handled

When the input list is empty, the loop body never executes, and the generator produces no output, which correctly reflects the absence of any positions to evaluate.

If all obstacles have the same height, bisect_right always returns the index after the last equal element, causing each new obstacle to extend the subsequence by one. Consequently, the output sequence is a simple arithmetic progression starting at one.

For a strictly decreasing sequence of obstacles, each new value is inserted at position zero because it is smaller than any existing tail. The algorithm repeatedly replaces last[0] with the new smaller value, and the emitted length remains one for every position, accurately representing that no longer non-decreasing subsequence can be formed.

When obstacle heights are large integers or negative numbers, the binary search operates on the numeric values without assumptions about magnitude, so the algorithm remains correct regardless of the numeric range.

If the input contains duplicate values interleaved with larger values, bisect_right ensures that duplicates are placed after existing equal entries, thereby allowing the subsequence to grow when appropriate while still maintaining the minimal tail property.

Performance Optimizations

The use of bisect_right provides logarithmic search time within the last list, which remains at most as long as the longest subsequence discovered so far. By keeping only the minimal tail for each length, the algorithm avoids storing full subsequences, dramatically reducing memory usage compared to naïve dynamic programming approaches.

The generator pattern (yield) produces results on the fly, allowing the caller to consume the output incrementally without allocating an additional list to hold all lengths. This lazy evaluation can be advantageous when the consumer processes results sequentially or stops early.

Appending to last only when a longer subsequence is found prevents unnecessary growth of the internal structure. Updating an existing entry with a smaller tail value improves future binary searches because a smaller tail widens the range of obstacles that can extend the subsequence, leading to fewer replacements later on.

Overall, the combination of a monotonic auxiliary array, binary search, and lazy output yields an implementation that scales efficiently with input size while maintaining a small memory footprint.

Imagine you have a long row of building blocks of different heights, and you want to stack them up to make the tallest obstacle course possible. As you walk down the line of blocks, you pick them up one by one and try to build a tower.

Think of the list called last as a special shelf where you save the very best blocks you have found so far to help you build your tower. You look at a block and check your shelf to see where it fits best. If the block is taller than everything you have already saved, you add it to the end of the shelf because it makes your tower even taller. If the block is shorter or the same size as one you already saved, you swap out the old block on the shelf for this new one. Using a shorter block on your shelf is a clever trick because it makes it much easier to find another block that can be added to your tower later on.

For every single block you look at, you count how many blocks are in your tower at that moment and remember that number. By keeping the shelf organized, you always know the best way to keep your tower growing as you move along the path.

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

Time: loglinear
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++		Java			Python	TS
	WalkCCC	C++		Java			Python
	leetcode.ca	C++		Java		Go	Python	TS
	Progiez	C++		Java			Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	suxrobGM				C#
	varunu28			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
suxrobGM	C#
varunu28	Java
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