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 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.
Java
C++
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.
C++
Time Complexity: O(n log m), where m is the maximum obstacle height. Space Complexity: O(m).
| 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). |
Find the Longest Valid Obstacle Course at Each Position - Leetcode 1964 - Python • NeetCodeIO • 8,208 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 FleetCodePractice this problem
Open in Editor