Find the Longest Valid Obstacle Course at Each Position

You want to find the length of the longest obstacle course at each position in the given array. To do this, you can use a dynamic programming approach with binary search.

Here’s a step-by-step guide to the solution:

  1. Initialize a result array to keep track of the lengths and a tops array to store the smallest obstacle at each length.
  2. Iterate through the obstacles and try to find the right place for each one in the tops array.
  3. Use binary search to find the right position for the current obstacle in the tops array.
  4. Update the tops array with the current obstacle and save the length in the result array.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

from bisect import bisect_right

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        n = len(obstacles)
        result = [0] * n
        tops = [float('inf')] * n
        tops[0] = obstacles[0]
        result[0] = 1

        for i in range(1, n):
            obstacle = obstacles[i]

            # Use binary search to find the right place for the obstacle
            pos = bisect_right(tops, obstacle)

            # Update the tops array
            tops[pos] = obstacle

            # Save the length in the result array
            result[i] = pos + 1

        return result

This code returns an array representing the length of the longest obstacle course at each position. It handles the constraints well, with a time complexity of O(n * log n) and a space complexity of O(n).