In this guide, you will get 1696. Jump Game VI LeetCode Solution with the best time and space complexity. The solution to Jump Game VI problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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. That is, you can jump from index i to any index in the range [i + 1, min(n – 1, i + k)] inclusive.
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.
Example 1:
Input: nums = [1,-1,-2,4,-7,3], k = 2
Output: 7
Explanation: You can choose your jumps forming the subsequence [1,-1,4,3] (underlined above). The sum is 7.
Example 2:
Input: nums = [10,-5,-2,4,0,3], k = 3
Output: 17
Explanation: You can choose your jumps forming the subsequence [10,4,3] (underlined above). The sum is 17.
Example 3:
Input: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
Output: 0
class Solution {
public:
int maxResult(vector<int>& nums, int k) {
// Stores dp[i] within the bounds.
deque<int> maxQ{0};
// dp[i] := the maximum score to consider nums[0..i]
vector<int> dp(nums.size());
dp[0] = nums[0];
for (int i = 1; i < nums.size(); ++i) {
// Pop the index if it's out-of-bounds.
if (maxQ.front() + k < i)
maxQ.pop_front();
dp[i] = dp[maxQ.front()] + nums[i];
// Pop indices that won't be chosen in the future.
while (!maxQ.empty() && dp[maxQ.back()] <= dp[i])
maxQ.pop_back();
maxQ.push_back(i);
}
return dp.back();
}
}; /* code provided by PROGIEZ */
1696. Jump Game VI LeetCode Solution in Java
class Solution {
public int maxResult(int[] nums, int k) {
// Stores dp[i] within the bounds.
Deque<Integer> maxQ = new ArrayDeque<>(List.of(0));
// dp[i] := the maximum score to consider nums[0..i]
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; ++i) {
// Pop the index if it's out-of-bounds.
if (maxQ.peekFirst() + k < i)
maxQ.pollFirst();
dp[i] = dp[maxQ.peekFirst()] + nums[i];
// Pop indices that won't be chosen in the future.
while (!maxQ.isEmpty() && dp[maxQ.peekLast()] <= dp[i])
maxQ.pollLast();
maxQ.offerLast(i);
}
return dp[nums.length - 1];
}
} // code provided by PROGIEZ
1696. Jump Game VI LeetCode Solution in Python
class Solution:
def maxResult(self, nums: list[int], k: int) -> int:
# Stores dp[i] within the bounds.
maxQ = collections.deque([0])
# dp[i] := the maximum score to consider nums[0..i]
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1, len(nums)):
# Pop the index if it's out-of-bounds.
if maxQ[0] + k < i:
maxQ.popleft()
dp[i] = dp[maxQ[0]] + nums[i]
# Pop indices that won't be chosen in the future.
while maxQ and dp[maxQ[-1]] <= dp[i]:
maxQ.pop()
maxQ.append(i)
return dp[-1] # code by PROGIEZ
