Find the Longest Valid Obstacle Course at Each Position

Problem

You want to build some obstacle courses. You are given a 0-indexed integer array obstacles of length n, where obstacles[i] describes the height of the ith obstacle.

For every index i between 0 and n - 1 (inclusive), find the length of the longest obstacle course in obstacles such that:

• You choose any number of obstacles between 0 and i inclusive.
• You must include the ith obstacle in the course.
• You must put the chosen obstacles in the same order as they appear in obstacles.
• Every obstacle (except the first) is taller than or the same height as the obstacle immediately before it.

Return an array ans of length n, where ans[i] is the length of thelongest obstacle course for index i as described above.

Examples

Example 1

Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [_1_], [1] has length 1.
- i = 1: [_1_ ,_2_], [1,2] has length 2.
- i = 2: [_1_ ,_2_ ,_3_], [1,2,3] has length 3.
- i = 3: [_1_ ,_2_ ,3,_2_], [1,2,2] has length 3.

Example 2

Input: obstacles = [2,2,1]
Output: [1,2,1]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [_2_], [2] has length 1.
- i = 1: [_2_ ,_2_], [2,2] has length 2.
- i = 2: [2,2,_1_], [1] has length 1.

Example 3

Input: obstacles = [3,1,5,6,4,2]
Output: [1,1,2,3,2,2]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [_3_], [3] has length 1.
- i = 1: [3,_1_], [1] has length 1.
- i = 2: [_3_ ,1,_5_], [3,5] has length 2. [1,5] is also valid.
- i = 3: [_3_ ,1,_5_ ,_6_], [3,5,6] has length 3. [1,5,6] is also valid.
- i = 4: [_3_ ,1,5,6,_4_], [3,4] has length 2. [1,4] is also valid.
- i = 5: [3,_1_ ,5,6,4,_2_], [1,2] has length 2.

Constraints

• n == obstacles.length
• 1 <= n <= 10^5
• 1 <= obstacles[i] <= 10^7

Solution

Method 1 – Patience Sorting (Binary Search)

Intuition

We want, for each position, the length of the longest non-decreasing subsequence ending at that position. This is similar to the Longest Increasing Subsequence (LIS) problem, but allows equal values. We can use a variant of patience sorting with binary search to efficiently compute the answer.

Approach

1. Initialize an empty list seq to keep track of the smallest possible ending values for subsequences of each length.
2. For each obstacle at index i:
   • Use binary search (bisect_right in Python) to find the rightmost position in seq where obstacles[i] can be placed (since equal values are allowed).
   • If the position is equal to the length of seq, append the obstacle; otherwise, replace the value at that position.
   • The answer for this position is the index + 1.
3. Return the answer array.

Code

C++

class Solution {
public:
    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obs) {
        int n = obs.size();
        vector<int> seq, ans(n);
        for(int i=0;i<n;++i) {
            int l=0, r=seq.size();
            while(l<r) {
                int m=(l+r)/2;
                if(seq[m]<=obs[i]) l=m+1;
                else r=m;
            }
            if(l==seq.size()) seq.push_back(obs[i]);
            else seq[l]=obs[i];
            ans[i]=l+1;
        }
        return ans;
    }
};

Go

func longestObstacleCourseAtEachPosition(obs []int) []int {
    n := len(obs)
    seq := []int{}
    ans := make([]int, n)
    for i, v := range obs {
        l, r := 0, len(seq)
        for l < r {
            m := (l + r) / 2
            if seq[m] <= v {
                l = m + 1
            } else {
                r = m
            }
        }
        if l == len(seq) {
            seq = append(seq, v)
        } else {
            seq[l] = v
        }
        ans[i] = l + 1
    }
    return ans
}

Java

class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obs) {
        int n = obs.length;
        ArrayList<Integer> seq = new ArrayList<>();
        int[] ans = new int[n];
        for(int i=0;i<n;++i) {
            int l=0, r=seq.size();
            while(l<r) {
                int m=(l+r)/2;
                if(seq.get(m)<=obs[i]) l=m+1;
                else r=m;
            }
            if(l==seq.size()) seq.add(obs[i]);
            else seq.set(l, obs[i]);
            ans[i]=l+1;
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun longestObstacleCourseAtEachPosition(obs: IntArray): IntArray {
        val n = obs.size
        val seq = mutableListOf<Int>()
        val ans = IntArray(n)
        for (i in 0 until n) {
            var l = 0; var r = seq.size
            while (l < r) {
                val m = (l + r) / 2
                if (seq[m] <= obs[i]) l = m + 1 else r = m
            }
            if (l == seq.size) seq.add(obs[i]) else seq[l] = obs[i]
            ans[i] = l + 1
        }
        return ans
    }
}

Python

class Solution:
    def longestObstacleCourseAtEachPosition(self, obs: list[int]) -> list[int]:
        from bisect import bisect_right
        seq = []
        ans = []
        for v in obs:
            i = bisect_right(seq, v)
            if i == len(seq):
                seq.append(v)
            else:
                seq[i] = v
            ans.append(i+1)
        return ans

Rust

impl Solution {
    pub fn longest_obstacle_course_at_each_position(obs: Vec<i32>) -> Vec<i32> {
        let n = obs.len();
        let mut seq = Vec::new();
        let mut ans = Vec::with_capacity(n);
        for &v in &obs {
            let i = seq.partition_point(|&x| x <= v);
            if i == seq.len() {
                seq.push(v);
            } else {
                seq[i] = v;
            }
            ans.push((i+1) as i32);
        }
        ans
    }
}

TypeScript

class Solution {
    longestObstacleCourseAtEachPosition(obs: number[]): number[] {
        const seq: number[] = [];
        const ans: number[] = [];
        for(const v of obs) {
            let l=0, r=seq.length;
            while(l<r) {
                const m = (l+r)>>1;
                if(seq[m]<=v) l=m+1; else r=m;
            }
            if(l===seq.length) seq.push(v); else seq[l]=v;
            ans.push(l+1);
        }
        return ans;
    }
}

Complexity

• ⏰ Time complexity: O(n log n), since each position uses binary search.
• 🧺 Space complexity: O(n), for the sequence and answer arrays.