Leetcode.com problem 1696: "Jump-Game-VI"

James S. Plank

Mon Jul 11 23:54:03 EDT 2022

Medium problem.

Problem Statement.
A skeleton with a main() that reads problems from stdin. It reads in the array and k.
Solution.cpp -- A commented solution.
tests.sh -- Testing script.
answers.txt -- Correct output of the testing script.
Success Rate (as of July, 2022): 46.4%

In case Leetcode's servers are down

If Leetcode's servers are down, I've given you tools to do the problem anyway. Do the solution in main.cpp, and then you can test yourself with tests.sh. Your output should match answers.txt, and your timing should be roughly the same as mine, which was just under 20 seconds.

Here is a summary of the problem:

You are given an array called nums of integers, whose values are between -10,000 and 10,000.
The size of nums is at most 100,000.
You are given in integer k which is between 1 and the size of nums.
You start at index 0.
At each step, if you are at index i, you may "jump" to any index between i+1 and i+k.
You will end at the last element of nums.
Your score is the sum of each element of nums that you have been on.
Return the maximum possible score.

The examples

#1: nums = [1,-1,-2,4,-7,3], k = 2. Answer: 7: Visit 1, -1, 4, 3.
#2: nums = [10,-5,-2,4,0,3], k = 3. Answer: 17: Visit 10, 4, 3.
#3: nums = [1,-5,-20,4,-1,3,-6,-3], k = 2.  Answer: 0: Visit 1, -5, 4, 3, -3.

Hints

Let n be the size of nums.

You can do this with dynamic programming, but unless you think about it a little, your solution will be too slow. Let's go over the DP solution, and then think about how to make it fast. The recursive function is DP(i), which is the answer when you start at index i. The base case is DP(n-1), whose value is nums[n-1]. Then, for all other i:

DP(i) equals nums[i] plus the maximum of DP(i+1) through DP(min(n-1,i+k)). The answer is DP(0). So, let's do example 1, showing DP(i) from big i down to zero:

DP(5) = 3 --      base case.
DP(4) = 4 -- -7 + DP(5)
DP(3) = 7 --  4 + max(DP(4),DP(5)).
DP(2) = 5 -- -2 + max(DP(3),DP(4)).
DP(1) = 6 -- -1 + max(DP(2),DP(3)).
DP(0) = 7 --  1 + max(DP(1),DP(2)).

Adding a cache to this (step 2 of dynamic programming) is simple, so let's go straight to step 3 of dynamic programming, where we realize that the recursive calls are all to bigger values of i, so we can remove the recursion by filling in the cache from big i to small i. Something like this:

cache.resize(n);
for (i = n-1; i >= 0; i--) {
  top = (i+k < n-1) ? i+k : n-1;
  cache[i] = nums[i] + max(cache[i+1] to cache[top])
}

And the answer is cache[0].

Before you program this up, think about what happens when k is big. If you try to implement "max(cache[i+1] to cache[top])" with a for loop, then the running time of your program is going to be O(nk). Since k may be as big as n, this will be O(n²), which is too slow.

Use a multiset

The solution to that problem is to use a multiset, that has every value from cache[i+1] to cache[top] in it. You can find the maximum value in O(1) time, and then you can erase cache[top] and add cache[i] in O(log k) time. Therefore, your running time will be O(n log k), which is nice and fast.

Let's show the steps of example 3:

i     cache[i]      multiset before    action at the end of the step                multiset after
-     --------      ----------------   -----------------------------------------    --------------
5     3                                Insert cache[5] = 3                          { 3 }
4     0+3=3         { 3 }              Insert cache[4] = 3                          { 3, 3 }
3     4+3=7         { 3, 3 }           Insert cache[3] = 7                          { 3, 3, 7 }
2     -2+7=5        { 3, 3, 7 }        Delete cache[5] = 3, Insert cache[2] = 5     { 3, 5, 7 }
1     -5+7=2        { 3, 5, 7 }        Delete cache[4] = 3, Insert cache[1] = 2     { 2, 5, 7 }
0     -10+7=17      { 2, 5, 7 }        Delete cache[3] = 7, Insert cache[0] = 17    { 2, 5, 17 }

My solution, in Solution.cpp, was fast enough to be accepted, but didn't blow anyone away:

Runtime: 535 ms, faster than 13.56% of C++ online submissions for Jump Game VI.
Memory Usage: 135.8 MB, less than 5.44% of C++ online submissions for Jump Game VI.