Problem overview
You get an array of non-negative integers and start at index 0. Each element is the maximum jump length from that position, so from index i you can land on any index from i + 1 to i + nums[i]. The method Jump returns the minimum number of jumps needed to reach the last index.
For [2, 3, 1, 1, 4] the answer is 2. Jump one step from index 0 to index 1, then three steps from index 1 to the last index. No single jump from index 0 can reach index 4, because nums[0] is only 2.
The lesson asks you to add memoization to the plain recursive solution, with O(n^2) time and O(n) extra space.
Approach: ask each cell for its best answer, once
Define MinJumps(nums, i, cache) as the minimum number of jumps to reach the last index when you stand on index i. Two facts give a recurrence:
- On the last index, the answer is 0.
- Anywhere else, you pick a first jump to some reachable index
jand then continue optimally from there. That costs1 + MinJumps(j), and the answer foriis the smallest of these over every reachablej.
Without a cache, this recursion reaches the same index along many different paths and recomputes its answer each time. In [2, 3, 1, 1, 4], index 3 is reached from index 1 and again from index 2, and without a cache it is recomputed on each visit. On a long array with large jump lengths the number of paths grows exponentially.
The answer for a given index never changes, so we store it in a Dictionary<int, int> that maps an index to its answer. Each index is then computed once. Computing one index takes a loop over at most n - 1 candidates, which gives O(n^2) time overall, and the dictionary holds at most n entries.
Tracing the example: MinJumps(0) calls MinJumps(1), which calls MinJumps(2), then MinJumps(3), which jumps straight to the last index and gets 1. Back in MinJumps(2), the only candidate gives 1 + 1 = 2. In MinJumps(1), index 3 is now a cache hit (1 jump) and index 4 is the base case, so the best is 1 + 0 = 1. Finally, MinJumps(0) compares 1 + 1 through index 1 and 1 + 2 through index 2, and returns 2.
Step by step
- Create the cache in
Jumpas an emptyDictionary<int, int>. - Return the helper's answer for index 0:
MinJumps(nums, 0, cache). Writing the call first lets you think about what the helper must do. - Declare the helper above
Jumpwith the array, the index and the cache as parameters, returning anint. The cache is a parameter so that every recursive call shares it. - Base case: on the last index,
nums.Length - 1, return 0. Every recursive call moves to a larger index, so all chains of calls end here or at a dead end. - Cache hit: if the dictionary already contains
i, return the stored value. - Start the minimum at
nums.Length. A path never needs more thannums.Length - 1jumps, so this acts as "infinity" that any real path beats. - Loop over the targets from
i + 1whilej < nums.Lengthandj <= i + nums[i]. The first condition keeps you inside the array, the second respects the jump length. - Update the best with
Math.Min(result, 1 + MinJumps(nums, j, cache)). - Store the result in
cache[i]before returning. - Return the result.
The solution in C#
class Solution {
public int MinJumps(int[] nums, int i, Dictionary<int, int> cache) {
if (i == nums.Length - 1) {
return 0;
}
if (cache.ContainsKey(i)) {
return cache[i];
}
int result = nums.Length;
for (int j = i + 1; j < nums.Length && j <= i + nums[i]; ++j) {
result = Math.Min(result, 1 + MinJumps(nums, j, cache));
}
cache[i] = result;
return result;
}
public int Jump(int[] nums) {
Dictionary<int, int> cache = new Dictionary<int, int>();
return MinJumps(nums, 0, cache);
}
}
C# details worth knowing
- The dictionary indexer.
cache[i] = resultadds the key if it is new. Readingcache[i]for a missing key throwsKeyNotFoundException, which is why the read happens only afterContainsKeyreturnedtrue. - Short-circuit loop condition. In
j < nums.Length && j <= i + nums[i], the left side is checked first, so the loop never evaluates an index outside the array. - Arrays and
Length.nums.Lengthis a property, not a method. There are no parentheses. - Pass the cache along. A
Dictionaryis a reference type, so every call that receivescacheworks on the same object. That is what lets a deep call's work be reused by its callers.
Complexity
There are n distinct indices, and each is computed at most once. Computing one index loops over at most n - 1 later indices, and every call inside that loop either returns a cached value in constant time or computes an index for the first time. That gives O(n^2) time. The dictionary stores up to n answers and the recursion can be about n calls deep (for example when every element is 1), so the extra space is O(n).
Edge cases and common mistakes
- A one-element array. The start is already the last index, so the base case returns 0 immediately. For
[0]the answer is 0. - Checking the cache after the loop. The cache lookup must come before the loop, or the loop recomputes everything and the cache saves nothing.
- Forgetting to store. If you never assign
cache[i], the code stays correct but is as slow as plain recursion. - Looping past the array. Without
j < nums.Length, a largenums[i]sendsjbeyond the end and the next call readsnums[j], which throwsIndexOutOfRangeException. - Unreachable last index. With input such as
[1, 0, 1], the last index can't be reached and this code returnsnums.Length, here 3, because the placeholder value is never beaten. The lesson's inputs are assumed to be reachable.
Testing
Running the solution gives these results:
[2, 3, 1, 1, 4]returns 2.[1, 1, 1, 1]returns 3, one jump per step.[0]returns 0.