We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Jump Game VI

Difficulty: Medium

Problem Description

You are given a 0-indexed integer array nums and an integer k. You are initially standing at index 0. In one move, you can jump at most k steps forward without going outside the boundaries of the array. You want to reach the last index of the array (index n - 1). Your score is the sum of all nums[j] for each index j you visited in the array. Return the maximum score you can get.

Key Insights

  • You can jump from index i to any index in the range [i + 1, min(n - 1, i + k)].
  • The goal is to maximize the score by selecting the best possible indices to jump to.
  • A dynamic programming approach can be utilized to keep track of the maximum score at each index.
  • A deque can be used to efficiently manage potential scores from previous indices within the jump range.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use dynamic programming in conjunction with a double-ended queue (deque). We maintain an array dp where dp[i] represents the maximum score achievable when reaching index i. We initialize dp[0] to nums[0] since we start there.

As we iterate through the array, we use the deque to keep track of indices in a way that allows us to quickly find the maximum score from the previous k indices. For each index i, we calculate dp[i] as the value of nums[i] plus the maximum score from the deque. We also ensure to remove indices from the deque that are out of the jump range or that have lower scores than the current index to maintain the property of the deque.

Code Solutions

from collections import deque

def maxScore(nums, k):
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    deq = deque([0])  # Store index of the dp array

    for i in range(1, n):
        # Remove indices from the deque that are out of the jump range
        while deq and deq[0] < i - k:
            deq.popleft()
        
        # Calculate dp[i] using the maximum from the deque
        dp[i] = nums[i] + (dp[deq[0]] if deq else 0)

        # Maintain the deque for future indices
        while deq and dp[deq[-1]] < dp[i]:
            deq.pop()
        deq.append(i)

    return dp[-1]
← Back to All Questions