Watch 10 video solutions for Find the Longest Valid Obstacle Course at Each Position, a hard level problem involving Array, Binary Search, Binary Indexed Tree. This walkthrough by NeetCodeIO has 9,083 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
0 and i inclusive.ith obstacle in the course.obstacles.Return an array ans of length n, where ans[i] is the length of the longest obstacle course for index i as described above.
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.length1 <= n <= 1051 <= obstacles[i] <= 107Problem Overview: You receive an array obstacles. For every index i, compute the length of the longest non‑decreasing obstacle course that ends at position i. Each course must respect the original order, and every next obstacle must be greater than or equal to the previous one.
Approach 1: Dynamic Programming with Binary Search (O(n log n) time, O(n) space)
This problem is a variation of the Longest Increasing Subsequence (LIS), except the sequence is non‑decreasing rather than strictly increasing. Maintain a tails array where tails[k] stores the minimum ending value of a non‑decreasing subsequence of length k+1. Iterate through the array and use binary search to find the rightmost position where the current obstacle can extend the sequence (upper bound because duplicates are allowed). The index returned by binary search determines the length of the course ending at that position. Update tails accordingly. This method relies on efficient binary search operations and works well for large inputs.
The technique is common in problems related to binary search and sequence optimization on arrays. Instead of storing full subsequences, it stores only minimal ending values, which keeps the algorithm efficient while still producing the correct length for each prefix.
Approach 2: Fenwick Tree (Binary Indexed Tree) with Coordinate Compression (O(n log n) time, O(n) space)
This method treats the task as a dynamic programming query problem. For each obstacle value, you want the maximum subsequence length among all previous values <= obstacles[i]. A Fenwick Tree supports fast prefix maximum queries and updates. Because obstacle values can be large, first compress them into ranks. For each element, query the Fenwick Tree to get the best sequence length so far, add 1 for the current obstacle, then update the tree with the new length.
The Fenwick Tree efficiently maintains prefix maximums in O(log n) per operation. This approach is useful when the problem generalizes into range queries or when practicing data structures like Fenwick Tree. While slightly more complex to implement, it provides a clear DP formulation with structured updates.
Recommended for interviews: The dynamic programming + binary search solution is usually expected. It demonstrates understanding of the LIS pattern and how to adapt binary search for non‑decreasing sequences. Mentioning the Fenwick Tree approach shows deeper data structure knowledge and is useful when interviewers push toward range query optimizations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Binary Search | O(n log n) | O(n) | Best general solution. Efficient and commonly expected in interviews for LIS-style problems. |
| Fenwick Tree (Binary Indexed Tree) | O(n log n) | O(n) | Useful when modeling the problem as prefix maximum queries or practicing range query data structures. |