# 1964. Find the Longest Valid Obstacle Course at Each Position

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MhIkl8BJOOpfGoGo8ZU%2F-MhIl_8di5DPV1TV_e_n%2Fimage.png?alt=media\&token=71ef5950-e230-470c-adfb-cf98aa5bfbef)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MhIkl8BJOOpfGoGo8ZU%2F-MhIldh_M7PmFNVyBFUs%2Fimage.png?alt=media\&token=ecfaa123-e6ca-4dca-aa89-273fb401d556)

## greedy + binary search

same as leetcode 300 **LIS**, but this one has the **equal** condition, it's **Longest Non-decreasing Subsequence**

and returns the **Longest Non-decreasing Subsequence** array of each length condition.

time: O(nlogn)

space: O(n), use a tails array

```java
class Solution {
    public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
        int len = 0;
        int tails[] = new int[obstacles.length];
        int res[] = new int[obstacles.length];
        
        for (int i = 0; i < obstacles.length; i++) {
            int num = obstacles[i];
            
            if (len == 0 || num >= tails[len - 1]) { // add equal condition
                tails[len++] = num;
                res[i] = len;
            } else {
                int position = findPositionToReplace(tails, len, num);
                tails[position] = num;
                res[i] = position + 1;
            }
        }
        return res;
    }
    private int findPositionToReplace(int tails[], int res, int num) {
        int left = 0;
        int right = res;
        while (left < right) {
            int mid = left + (right - left)/2;
            if (tails[mid] <= num) { // add equal condition
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}
```
