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.
In this approach, we use a combination of dynamic programming and binary search to find the longest obstacle course at each position. We maintain a list which helps to track the longest increasing subsequence (LIS) up to the current index. For each obstacle, we find its position in the LIS using binary search (which keeps it sorted), updating the LIS while also determining the length of the LIS at each step.
The Python solution utilizes the bisect_right function from the built-in bisect module, which performs a binary search to help determine positions. The lis list maintains the lengths, and for each obstacle, the list is updated by replacing or extending as necessary.
Time Complexity: O(n log n), as each binary search operation runs in O(log n) and is performed n times. Space Complexity: O(n), storing the longest sequence lengths.
This approach uses a Fenwick Tree (or BIT) to keep track of the lengths of obstacle courses efficiently. As we iterate through the obstacles array, we update our Fenwick Tree with the longest course length ending at each obstacle using range queries.
This Python code defines a Fenwick Tree class to support efficient updates and queries. The main function iterates over the obstacles, with each step updating and querying the Fenwick Tree for the current obstacle height, ensuring optimal performance.
Time Complexity: O(n log m), where m is the maximum obstacle height. Space Complexity: O(m).
We can use a Binary Indexed Tree to maintain an array of the lengths of the longest increasing subsequences.
Then for each obstacle, we query in the Binary Indexed Tree for the length of the longest increasing subsequence that is less than or equal to the current obstacle, suppose it is l. Then the length of the longest increasing subsequence of the current obstacle is l+1. We add l+1 to the answer array, and update l+1 in the Binary Indexed Tree.
The time complexity is O(n times log n), and the space complexity is O(n). Where n is the number of obstacles.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming with Binary Search | Time Complexity: O(n log n), as each binary search operation runs in O(log n) and is performed n times. Space Complexity: O(n), storing the longest sequence lengths. |
| Fenwick Tree (Binary Indexed Tree) | Time Complexity: O(n log m), where m is the maximum obstacle height. Space Complexity: O(m). |
| Binary Indexed Tree (Fenwick Tree) | — |
| 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. |
Find the Longest Valid Obstacle Course at Each Position - Leetcode 1964 - Python • NeetCodeIO • 9,083 views views
Watch 9 more video solutions →Practice Find the Longest Valid Obstacle Course at Each Position with our built-in code editor and test cases.
Practice on FleetCode