Find the Longest Valid Obstacle Course at Each Position

How it works

This is a space-optimized version of the previous approach. Instead of preallocating an array of size n + 1, we start with an empty array and only grow it as needed. When a new element extends the longest sequence found so far, we append it; otherwise, we update an existing position. This uses only as much space as the length of the longest subsequence.

Steps

1. Initialize an empty dp array.
2. For each obstacle:
   • Use binary search to find the first index in dp where the value is greater than the current obstacle.
   • If the index equals the current length of dp, append the obstacle (new longest length).
   • Otherwise, update dp[index] with the current obstacle.
   • Store index + 1 as the result for this position.
3. Return the result array.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Using Lower Bound Instead of Upper Bound

This problem allows equal elements in the subsequence (non-strictly increasing), so we need upper_bound (first element greater than target), not lower_bound (first element greater than or equal to target). Using lower bound would treat equal elements as strictly increasing and produce incorrect results.

Confusing with Standard LIS

Standard Longest Increasing Subsequence requires strictly increasing elements and uses lower_bound. This problem requires non-decreasing elements (allowing duplicates), which changes the binary search condition. Applying the standard LIS algorithm directly will undercount valid sequences containing equal consecutive elements.

Forgetting to Update the DP Array

After finding the insertion position using binary search, the dp array must be updated with the current element. Forgetting this update means the algorithm does not track the optimal ending values for each sequence length, leading to incorrect results for subsequent elements.

Returning Indices Instead of Lengths

The binary search returns an index in the dp array, but the answer is the length of the longest valid course. The result for each position is index + 1 (since dp is 0-indexed and the index represents sequences of length index + 1). Returning index directly gives answers that are off by one.

Not Handling the First Element

The first obstacle always has a course length of 1 since there are no previous obstacles. Some implementations may incorrectly initialize or skip this case, especially when using recursive approaches that need careful base case handling.

from typing import List
from bisect import bisect
import bisect

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        res = []
        dp = []

        for num in obstacles:
            index = bisect.bisect_right(dp, num)
            res.append(index + 1)

            if index == len(dp):
                dp.append(num)
            else:
                dp[index] = num

        return res

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        int n = obstacles.size();
        vector<int> res(n);
        vector<int> dp;

        for (int i = 0; i < n; i++) {
            int index = upper_bound(dp.begin(), dp.end(), obstacles[i]) - dp.begin();
            res[i] = index + 1;

            if (index == dp.size()) {
                dp.push_back(obstacles[i]);
            } else {
                dp[index] = obstacles[i];
            }
        }

        return res;
    }
};