# 1964. Find the Longest Valid Obstacle Course at Each Position     • Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution { public: vector longestObstacleCourseAtEachPosition(vector& obstacles) { vector ans; // tail[i] := the minimum tail of all increasing subseqs having length i + 1 // it's easy to see that tail must be an increasing array vector tail; for (const int obstacle : obstacles) if (tail.empty() || obstacle >= tail.back()) { tail.push_back(obstacle); ans.push_back(tail.size()); } else { const int index = firstGreater(tail, obstacle); tail[index] = obstacle; ans.push_back(index + 1); } return ans; } private: // Find the first index l s.t A[l] > target // Returns A.size() if can't find int firstGreater(const vector& A, int target) { return upper_bound(begin(A), end(A), target) - begin(A); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { List ans = new ArrayList<>(); // tail[i] := the minimum tail of all increasing subseqs with length i + 1 // it's easy to see that tail must be an increasing array List tail = new ArrayList<>(); for (final int obstacle : obstacles) if (tail.isEmpty() || obstacle >= tail.get(tail.size() - 1)) { tail.add(obstacle); ans.add(tail.size()); } else { final int index = firstGreater(tail, obstacle); tail.set(index, obstacle); ans.add(index + 1); } return ans.stream().mapToInt(Integer::intValue).toArray(); } // Find the first index l s.t A.get(l) > target // Returns obstacles.length if can't find private int firstGreater(List A, int target) { int l = 0; int r = A.size(); while (l < r) { final int m = (l + r) / 2; if (A.get(m) > target) r = m; else l = m + 1; } return l; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]: ans = [] # tail[i] := the minimum tail of all increasing subseqs having length i + 1 # it's easy to see that tail must be an increasing array tail = [] for obstacle in obstacles: if not tail or obstacle >= tail[-1]: tail.append(obstacle) ans.append(len(tail)) else: index = bisect_right(tail, obstacle) tail[index] = obstacle ans.append(index + 1) return ans