Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2096. Find the Longest Valid Obstacle Course at Each Position

My accepted Python solution to LeetCode problem 2096, Find the Longest Valid Obstacle Course at Each Position, running in 138ms.

  • Difficulty: Hard
  • Python
  • Runtime 138ms
  • Memory 33.2MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 138ms, memory 33.2MB, accepted 2026-01-01.

python
class Solution:
    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
        n = len(obstacles)
        result = []
        tails = []
        
        for i in range(n):
            h = obstacles[i]
            # Find position to insert (rightmost position where tails[pos] <= h)
            pos = bisect_right(tails, h)
            
            if pos == len(tails):
                tails.append(h)
            else:
                tails[pos] = h
            
            result.append(pos + 1)
        
        return result

Source