1964. Find the Longest Valid Obstacle Course at Each Position - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming - Used to build optimal subsequences by tracking states
Longest Increasing Subsequence (LIS) - This problem is a variant of the classic LIS problem with non-strict inequality
Binary Search - Used to optimize the LIS approach from O(n^2) to O(n log n)
Upper Bound vs Lower Bound - Understanding when to use each for subsequence problems

1. Dynamic Programming (Top-Down)

Intuition

For each position, we want the longest increasing subsequence ending at that position where each element is less than or equal to the next. This is a variant of the classic LIS problem. We can use memoization: for each index and the previous element chosen, we either include the current element in our sequence (if valid) or skip it.

Algorithm

Create a 2D memoization table dp[i][prev] representing the longest valid sequence considering elements from 0 to i, where prev is the index of the last chosen element.
Define a recursive function dfs(i, prev):
- Base case: if i < 0, return 0.
- If already computed, return the cached value.
- Option 1: Skip the current element, recurse with dfs(i - 1, prev).
- Option 2: If valid (no previous element or current element is less than or equal to previous), include it and recurse with dfs(i - 1, i).
- Store and return the maximum.
Call dfs(n - 1, n) to fill the table, then construct the result array from the memoized values.

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        n = len(obstacles)
        dp = [[-1] * (n + 1) for _ in range(n)]

        def dfs(i, prev):
            if i < 0:
                return 0
            if dp[i][prev] != -1:
                return dp[i][prev]

            res = dfs(i - 1, prev)
            if prev == n or obstacles[prev] >= obstacles[i]:
                res = max(res, 1 + dfs(i - 1, i))
            dp[i][prev] = res
            return res

        dfs(n - 1, n)
        return [1] + [1 + dp[i - 1][i] for i in range(1, n)]

public class Solution {
    private int[][] dp;

    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.length;
        this.dp = new int[n][n + 1];
        for (int[] row : dp) {
            Arrays.fill(row, -1);
        }

        dfs(n - 1, n, obstacles);

        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            res[i] = 1 + dp[i - 1][i];
        }
        return res;
    }

    private int dfs(int i, int prev, int[] obstacles) {
        if (i < 0) {
            return 0;
        }
        if (dp[i][prev] != -1) {
            return dp[i][prev];
        }

        int res = dfs(i - 1, prev, obstacles);
        if (prev == obstacles.length || obstacles[prev] >= obstacles[i]) {
            res = Math.max(res, 1 + dfs(i - 1, i, obstacles));
        }
        return dp[i][prev] = res;
    }
}

class Solution {
public:
    vector<vector<int>> dp;

    vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
        int n = obstacles.size();
        this->dp = vector<vector<int>>(n, vector<int>(n + 1, -1));

        dfs(n - 1, n, obstacles);

        vector<int> res(n, 1);
        for (int i = 1; i < n; i++) {
            res[i] = 1 + dp[i - 1][i];
        }
        return res;
    }

private:
    int dfs(int i, int prev, vector<int>& obstacles) {
        if (i < 0) {
            return 0;
        }
        if (dp[i][prev] != -1) {
            return dp[i][prev];
        }

        int res = dfs(i - 1, prev, obstacles);
        if (prev == obstacles.size() || obstacles[prev] >= obstacles[i]) {
            res = max(res, 1 + dfs(i - 1, i, obstacles));
        }
        return dp[i][prev] = res;
    }
};

class Solution {
    /**
     * @param {number[]} obstacles
     * @return {number[]}
     */
    longestObstacleCourseAtEachPosition(obstacles) {
        const n = obstacles.length;
        const dp = Array.from({ length: n }, () => new Array(n + 1).fill(-1));

        const dfs = (i, prev) => {
            if (i < 0) {
                return 0;
            }
            if (dp[i][prev] !== -1) {
                return dp[i][prev];
            }

            let res = dfs(i - 1, prev);
            if (prev === n || obstacles[prev] >= obstacles[i]) {
                res = Math.max(res, 1 + dfs(i - 1, i));
            }
            dp[i][prev] = res;
            return res;
        };

        dfs(n - 1, n);

        const res = new Array(n).fill(1);
        for (let i = 1; i < n; i++) {
            res[i] = 1 + dp[i - 1][i];
        }
        return res;
    }
}

public class Solution {
    private int[][] dp;

    public int[] LongestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.Length;
        dp = new int[n][];
        for (int i = 0; i < n; i++) {
            dp[i] = new int[n + 1];
            Array.Fill(dp[i], -1);
        }

        Dfs(n - 1, n, obstacles);

        int[] res = new int[n];
        res[0] = 1;
        for (int i = 1; i < n; i++) {
            res[i] = 1 + dp[i - 1][i];
        }
        return res;
    }

    private int Dfs(int i, int prev, int[] obstacles) {
        if (i < 0) return 0;
        if (dp[i][prev] != -1) return dp[i][prev];

        int res = Dfs(i - 1, prev, obstacles);
        if (prev == obstacles.Length || obstacles[prev] >= obstacles[i]) {
            res = Math.Max(res, 1 + Dfs(i - 1, i, obstacles));
        }
        return dp[i][prev] = res;
    }
}

func longestObstacleCourseAtEachPosition(obstacles []int) []int {
    n := len(obstacles)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, n+1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    var dfs func(i, prev int) int
    dfs = func(i, prev int) int {
        if i < 0 {
            return 0
        }
        if dp[i][prev] != -1 {
            return dp[i][prev]
        }

        res := dfs(i-1, prev)
        if prev == n || obstacles[prev] >= obstacles[i] {
            res = max(res, 1+dfs(i-1, i))
        }
        dp[i][prev] = res
        return res
    }

    dfs(n-1, n)

    res := make([]int, n)
    res[0] = 1
    for i := 1; i < n; i++ {
        res[i] = 1 + dp[i-1][i]
    }
    return res
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

class Solution {
    private lateinit var dp: Array<IntArray>

    fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
        val n = obstacles.size
        dp = Array(n) { IntArray(n + 1) { -1 } }

        dfs(n - 1, n, obstacles)

        val res = IntArray(n) { 1 }
        for (i in 1 until n) {
            res[i] = 1 + dp[i - 1][i]
        }
        return res
    }

    private fun dfs(i: Int, prev: Int, obstacles: IntArray): Int {
        if (i < 0) return 0
        if (dp[i][prev] != -1) return dp[i][prev]

        var res = dfs(i - 1, prev, obstacles)
        if (prev == obstacles.size || obstacles[prev] >= obstacles[i]) {
            res = maxOf(res, 1 + dfs(i - 1, i, obstacles))
        }
        dp[i][prev] = res
        return res
    }
}

class Solution {
    private var dp: [[Int]] = []

    func longestObstacleCourseAtEachPosition(_ obstacles: [Int]) -> [Int] {
        let n = obstacles.count
        dp = Array(repeating: Array(repeating: -1, count: n + 1), count: n)

        dfs(n - 1, n, obstacles)

        var res = Array(repeating: 1, count: n)
        for i in 1..<n {
            res[i] = 1 + dp[i - 1][i]
        }
        return res
    }

    private func dfs(_ i: Int, _ prev: Int, _ obstacles: [Int]) -> Int {
        if i < 0 { return 0 }
        if dp[i][prev] != -1 { return dp[i][prev] }

        var res = dfs(i - 1, prev, obstacles)
        if prev == obstacles.count || obstacles[prev] >= obstacles[i] {
            res = max(res, 1 + dfs(i - 1, i, obstacles))
        }
        dp[i][prev] = res
        return res
    }
}

impl Solution {
    pub fn longest_obstacle_course_at_each_position(obstacles: Vec<i32>) -> Vec<i32> {
        let n = obstacles.len();
        let mut dp = vec![vec![-1i32; n + 1]; n];

        fn dfs(i: i32, prev: usize, obstacles: &[i32], dp: &mut Vec<Vec<i32>>) -> i32 {
            if i < 0 { return 0; }
            let ui = i as usize;
            if dp[ui][prev] != -1 { return dp[ui][prev]; }

            let mut res = dfs(i - 1, prev, obstacles, dp);
            if prev == obstacles.len() || obstacles[prev] >= obstacles[ui] {
                res = res.max(1 + dfs(i - 1, ui, obstacles, dp));
            }
            dp[ui][prev] = res;
            res
        }

        dfs(n as i32 - 1, n, &obstacles, &mut dp);

        let mut res = vec![1i32; n];
        for i in 1..n {
            res[i] = 1 + dp[i - 1][i];
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

2. Dynamic Programming (Binary Search) - I

Intuition

We can optimize the LIS approach using binary search. Maintain a dp array where dp[i] represents the smallest ending value of all increasing subsequences of length i + 1. For each new element, we find where it fits using binary search (finding the first element greater than it), which tells us the longest subsequence we can extend. We then update that position with the current value to keep subsequences as extensible as possible.

Algorithm

Initialize a dp array of size n + 1 filled with a large value (representing "no sequence of this length yet").
For each obstacle:
- Use binary search to find the first index in dp where the value is greater than the current obstacle.
- This index represents the longest valid course ending at this position.
- Update dp[index] with the current obstacle value.
- Store index + 1 as the result for this position.
Return the result array.

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        res = []
        dp = [10**8] * (len(obstacles) + 1)

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

        return res

public class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.length;
        int[] res = new int[n];
        int[] dp = new int[n + 1];
        Arrays.fill(dp, (int) 1e8);

        for (int i = 0; i < n; i++) {
            int index = upperBound(dp, obstacles[i]);
            res[i] = index + 1;
            dp[index] = obstacles[i];
        }

        return res;
    }

    private int upperBound(int[] dp, int target) {
        int left = 0, right = dp.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (dp[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

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

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

        return res;
    }
};

class Solution {
    /**
     * @param {number[]} obstacles
     * @return {number[]}
     */
    longestObstacleCourseAtEachPosition(obstacles) {
        let n = obstacles.length;
        let res = new Array(n).fill(0);
        let dp = new Array(n + 1).fill(1e8);

        const upperBound = (dp, target) => {
            let left = 0,
                right = dp.length;
            while (left < right) {
                let mid = Math.floor((left + right) / 2);
                if (dp[mid] > target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        };

        for (let i = 0; i < n; i++) {
            let index = upperBound(dp, obstacles[i]);
            res[i] = index + 1;
            dp[index] = obstacles[i];
        }

        return res;
    }
}

public class Solution {
    public int[] LongestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.Length;
        int[] res = new int[n];
        int[] dp = new int[n + 1];
        Array.Fill(dp, (int)1e8);

        for (int i = 0; i < n; i++) {
            int index = UpperBound(dp, obstacles[i]);
            res[i] = index + 1;
            dp[index] = obstacles[i];
        }

        return res;
    }

    private int UpperBound(int[] dp, int target) {
        int left = 0, right = dp.Length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (dp[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

import "sort"

func longestObstacleCourseAtEachPosition(obstacles []int) []int {
    n := len(obstacles)
    res := make([]int, n)
    dp := make([]int, n+1)
    for i := range dp {
        dp[i] = 1e8
    }

    for i := 0; i < n; i++ {
        index := sort.Search(len(dp), func(j int) bool {
            return dp[j] > obstacles[i]
        })
        res[i] = index + 1
        dp[index] = obstacles[i]
    }

    return res
}

class Solution {
    fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
        val n = obstacles.size
        val res = IntArray(n)
        val dp = IntArray(n + 1) { 1e8.toInt() }

        for (i in 0 until n) {
            val index = upperBound(dp, obstacles[i])
            res[i] = index + 1
            dp[index] = obstacles[i]
        }

        return res
    }

    private fun upperBound(dp: IntArray, target: Int): Int {
        var left = 0
        var right = dp.size
        while (left < right) {
            val mid = left + (right - left) / 2
            if (dp[mid] > target) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

class Solution {
    func longestObstacleCourseAtEachPosition(_ obstacles: [Int]) -> [Int] {
        let n = obstacles.count
        var res = [Int](repeating: 0, count: n)
        var dp = [Int](repeating: Int(1e8), count: n + 1)

        for i in 0..<n {
            let index = upperBound(dp, obstacles[i])
            res[i] = index + 1
            dp[index] = obstacles[i]
        }

        return res
    }

    private func upperBound(_ dp: [Int], _ target: Int) -> Int {
        var left = 0
        var right = dp.count
        while left < right {
            let mid = left + (right - left) / 2
            if dp[mid] > target {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

impl Solution {
    pub fn longest_obstacle_course_at_each_position(obstacles: Vec<i32>) -> Vec<i32> {
        let n = obstacles.len();
        let mut res = vec![0i32; n];
        let mut dp = vec![i32::MAX; n + 1];

        for i in 0..n {
            let index = dp.partition_point(|&x| x <= obstacles[i]);
            res[i] = index as i32 + 1;
            dp[index] = obstacles[i];
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

3. Dynamic Programming (Binary Search) - II

Intuition

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.

Algorithm

Initialize an empty dp array.
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.
Return the result array.

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

public class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.length;
        int[] res = new int[n];
        List<Integer> dp = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int index = upperBound(dp, obstacles[i]);
            res[i] = index + 1;

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

        return res;
    }

    private int upperBound(List<Integer> dp, int target) {
        int left = 0, right = dp.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (dp.get(mid) > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

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;
    }
};

class Solution {
    /**
     * @param {number[]} obstacles
     * @return {number[]}
     */
    longestObstacleCourseAtEachPosition(obstacles) {
        let n = obstacles.length;
        let res = new Array(n).fill(0);
        let dp = [];

        const upperBound = (dp, target) => {
            let left = 0,
                right = dp.length;
            while (left < right) {
                let mid = Math.floor((left + right) / 2);
                if (dp[mid] > target) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            return left;
        };

        for (let i = 0; i < n; i++) {
            let index = upperBound(dp, obstacles[i]);
            res[i] = index + 1;

            if (index === dp.length) {
                dp.push(obstacles[i]);
            } else {
                dp[index] = obstacles[i];
            }
        }

        return res;
    }
}

public class Solution {
    public int[] LongestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.Length;
        int[] res = new int[n];
        List<int> dp = new List<int>();

        for (int i = 0; i < n; i++) {
            int index = UpperBound(dp, obstacles[i]);
            res[i] = index + 1;

            if (index == dp.Count) {
                dp.Add(obstacles[i]);
            } else {
                dp[index] = obstacles[i];
            }
        }

        return res;
    }

    private int UpperBound(List<int> dp, int target) {
        int left = 0, right = dp.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (dp[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

import "sort"

func longestObstacleCourseAtEachPosition(obstacles []int) []int {
    n := len(obstacles)
    res := make([]int, n)
    dp := []int{}

    for i := 0; i < n; i++ {
        index := sort.Search(len(dp), func(j int) bool {
            return dp[j] > obstacles[i]
        })
        res[i] = index + 1

        if index == len(dp) {
            dp = append(dp, obstacles[i])
        } else {
            dp[index] = obstacles[i]
        }
    }

    return res
}

class Solution {
    fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
        val n = obstacles.size
        val res = IntArray(n)
        val dp = mutableListOf<Int>()

        for (i in 0 until n) {
            val index = upperBound(dp, obstacles[i])
            res[i] = index + 1

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

        return res
    }

    private fun upperBound(dp: List<Int>, target: Int): Int {
        var left = 0
        var right = dp.size
        while (left < right) {
            val mid = left + (right - left) / 2
            if (dp[mid] > target) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

class Solution {
    func longestObstacleCourseAtEachPosition(_ obstacles: [Int]) -> [Int] {
        let n = obstacles.count
        var res = [Int](repeating: 0, count: n)
        var dp = [Int]()

        for i in 0..<n {
            let index = upperBound(dp, obstacles[i])
            res[i] = index + 1

            if index == dp.count {
                dp.append(obstacles[i])
            } else {
                dp[index] = obstacles[i]
            }
        }

        return res
    }

    private func upperBound(_ dp: [Int], _ target: Int) -> Int {
        var left = 0
        var right = dp.count
        while left < right {
            let mid = left + (right - left) / 2
            if dp[mid] > target {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

impl Solution {
    pub fn longest_obstacle_course_at_each_position(obstacles: Vec<i32>) -> Vec<i32> {
        let n = obstacles.len();
        let mut res = vec![0i32; n];
        let mut dp: Vec<i32> = Vec::new();

        for i in 0..n {
            let index = dp.partition_point(|&x| x <= obstacles[i]);
            res[i] = index as i32 + 1;

            if index == dp.len() {
                dp.push(obstacles[i]);
            } else {
                dp[index] = obstacles[i];
            }
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

Common Pitfalls

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.