Jump Game VI

Jump Game VI is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Sliding Window pattern, in the Monotonic Queue for Max/Min subpattern.

Problem statement

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

Constraints:

- 1 <= nums.length, k <= 105

- -104 <= nums[i] <= 104

Topics and companies

Topics: Array, Dynamic Programming, Queue, Heap (Priority Queue), Monotonic Queue.

Reported in interviews at Uber.

How to practise Jump Game VI on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(k) space.

Open Jump Game VI in the code editor, or read the Jump Game VI editorial for a worked solution with its approach and complexity analysis.

Where Jump Game VI sits in the DSA pattern sheet

Problems related to Jump Game VI

Other problems that use the same Monotonic Queue for Max/Min and Sliding Window techniques:

Preparing this workspace.