Skip to main content
Talentd

Find the Longest Valid Obstacle Course at Each Position - Solution & Explanation

HardArrayBinary SearchBinary Indexed Tree13 min readAsked at: Morgan Stanley
Practice this problem

Problem Statement

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 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.length
  • 1 <= n <= 105
  • 1 <= obstacles[i] <= 107

Approach Overview

Problem 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 1: Dynamic Programming with Binary Search

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.

Code

PythonJavaC++

Python

Java

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Fenwick Tree (Binary Indexed Tree)

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n log m), where m is the maximum obstacle height. Space Complexity: O(m).

Try this approach in the editor →

Approach 3: Binary Indexed Tree (Fenwick Tree)

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Dynamic Programming with Binary SearchO(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.

Video Solution

Find the Longest Valid Obstacle Course at Each Position - Leetcode 1964 - Python • NeetCodeIO • 9,279 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the Longest Valid Obstacle Course at Each Position easy or hard?
The problem is labeled Hard on LeetCode because it requires recognizing a modified LIS pattern and adapting binary search to allow non-decreasing values. Implementing the Fenwick Tree alternative also requires coordinate compression and prefix maximum queries, which increases difficulty.
Find the Longest Valid Obstacle Course at Each Position Python/Java solution
Python, Java, and C++ solutions typically implement the LIS-style method with binary search. Maintain a list of minimal ending values and use bisect_right (Python) or upper_bound style logic to place each obstacle. The resulting index plus one gives the length of the valid obstacle course ending at that position.
How to solve Find the Longest Valid Obstacle Course at Each Position in O(n)?
A strict O(n) solution is not known for the general case. The best widely accepted solution uses an LIS-style dynamic programming approach with binary search, giving O(n log n) complexity. Fenwick Tree based implementations also run in O(n log n) because of the logarithmic update and query operations.
What is the best approach for Find the Longest Valid Obstacle Course at Each Position?
The most practical solution uses dynamic programming with binary search, similar to the Longest Increasing Subsequence technique. Maintain a tails array storing the smallest possible ending value for subsequences of each length. Using an upper-bound binary search allows duplicates, which fits the non-decreasing constraint. This approach runs in O(n log n) time with O(n) space.
Is Find the Longest Valid Obstacle Course at Each Position asked at Google/Amazon/Meta?
Problems based on Longest Increasing Subsequence patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require computing LIS length at each index or handling non-decreasing constraints test knowledge of binary search optimization and advanced data structures.
What data structure is used in Find the Longest Valid Obstacle Course at Each Position?
Common implementations use a dynamic programming array combined with binary search over a tails list. Another approach uses a Fenwick Tree (Binary Indexed Tree) with coordinate compression to maintain prefix maximum subsequence lengths efficiently.
What is the time complexity of Find the Longest Valid Obstacle Course at Each Position?
The optimal solutions run in O(n log n) time. Each element performs a binary search or Fenwick Tree query/update, both of which take O(log n). The algorithm processes all n elements once, leading to the final complexity of O(n log n) with O(n) additional space.

Ready to solve this problem?

Practice Find the Longest Valid Obstacle Course at Each Position with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Increasing Subsequence