Find the Longest Valid Obstacle Course at Each Position

Hard

#1791Time: O(n^2) - There are two nested loops. The outer loop runs `n` times, and for each iteration, the inner loop can run up to `n` times. This leads to a quadratic time complexity.Space: O(n) - We use an array `ans` of size `n` to store the results. If the output array is not considered, the space complexity is O(1).1 company

Algorithms

Binary Search

Data structures

Array Binary Indexed Tree

Companies

Morgan Stanley

Prompt

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 i^th 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 i^th 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 <= 10⁵
1 <= obstacles[i] <= 10⁷

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a straightforward dynamic programming technique. We define ans[i] as the length of the longest valid obstacle course that includes the i-th obstacle. To compute ans[i], we look at all previous obstacles obstacles[j] where j < i. If obstacles[j] is less than or equal to obstacles[i], it means obstacles[i] can be placed after obstacles[j] in a valid course. We find the maximum length among all such valid preceding courses (ans[j]) and add 1 to it (for obstacles[i] itself) to determine ans[i]. If no such j exists, the course consists of only obstacles[i], so its length is 1.

Algorithm

Initialize an integer array ans of size n (the length of obstacles). This array will store the result.
Iterate through the obstacles array with an index i from 0 to n-1.
For each i, we need to find the length of the longest valid course ending with obstacles[i].
Initialize a variable maxLength to 0. This will keep track of the length of the longest valid course among the previous obstacles that obstacles[i] can extend.
Start an inner loop with an index j from 0 to i-1.
Inside the inner loop, check if obstacles[j] <= obstacles[i]. This condition must be met to extend the course ending at j.
If the condition is true, update maxLength with the maximum of its current value and ans[j] (the length of the course ending at j).
After the inner loop completes, the length of the longest course ending at i is 1 + maxLength (1 for the current obstacle). Store this value in ans[i].
After the outer loop finishes, return the ans array.

Walkthrough

The algorithm iterates through each obstacle and, for each one, scans all the preceding obstacles to find the best one to extend. This results in a nested loop structure.

1class Solution {2    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {3        int n = obstacles.length;4        // ans[i] will store the length of the longest valid obstacle course ending at index i.5        int[] ans = new int[n];6 7        for (int i = 0; i < n; i++) {8            int maxLength = 0;9            // Find the longest course among previous obstacles that we can extend.10            for (int j = 0; j < i; j++) {11                if (obstacles[j] <= obstacles[i]) {12                    maxLength = Math.max(maxLength, ans[j]);13                }14            }15            // The length of the course ending at i is 1 (for obstacles[i]) + maxLength.16            ans[i] = maxLength + 1;17        }18        return ans;19    }20}

Complexity

Time

O(n^2) - There are two nested loops. The outer loop runs `n` times, and for each iteration, the inner loop can run up to `n` times. This leads to a quadratic time complexity.

Space

O(n) - We use an array `ans` of size `n` to store the results. If the output array is not considered, the space complexity is O(1).

Trade-offs

Pros

The logic is simple and directly follows the problem's definition.
It's easy to implement and debug.

Cons

The quadratic time complexity O(n^2) is inefficient for large inputs, as specified by the problem constraints (n <= 10^5). This will result in a 'Time Limit Exceeded' (TLE) error on most online judges.

This approach significantly optimizes the O(n^2) dynamic programming solution by using binary search. The key bottleneck in the brute-force method is finding the maximum length of a valid preceding course. Instead of a linear scan, we can find this information in logarithmic time.

We maintain an auxiliary list, lis, which is conceptually related to Patience Sorting. This list stores the smallest possible ending obstacle for a valid course of a given length. Because this list is always sorted, we can use binary search to find the correct position for the current obstacle. This determines the length of the longest valid course ending at the current position.

Algorithm

Initialize an integer array ans of size n and an empty list lis.
The lis list will store the smallest ending element of a non-decreasing subsequence of a certain length. For example, lis.get(k) will be the smallest obstacle height that can end a valid course of length k+1. This list will always be sorted.
Iterate through the obstacles array from i = 0 to n-1. Let the current obstacle be obs.
For each obs, perform a binary search on lis to find the index of the first element that is strictly greater than obs. This is equivalent to an upper_bound search. Let's call this index j.
If j equals the current size of lis, it means obs is greater than or equal to all elements in lis. We can therefore extend the longest known course. Append obs to lis.
If j is less than the size of lis, it means we have found a way to form a course of length j+1 that ends with a smaller element (obs) than the previous one (lis.get(j)). We update the element at index j with obs (lis.set(j, obs)). This provides a better (smaller) ending for a course of this length, which might allow for more extensions later.
The length of the longest valid course ending at the current position i is j + 1. Store this value in ans[i].
After iterating through all obstacles, return the ans array.

Walkthrough

For each obstacle, we use binary search to find its place in the lis list. The index where it's placed (or would be placed) corresponds to the length of the valid course ending with that obstacle. This reduces the inner loop of the previous approach from O(n) to O(log n).

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {6        int n = obstacles.length;7        int[] ans = new int[n];8        // 'lis' stores the smallest ending element of a non-decreasing subsequence of length i+1 at index i.9        List<Integer> lis = new ArrayList<>();10 11        for (int i = 0; i < n; i++) {12            int currentObstacle = obstacles[i];13            14            // Find the first element in 'lis' that is strictly greater than currentObstacle.15            int insertionPoint = upper_bound(lis, currentObstacle);16            17            if (insertionPoint == lis.size()) {18                // If currentObstacle is greater than all elements in lis, it extends the longest subsequence.19                lis.add(currentObstacle);20            } else {21                // Otherwise, it can be the new end of a subsequence of length insertionPoint+1.22                // This makes the subsequence ending potentially smaller, which is better for future extensions.23                lis.set(insertionPoint, currentObstacle);24            }25            26            // The length of the LIS ending at index i is insertionPoint + 1.27            ans[i] = insertionPoint + 1;28        }29        return ans;30    }31 32    // Custom binary search to find the index of the first element > key (upper_bound).33    private int upper_bound(List<Integer> list, int key) {34        int low = 0;35        int high = list.size();36        while (low < high) {37            int mid = low + (high - low) / 2;38            if (list.get(mid) <= key) {39                low = mid + 1;40            } else {41                high = mid;42            }43        }44        return low;45    }46}

Complexity

Time

O(n log n) - The main loop iterates `n` times. Inside the loop, the binary search operation on the `lis` list takes O(log k) time, where `k` is the current size of `lis`. Since `k` is at most `n`, the total time complexity is O(n log n).

Space

O(n) - We use the `ans` array for the output and the `lis` list, both of which can grow to a size of `n` in the worst case.

Trade-offs

Pros

The O(n log n) time complexity is very efficient and passes the given constraints.
This is a standard and powerful technique for solving Longest Increasing Subsequence (LIS) and its variations.

Cons

The logic is more complex and less intuitive than the brute-force approach, particularly the purpose of the lis array and the binary search.

Solutions

Solution

1class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] = Math . max ( c [ x ], v ); x += x & - x ; } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s = Math . max ( s , c [ x ]); x -= x & - x ; } return s ; } } class Solution { public int [] longestObstacleCourseAtEachPosition ( int [] obstacles ) { int [] nums = obstacles . clone (); Arrays . sort ( nums ); int n = nums . length ; int [] ans = new int [ n ]; BinaryIndexedTree tree = new BinaryIndexedTree ( n ); for ( int k = 0 ; k < n ; ++ k ) { int x = obstacles [ k ]; int i = Arrays . binarySearch ( nums , x ) + 1 ; ans [ k ] = tree . query ( i ) + 1 ; tree . update ( i , ans [ k ]); } return ans ; } }

1class BinaryIndexedTree { private: int n ; vector < int > c ; public: BinaryIndexedTree ( int n ) { this -> n = n ; c = vector < int > ( n + 1 ); } void update ( int x , int v ) { while ( x <= n ) { c [ x ] = max ( c [ x ], v ); x += x & - x ; } } int query ( int x ) { int s = 0 ; while ( x > 0 ) { s = max ( s , c [ x ]); x -= x & - x ; } return s ; } }; class Solution { public: vector < int > longestObstacleCourseAtEachPosition ( vector < int >& obstacles ) { vector < int > nums = obstacles ; sort ( nums . begin (), nums . end ()); int n = nums . size (); vector < int > ans ( n ); BinaryIndexedTree tree ( n ); for ( int k = 0 ; k < n ; ++ k ) { int x = obstacles [ k ]; auto it = lower_bound ( nums . begin (), nums . end (), x ); int i = distance ( nums . begin (), it ) + 1 ; ans [ k ] = tree . query ( i ) + 1 ; tree . update ( i , ans [ k ]); } return ans ; } };

1class BinaryIndexedTree : __slots__ = [ "n" , "c" ] def __init__ ( self , n : int ): self . n = n self . c = [ 0 ] * ( n + 1 ) def update ( self , x : int , v : int ): while x <= self . n : self . c [ x ] = max ( self . c [ x ], v ) x += x & - x def query ( self , x : int ) -> int : s = 0 while x : s = max ( s , self . c [ x ]) x -= x & - x return s class Solution : def longestObstacleCourseAtEachPosition ( self , obstacles : List [ int ]) -> List [ int ]: nums = sorted ( set ( obstacles )) n = len ( nums ) tree = BinaryIndexedTree ( n ) ans = [] for x in obstacles : i = bisect_left ( nums , x ) + 1 ans . append ( tree . query ( i ) + 1 ) tree . update ( i , ans [ - 1 ]) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem