> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Find the Longest Valid Obstacle Course at

> Tested Python solution for LeetCode 1964 with 22 pytest cases. Generate a practice environment with lcpy.

LeetCode 1964, [Hard](/catalog/hard). Topics: [Array](/catalog/topics/array), [Binary Search](/catalog/topics/binary-search), [Binary Indexed Tree](/catalog/topics/binary-indexed-tree), Longest Increasing Subsequence. [View on LeetCode](https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position/description/).

Generate this problem as a practice environment: tested reference solution, 22 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 1964   # by problem number
lcpy gen -s find_the_longest_valid_obstacle_course_at_each_position   # by problem name
```

## Problem

You want to build some obstacle courses. You are given a \<strong>0-indexed\</strong> integer array \<code>obstacles\</code> of length \<code>n\</code>, where \<code>obstacles\[i]\</code> describes the height of the \<code>i\<sup>th\</sup>\</code> obstacle.

For every index \<code>i\</code> between \<code>0\</code> and \<code>n - 1\</code> (\<strong>inclusive\</strong>), find the length of the \<strong>longest obstacle course\</strong> in \<code>obstacles\</code> such that:

\<ul>
\<li>You choose any number of obstacles between \<code>0\</code> and \<code>i\</code> \<strong>inclusive\</strong>.\</li>
\<li>You must include the \<code>i\<sup>th\</sup>\</code> obstacle in the course.\</li>
\<li>You must put the chosen obstacles in the \<strong>same order\</strong> as they appear in \<code>obstacles\</code>.\</li>
\<li>Every obstacle (except the first) is \<strong>taller\</strong> than or the \<strong>same height\</strong> as the obstacle immediately before it.\</li>
\</ul>

Return \<em>an array\</em> \<code>ans\</code> \<em>of length\</em> \<code>n\</code>, \<em>where\</em> \<code>ans\[i]\</code> \<em>is the length of the \<strong>longest obstacle course\</strong> for index\</em> \<code>i\</code>\<em> as described above\</em>.

### Examples

```
Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [1], [1] has length 1.
- i = 1: [1,2], [1,2] has length 2.
- i = 2: [1,2,3], [1,2,3] has length 3.
- i = 3: [1,2,3,2], [1,2,2] has length 3.
```

```
Input: obstacles = [2,2,1]
Output: [1,2,1]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [2], [2] has length 1.
- i = 1: [2,2], [2,2] has length 2.
- i = 2: [2,2,1], [1] has length 1.
```

```
Input: obstacles = [3,1,5,6,4,2]
Output: [1,1,2,3,2,2]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [3], [3] has length 1.
- i = 1: [3,1], [1] has length 1.
- i = 2: [3,1,5], [3,5] has length 2. [1,5] is also valid.
- i = 3: [3,1,5,6], [3,5,6] has length 3. [1,5,6] is also valid.
- i = 4: [3,1,5,6,4], [3,4] has length 2. [1,4] is also valid.
- i = 5: [3,1,5,6,4,2], [1,2] has length 2.
```

### Constraints

* n == obstacles.length
* 1 \<= n \<= 10^5
* 1 \<= obstacles\[i] \<= 10^7

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_the_longest_valid_obstacle_course_at_each_position/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/find_the_longest_valid_obstacle_course_at_each_position/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import bisect


class Solution:
    # Time: O(n log n)
    # Space: O(n)
    def longest_obstacle_course(self, obstacles: list[int]) -> list[int]:
        tails: list[int] = []
        result: list[int] = []
        for height in obstacles:
            pos = bisect.bisect_right(tails, height)
            if pos == len(tails):
                tails.append(height)
            else:
                tails[pos] = height
            result.append(pos + 1)
        return result
```

## Complexity

| Time | Space |
| - | - |
| O(n log n) | O(n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.