# Find the Longest Valid Obstacle Course at Each Position
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-the-longest-valid-obstacle-course-at-each-position)
Canonical: https://scaleengineer.com/dsa/problems/find-the-longest-valid-obstacle-course-at-each-position
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array, Binary Indexed Tree
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley)
---
## Problem
You want to build some obstacle courses. You are given a **0-indexed** integer array `obstacles` of length `n`, where `obstacles[i]` describes the height of the `ith` obstacle.

For every index `i` between `0` and `n - 1` (**inclusive**), find the length of the **longest obstacle course** in `obstacles` such that:

* You choose any number of obstacles between `0` and `i` **inclusive**.
* You must include the `ith` obstacle in the course.
* You must put the chosen obstacles in the **same order** as they appear in `obstacles`.
* Every obstacle (except the first) is **taller** than or the **same height** as the obstacle immediately before it.

Return _an array_ `ans` _of length_ `n`, _where_ `ans[i]` _is the length of the **longest obstacle course** for index_ `i` _as described above_.

**Example 1:**

**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.

**Example 2:**

**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.

**Example 3:**

**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 <= 105`
* `1 <= obstacles[i] <= 107`

# Approaches
## Brute-Force Dynamic Programming
This approach uses a straightforward dynamic programming technique. We define `ans[i]` as the length of the longest valid obstacle course that includes the `i-th` obstacle. To compute `ans[i]`, we look at all previous obstacles `obstacles[j]` where `j < i`. If `obstacles[j]` is less than or equal to `obstacles[i]`, it means `obstacles[i]` can be placed after `obstacles[j]` in a valid course. We find the maximum length among all such valid preceding courses (`ans[j]`) and add 1 to it (for `obstacles[i]` itself) to determine `ans[i]`. If no such `j` exists, the course consists of only `obstacles[i]`, so its length is 1.
**Time:** O(n^2) - There are two nested loops. The outer loop runs `n` times, and for each iteration, the inner loop can run up to `n` times. This leads to a quadratic time complexity. · **Space:** O(n) - We use an array `ans` of size `n` to store the results. If the output array is not considered, the space complexity is O(1).
**Pros:** The logic is simple and directly follows the problem's definition.; It's easy to implement and debug.
**Cons:** The quadratic time complexity O(n^2) is inefficient for large inputs, as specified by the problem constraints (n <= 10^5). This will result in a 'Time Limit Exceeded' (TLE) error on most online judges.
### Explanation
The algorithm iterates through each obstacle and, for each one, scans all the preceding obstacles to find the best one to extend. This results in a nested loop structure.

```java
class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.length;
        // ans[i] will store the length of the longest valid obstacle course ending at index i.
        int[] ans = new int[n];

        for (int i = 0; i < n; i++) {
            int maxLength = 0;
            // Find the longest course among previous obstacles that we can extend.
            for (int j = 0; j < i; j++) {
                if (obstacles[j] <= obstacles[i]) {
                    maxLength = Math.max(maxLength, ans[j]);
                }
            }
            // The length of the course ending at i is 1 (for obstacles[i]) + maxLength.
            ans[i] = maxLength + 1;
        }
        return ans;
    }
}
```
### Algorithm
*   Initialize an integer array `ans` of size `n` (the length of `obstacles`). This array will store the result.
*   Iterate through the `obstacles` array with an index `i` from `0` to `n-1`.
*   For each `i`, we need to find the length of the longest valid course ending with `obstacles[i]`.
*   Initialize a variable `maxLength` to `0`. This will keep track of the length of the longest valid course among the previous obstacles that `obstacles[i]` can extend.
*   Start an inner loop with an index `j` from `0` to `i-1`.
*   Inside the inner loop, check if `obstacles[j] <= obstacles[i]`. This condition must be met to extend the course ending at `j`.
*   If the condition is true, update `maxLength` with the maximum of its current value and `ans[j]` (the length of the course ending at `j`).
*   After the inner loop completes, the length of the longest course ending at `i` is `1 + maxLength` (1 for the current obstacle). Store this value in `ans[i]`. 
*   After the outer loop finishes, return the `ans` array.

## Dynamic Programming with Binary Search
This approach significantly optimizes the O(n^2) dynamic programming solution by using binary search. The key bottleneck in the brute-force method is finding the maximum length of a valid preceding course. Instead of a linear scan, we can find this information in logarithmic time.

We maintain an auxiliary list, `lis`, which is conceptually related to Patience Sorting. This list stores the smallest possible ending obstacle for a valid course of a given length. Because this list is always sorted, we can use binary search to find the correct position for the current obstacle. This determines the length of the longest valid course ending at the current position.
**Time:** O(n log n) - The main loop iterates `n` times. Inside the loop, the binary search operation on the `lis` list takes O(log k) time, where `k` is the current size of `lis`. Since `k` is at most `n`, the total time complexity is O(n log n). · **Space:** O(n) - We use the `ans` array for the output and the `lis` list, both of which can grow to a size of `n` in the worst case.
**Pros:** The O(n log n) time complexity is very efficient and passes the given constraints.; This is a standard and powerful technique for solving Longest Increasing Subsequence (LIS) and its variations.
**Cons:** The logic is more complex and less intuitive than the brute-force approach, particularly the purpose of the `lis` array and the binary search.
### Explanation
For each obstacle, we use binary search to find its place in the `lis` list. The index where it's placed (or would be placed) corresponds to the length of the valid course ending with that obstacle. This reduces the inner loop of the previous approach from O(n) to O(log n).

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int n = obstacles.length;
        int[] ans = new int[n];
        // 'lis' stores the smallest ending element of a non-decreasing subsequence of length i+1 at index i.
        List<Integer> lis = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int currentObstacle = obstacles[i];
            
            // Find the first element in 'lis' that is strictly greater than currentObstacle.
            int insertionPoint = upper_bound(lis, currentObstacle);
            
            if (insertionPoint == lis.size()) {
                // If currentObstacle is greater than all elements in lis, it extends the longest subsequence.
                lis.add(currentObstacle);
            } else {
                // Otherwise, it can be the new end of a subsequence of length insertionPoint+1.
                // This makes the subsequence ending potentially smaller, which is better for future extensions.
                lis.set(insertionPoint, currentObstacle);
            }
            
            // The length of the LIS ending at index i is insertionPoint + 1.
            ans[i] = insertionPoint + 1;
        }
        return ans;
    }

    // Custom binary search to find the index of the first element > key (upper_bound).
    private int upper_bound(List<Integer> list, int key) {
        int low = 0;
        int high = list.size();
        while (low < high) {
            int mid = low + (high - low) / 2;
            if (list.get(mid) <= key) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}
```
### Algorithm
*   Initialize an integer array `ans` of size `n` and an empty list `lis`.
*   The `lis` list will store the smallest ending element of a non-decreasing subsequence of a certain length. For example, `lis.get(k)` will be the smallest obstacle height that can end a valid course of length `k+1`. This list will always be sorted.
*   Iterate through the `obstacles` array from `i = 0` to `n-1`. Let the current obstacle be `obs`.
*   For each `obs`, perform a binary search on `lis` to find the index of the first element that is strictly greater than `obs`. This is equivalent to an `upper_bound` search. Let's call this index `j`.
*   If `j` equals the current size of `lis`, it means `obs` is greater than or equal to all elements in `lis`. We can therefore extend the longest known course. Append `obs` to `lis`.
*   If `j` is less than the size of `lis`, it means we have found a way to form a course of length `j+1` that ends with a smaller element (`obs`) than the previous one (`lis.get(j)`). We update the element at index `j` with `obs` (`lis.set(j, obs)`). This provides a better (smaller) ending for a course of this length, which might allow for more extensions later.
*   The length of the longest valid course ending at the current position `i` is `j + 1`. Store this value in `ans[i]`.
*   After iterating through all obstacles, return the `ans` array.

# Solutions
### Java

```java
class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] = Math . max ( c [ x ], v ); x += x & - x ; } } public int query ( int x ) { int s = 0 ; while ( x > 0 ) { s = Math . max ( s , c [ x ]); x -= x & - x ; } return s ; } } class Solution { public int [] longestObstacleCourseAtEachPosition ( int [] obstacles ) { int [] nums = obstacles . clone (); Arrays . sort ( nums ); int n = nums . length ; int [] ans = new int [ n ]; BinaryIndexedTree tree = new BinaryIndexedTree ( n ); for ( int k = 0 ; k < n ; ++ k ) { int x = obstacles [ k ]; int i = Arrays . binarySearch ( nums , x ) + 1 ; ans [ k ] = tree . query ( i ) + 1 ; tree . update ( i , ans [ k ]); } return ans ; } }
```

### CPP

```cpp
class BinaryIndexedTree { private: int n ; vector < int > c ; public: BinaryIndexedTree ( int n ) { this -> n = n ; c = vector < int > ( n + 1 ); } void update ( int x , int v ) { while ( x <= n ) { c [ x ] = max ( c [ x ], v ); x += x & - x ; } } int query ( int x ) { int s = 0 ; while ( x > 0 ) { s = max ( s , c [ x ]); x -= x & - x ; } return s ; } }; class Solution { public: vector < int > longestObstacleCourseAtEachPosition ( vector < int >& obstacles ) { vector < int > nums = obstacles ; sort ( nums . begin (), nums . end ()); int n = nums . size (); vector < int > ans ( n ); BinaryIndexedTree tree ( n ); for ( int k = 0 ; k < n ; ++ k ) { int x = obstacles [ k ]; auto it = lower_bound ( nums . begin (), nums . end (), x ); int i = distance ( nums . begin (), it ) + 1 ; ans [ k ] = tree . query ( i ) + 1 ; tree . update ( i , ans [ k ]); } return ans ; } };
```

### Python

```python
class BinaryIndexedTree : __slots__ = [ "n" , "c" ] def __init__ ( self , n : int ): self . n = n self . c = [ 0 ] * ( n + 1 ) def update ( self , x : int , v : int ): while x <= self . n : self . c [ x ] = max ( self . c [ x ], v ) x += x & - x def query ( self , x : int ) -> int : s = 0 while x : s = max ( s , self . c [ x ]) x -= x & - x return s class Solution : def longestObstacleCourseAtEachPosition ( self , obstacles : List [ int ]) -> List [ int ]: nums = sorted ( set ( obstacles )) n = len ( nums ) tree = BinaryIndexedTree ( n ) ans = [] for x in obstacles : i = bisect_left ( nums , x ) + 1 ans . append ( tree . query ( i ) + 1 ) tree . update ( i , ans [ - 1 ]) return ans
```