#### Discover more from DMITRII’s Substack

# 7.05.2023

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

```
fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
// 2 3 1 3
// 2 2
// 3 2 3
// 1 1 3 (pos = 1)
// 3 1 3 3
// 5 2 5 4 1 1 1 5 3 1
// 5 . 5
// 2 . 2
// 5 . 2 5
// 4 . 2 4
// 1 1 4 (pos = 1)
// 1 1 1
// 1 1 1 1
// 5 1 1 1 5
// 3 1 1 1 3
// 1 1 1 1 1
val lis = IntArray(obstacles.size)
var end = 0
return obstacles.map { x ->
var pos = -1
var lo = 0
var hi = end - 1
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
if (lis[mid] > x) {
hi = mid - 1
pos = mid
} else lo = mid + 1
}
if (pos == -1) {
lis[end++] = x
end
} else {
lis[pos] = x
pos + 1
}
}.toIntArray()
}
```

#### Join me on Telegram

https://t.me/leetcode_daily_unstoppable/205

#### Intuition

This is the Longest Increasing Subsequence length problem, that have a classic algorithm, which must be learned and understood.

The trivial case of `any increasing subsequence`

is broken by example: `2 3 1 3`

, when we consider the last `3`

result must be: `233`

instead of `13`

. So, we must track all the sequences.

To track all the sequences, we can use `TreeMap`

that will hold the `largest`

element and length of any subsequence. Adding a new element will take O(n^2).

The optimal `LIS`

solution is to keep the largest increasing subsequence so far and cleverly add new elements:

for a new element, search for the

`smallest`

element that is`larger`

than itif found, replace

if not, append

#### Approach

google what is the solution of

`LIS`

use an array for

`lis`

carefully write binary search

#### Complexity

Time complexity:

O(nlog(n))Space complexity:

O(n)