Find the Longest Valid Obstacle Course at Each Position

You are given an array of integers obstacles where obstacles[i] is the height of the i-th obstacle. For each position i, find the length of the longest obstacle course you can build using obstacles from index 0 to i, where the last obstacle in the course is obstacles[i] and the heights are non-decreasing.

This is LeetCode 1964: Find the Longest Valid Obstacle Course at Each Position. It asks you to compute, for every index, the longest non-decreasing subsequence ending at that index. That makes it a variant of the Longest Increasing Subsequence (LIS) problem, with two twists: you allow equal values (non-decreasing instead of strictly increasing), and you need the answer at every position, not just the global maximum.

Why this problem is harder than standard LIS

In the classic Longest Increasing Subsequence problem, you compute one number: the global LIS length. Here you need an answer for every index, which means you cannot just track the final tails length. You need to record the position where each element lands during patience sorting.

The other difference is the "non-decreasing" requirement. Standard LIS uses bisect_left to enforce strict increase (equal values replace rather than extend). For non-decreasing subsequences, you use bisect_right instead, which allows equal values to extend the sequence.

The approach: patience sorting with bisect_right

The algorithm maintains a tails array, just like the O(n log n) LIS algorithm. For each obstacle:

1. Binary search tails using bisect_right to find the first position where the value is strictly greater than the current obstacle.
2. If that position is at the end, append the obstacle to tails. The sequence grows.
3. Otherwise, replace tails[pos] with the current obstacle. This keeps tails optimized for future extensions.
4. Record pos + 1 as the answer for this index. That is the length of the longest non-decreasing subsequence ending here.

The key difference from standard LIS: using bisect_right instead of bisect_left. With bisect_right, when you encounter a value equal to an existing element in tails, the search returns the position after the equal elements. This means equal values extend the sequence rather than replacing existing entries of the same value. That is exactly what "non-decreasing" requires.

The code

from bisect import bisect_right

def longestObstacleCourseAtEachPosition(obstacles):
    tails = []
    answer = []

    for obs in obstacles:
        pos = bisect_right(tails, obs)
        if pos == len(tails):
            tails.append(obs)
        else:
            tails[pos] = obs
        answer.append(pos + 1)

    return answer

That is the entire solution. The structure is nearly identical to the O(n log n) LIS algorithm. The only changes are bisect_right instead of bisect_left, and recording pos + 1 into an answer array at each step instead of returning len(tails) at the end.

Step-by-step walkthrough

Let's trace through obstacles = [1, 2, 3, 2] and see how tails and answer evolve at each step.

Notice step 4 carefully. When obstacle 2 arrives, bisect_right(tails, 2) returns 2, not 1. That is because bisect_right returns the position after any existing equal values. Since tails[1] = 2, the insertion point is index 2. We replace tails[2] (which was 3) with 2. The answer is pos + 1 = 3, meaning there is a non-decreasing subsequence of length 3 ending with this 2. That subsequence is [1, 2, 2].

If we had used bisect_left instead, it would return position 1, giving an answer of 2. That would be wrong for the non-decreasing case because [1, 2, 2] is a valid course of length 3.

Complexity analysis

For each of the n obstacles, the binary search over tails takes O(log n). The tails array and the answer array each hold at most n elements. There is no way to solve this problem faster than O(n) because you must read every element at least once and output n values. The O(n log n) solution is optimal.

Building blocks

This problem snaps together two reusable building blocks.

The first is patience sorting for subsequence problems. The tails array with binary search is the same technique used in Longest Increasing Subsequence and Russian Doll Envelopes. Once you internalize how tails tracks the smallest possible ending value for each subsequence length, you can apply it to any LIS variant. The only thing that changes between variants is the binary search function (bisect_left for strict, bisect_right for non-decreasing) and whether you record per-element answers or just the final length.

The second is binary search as a decision tool. You are not searching for a target value. You are searching for the correct insertion position to maintain a sorted invariant. This same idea appears in Binary Search and in problems like Search Insert Position (LeetCode 35) and Kth Largest Element where binary search helps you make O(log n) decisions inside a larger algorithm.

Edge cases

• Single element: obstacles = [5]. The answer is always [1]. One obstacle by itself is a course of length 1.
• Already non-decreasing: obstacles = [1, 1, 2, 3, 3]. Every element extends tails. The answer is [1, 2, 3, 4, 5].
• Strictly decreasing: obstacles = [5, 4, 3, 2, 1]. Every element replaces tails[0]. The answer is [1, 1, 1, 1, 1].
• All equal values: obstacles = [3, 3, 3, 3]. With bisect_right, each 3 extends the sequence. The answer is [1, 2, 3, 4]. This is correct because [3, 3, 3, 3] is non-decreasing.
• Large input: n can be up to 100,000. The O(n^2) DP approach would time out. The O(n log n) patience sorting approach handles this comfortably.

From understanding to recall

You have just seen how a small tweak to the standard LIS algorithm, swapping bisect_left for bisect_right and recording per-position answers, solves a hard-rated LeetCode problem. The logic is clean once you see it. But "I understand it" and "I can write it from scratch in an interview" are very different things.

The tricky part is remembering which bisect function to use and why. If you mix up bisect_left and bisect_right, your solution handles duplicates incorrectly and fails on test cases with equal values. That is a subtle bug that is hard to catch under pressure.

Spaced repetition locks in both the algorithm and the reasoning behind the bisect_right choice. You drill the problem at increasing intervals, and each time you write the solution from memory, reinforcing the connection between "non-decreasing" and "bisect_right." After a few reps, the distinction becomes automatic.

Patience sorting for subsequence problems is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition beats random problem grinding every time.

Related posts

• Longest Increasing Subsequence - The foundational problem. Master this first, and the obstacle course variant becomes a one-line change.
• Russian Doll Envelopes - Another LIS variant that reduces a 2D nesting problem to patience sorting via a clever sort trick.
• Binary Search - Understanding bisect_left vs bisect_right is essential for getting this problem right.