How hard is LeetCode 2297. Jump Game VIII?

LeetCode 2297. Jump Game VIII is rated Medium on LeetCode.

What is the time complexity of LeetCode 2297. Jump Game VIII?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2297. Jump Game VIII?

The Python solution on this page uses O(n) auxiliary space.

Is LeetCode 2297. Jump Game VIII a premium problem?

Yes. LeetCode 2297. Jump Game VIII is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Jump Game VIII — LeetCode 2297 Python Solution

MediumLeetCode PremiumStackGraphArrayDynamic ProgrammingShortest PathMonotonic Stack

Problem: #2297
Pattern: Stack
Reading time: 5 min
Source: leetcode.com

The problem

You are given a 0-indexed integer array nums of length n. You are initially standing at index 0.

Example

Input: nums = [3,2,4,4,1], costs = [3,7,6,4,2]
Output: 8
Explanation: You start at index 0.

Python solution

Python

class Solution:
    def minCost(self, nums: List[int], costs: List[int]) -> int:
        n = len(nums)
        g = defaultdict(list)
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and nums[stk[-1]] < nums[i]:
                stk.pop()
            if stk:
                g[i].append(stk[-1])
            stk.append(i)

        stk = []
        for i in range(n - 1, -1, -1):
            while stk and nums[stk[-1]] >= nums[i]:
                stk.pop()
            if stk:
                g[i].append(stk[-1])
            stk.append(i)

        f = [inf] * n
        f[0] = 0
        for i in range(n):
            for j in g[i]:
                f[j] = min(f[j], f[i] + costs[j])
        return f[n - 1]

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2297. Jump Game VIII is filed here because LeetCode tags it Stack, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2297. Jump Game VIII?: LeetCode 2297. Jump Game VIII is rated Medium on LeetCode.
What is the time complexity of LeetCode 2297. Jump Game VIII?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2297. Jump Game VIII?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2297. Jump Game VIII cover?: LeetCode 2297. Jump Game VIII is tagged Stack, Graph, Array, Dynamic Programming, Shortest Path and Monotonic Stack on LeetCode.
Is LeetCode 2297. Jump Game VIII a premium problem?: Yes. LeetCode 2297. Jump Game VIII is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.