DMITRII’s Substack

Share this post

Leetcode daily # 7.05.2023

dmitriisamoilenko.substack.com

Leetcode daily # 7.05.2023

[1964. Find the Longest Valid Obstacle Course at Each Position]

DMITRII SAMOILENKO
May 7, 2023
Share
Share this post

Leetcode daily # 7.05.2023

dmitriisamoilenko.substack.com

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()
}

blog post

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

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:

  1. for a new element, search for the smallest element that is larger than it

  2. if found, replace

  3. if not, append

lis.gif

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)

Thanks for reading DMITRII’s Substack! Subscribe for free to receive new posts and support my work.

Share
Share this post

Leetcode daily # 7.05.2023

dmitriisamoilenko.substack.com
Previous
Next
Comments
Top
New

No posts

Ready for more?

© 2023 DMITRII SAMOILENKO
Privacy ∙ Terms ∙ Collection notice
Start WritingGet the app
Substack is the home for great writing