DMITRII’s Substack

Share this post

Leetcode daily # 12.05.2023

dmitriisamoilenko.substack.com

Discover more from DMITRII’s Substack

I post a problem that I solve every single day
Continue reading
Sign in

Leetcode daily # 12.05.2023

[2140. Solving Questions With Brainpower]

DMITRII SAMOILENKO
May 12, 2023
Share this post

Leetcode daily # 12.05.2023

dmitriisamoilenko.substack.com
Share

12.05.2023

2140. Solving Questions With Brainpower medium

fun mostPoints(questions: Array<IntArray>): Long {
    val dp = LongArray(questions.size)
    for (i in questions.lastIndex downTo 0) {
        val (points, skip) = questions[i]
        val tail = if (i + skip + 1 > questions.lastIndex) 0 else dp[i + skip + 1]
        val notTake = if (i + 1 > questions.lastIndex) 0 else dp[i + 1]
        dp[i] = maxOf(points + tail, notTake)
    }
    return dp[0]
}

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/210

Intuition

If we go from the tail, for each element we are interested only on what happens to the right from it. Prefix of the array is irrelevant, when we’re starting from the element i, because we sure know, that we are taking it and not skipping.
Given that, dynamic programming equation is:
dpi=max(pointsi+dpi+1+skipi,dpi+1), where dp is the mostPoints starting from position i.

Approach

Let’s implement a bottom-up solution.

Complexity

  • Time complexity:
    O(n)

  • Space complexity:
    O(n)

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

Share this post

Leetcode daily # 12.05.2023

dmitriisamoilenko.substack.com
Share
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