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] <= 107In #1964 Find the Longest Valid Obstacle Course at Each Position, we must determine the length of the longest valid non-decreasing obstacle course ending at every index. This is closely related to the Longest Increasing Subsequence (LIS), but with a key modification: equal values are allowed because the sequence must be non-decreasing.
A common approach uses a patience sorting style technique with binary search. Maintain an array that stores the smallest possible ending value for subsequences of each length. For every obstacle, use upper_bound (first element greater than the current value) to find where it fits. The index of insertion determines the length of the valid course ending at that position.
Another advanced approach uses a Binary Indexed Tree (Fenwick Tree) with coordinate compression. For each obstacle height, query the maximum length achievable with heights ≤ the current value, then update the structure.
Both strategies efficiently process each element while maintaining partial results, avoiding the quadratic complexity of naive dynamic programming.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Binary Search (Patience Sorting / LIS Variant) | O(n log n) | O(n) |
| Binary Indexed Tree with Coordinate Compression | O(n log n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Can you keep track of the minimum height for each obstacle course length?
You can use binary search to find the longest previous obstacle course length that satisfies the conditions.
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.
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.
1import java.util.*;
2
3public class LongestObstacleCourse {
4 public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
5 int n = obstacles.length;
6 List<Integer> lis = new ArrayList<>();
7 int[] ans = new int[n];
8 for (int i = 0; i < n; i++) {
9 int obstacle = obstacles[i];
10 int pos = Collections.binarySearch(lis, obstacle);
11 if (pos < 0) pos = -(pos + 1);
12 ans[i] = pos + 1;
13 if (pos == lis.size()) {
14 lis.add(obstacle);
15 } else {
16 lis.set(pos, obstacle);
17 }
18 }
19 return ans;
20 }
21}
22The Java solution manages a list to keep track of the increasing sequence. Collections.binarySearch() helps to find the right position and modifies the current list as necessary.
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.
Time Complexity: O(n log m), where m is the maximum obstacle height. Space Complexity: O(m).
1class FenwickTree:
2 def __init__(self
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The sequence must be non-decreasing, meaning equal obstacle heights are allowed. Using upper_bound ensures that values equal to the current obstacle can extend the subsequence rather than replacing an existing position prematurely.
Problems based on Longest Increasing Subsequence variations are common in FAANG-style interviews. This question tests understanding of binary search optimization, sequence DP patterns, and advanced data structures like Fenwick Trees.
The optimal approach is a modified Longest Increasing Subsequence technique using binary search. By maintaining a structure that tracks the smallest possible tail for subsequences and using upper_bound for placement, we can compute the result for each index in O(n log n) time.
Yes, a Binary Indexed Tree combined with coordinate compression can track the maximum subsequence length for obstacle heights up to a given value. Each step queries the best previous length and updates the structure efficiently.
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.