⚡Flashcard Drill➔
NeetCode #701LC-1964Hard1-D Dynamic Programming
← Back to All Problems

#701 · #1964 · Find the Longest Valid Obstacle Course at Each Position(找出到每个位置为止最长的有效障碍赛跑路线)

📌 Problem Statement & Constraints

For each index i in obstacles, find the length of the longest non-decreasing subsequence that ends at i, and return the array of those lengths. Constraints: 1 <= obstacles.length <= 10^5, 1 <= obstacles[i] <= 10^7.

💡 Core Algorithmic Approaches

  1. This is the LIS-length-per-index problem, but the order is non-decreasing rather than strictly increasing.
  2. Maintain tails, where tails[k] is the smallest possible tail of a non-decreasing subsequence of length k + 1.
  3. For each element, bisect_right finds the first index with tails[pos] > x; overwrite it and record pos + 1.
  4. Using bisect_right rather than bisect_left permits equal values and therefore non-decreasing subsequences.

💻 Benchmark Python3 Implementation

class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        from bisect import bisect_right
        tails = []
        res = []
        for x in obstacles:
            pos = bisect_right(tails, x)   # first index with tails[pos] > x
            if pos == len(tails):
                tails.append(x)
            else:
                tails[pos] = x
            res.append(pos + 1)            # best length ending here
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): one binary search per element.
💾 Space Complexity
O(n): the tails array.

⚠️ Interview Pitfalls & Follow-ups

  • Using bisect_left: that enforces strictly increasing subsequences; equal values are allowed here, so bisect_right is correct.
  • Recording pos instead of pos + 1: pos is a 0-based index into tails, so the length is pos + 1.
  • Skipping the overwrite when the tail is shorter: patience sorting always writes the smaller tail at pos.
  • Attempting an O(n^2) DP: too slow for n = 10^5.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems