Leetcode daily # 7.05.2023
[1964. Find the Longest Valid Obstacle Course at Each Position]
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
smallestelement that islargerthan itif found, replace
if not, append
Approach
google what is the solution of
LISuse an array for
liscarefully write binary search
Complexity
Time complexity:
O(nlog(n))Space complexity:
O(n)