Find the longest valid obstacle course at each position
May 6, 2023
binary-searchProblem URL: Find the longest valid obstacle course at each position
Given an array of integers, find the longest non-decreasing subsequence. This problem is very similar to Longest increasing subsequence. We will solve this with a greedy approach. The key is, the longest course for index i is determined by two factors:
- obstacles[i], which is required.
- the longest course before index i whose last obstacle is shorter than or equal to obstacles[i].
By combining the two terms above, we can determine the longest course for index i.
In short, the longest course ending at index i depends on the courses ending before index i.
class Solution:
def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
res = []
courses = []
for obstacle in obstacles:
if not courses or obstacle >= courses[-1]:
courses.append(obstacle)
res.append(len(courses))
else:
index = bisect.bisect_right(courses, obstacle)
courses[index] = obstacle
res.append(index + 1)
return res
Time complexity: O(nlogn)
Space complexity: O(n)