Leetcode Problem 1964. Find the Longest Valid Obstacle Course at Each Position

1964. Find the Longest Valid Obstacle Course at Each Position

Leetcode Solutions

Key approach of the solution.

  1. Initialize an empty array lis and an array answer of the same length as obstacles.
  2. Iterate over obstacles. For each obstacle obstacles[i]: a. Perform a binary search on lis to find the rightmost position where obstacles[i] can be inserted (let's call this position idx). b. If idx is equal to the length of lis, append obstacles[i] to lis. c. Otherwise, update lis[idx] with obstacles[i]. d. Update answer[i] with idx + 1.
  3. Return the answer array after the iteration is complete.
UML Thumbnail

Alternative approach using Dynamic Programming.

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...