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
- This is the LIS-length-per-index problem, but the order is non-decreasing rather than strictly increasing.
- Maintain
tails, wheretails[k]is the smallest possible tail of a non-decreasing subsequence of lengthk + 1. - For each element,
bisect_rightfinds the first index withtails[pos] > x; overwrite it and recordpos + 1. - Using
bisect_rightrather thanbisect_leftpermits 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, sobisect_rightis correct. - Recording
posinstead ofpos + 1:posis a 0-based index intotails, so the length ispos + 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.