Problem overview
The method jump receives an array nums of non-negative integers. You start at index 0, and nums(i) is the maximum length of a jump from index i. The goal is to reach the last index in the minimum number of jumps, and the method returns that number.
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 reaches index 4, so one jump is not enough.
The statement sets a budget of O(n^2) time and O(n) extra space, and asks you to add memoization to the plain recursive solution.
Approach: recursion that remembers its answers
Define minJumps(nums, i, cache) as the minimum number of jumps needed to reach the last cell starting from cell i. From i you can land on any cell from i + 1 to i + nums(i), as long as it is inside the array. The best plan that starts with a jump to cell j costs 1 jump plus minJumps(nums, j, cache), and the answer for i is the smallest of these over every reachable j. When i is the last index, the answer is 0.
Without memoization, the recursion reaches the same cell by many different routes and recomputes its answer each time, which takes exponential time. The fix is a cache from index to answer. There are only n distinct cells, and each is computed once. Computing one cell loops over up to n reachable cells, so the total is O(n^2).
The lesson also has an iterative version of this idea and a faster greedy one; here the focus is the top-down recursion with a cache.
Step by step
- Create the cache in
jumpas a new emptyscala.collection.mutable.Map[Int, Int], declared withval. It must be the mutable map so the helper can add entries. - Return
minJumps(nums, 0, cache), since the answer starts from cell 0. The helper doesn't exist yet; the next steps write it. - Declare
minJumpsabovejump, taking the array, the indexiand the cache, and returning anInt. - Base case. When
i == nums.length - 1, you are already on the last cell, so return 0. Every recursive call moves to a larger index, so all chains of calls end here or at a cell with nowhere to go. - Cache hit. If the cache contains
i, returncache(i)straight away. - Start
resultatnums.length, as avar. No path needs that many jumps (at mostnums.length - 1), so it works as infinity. - Walk the reachable cells with
var j = i + 1and awhileloop that runs whilej < nums.lengthandj <= i + nums(i), ending the body withj += 1. - Take the minimum of
resultand1 + minJumps(nums, j, cache)withMath.min, passing the same cache down. - Store the answer with
cache(i) = resultbefore returning it, so this cell is never computed again. - Return
result.
The solution in Scala
class Solution {
def minJumps(nums: Array[Int], i: Int, cache: scala.collection.mutable.Map[Int, Int]): Int = {
if (i == nums.length - 1) {
return 0
}
if (cache.contains(i)) {
return cache(i)
}
var result = nums.length
var j = i + 1
while (j < nums.length && j <= i + nums(i)) {
result = Math.min(result, 1 + minJumps(nums, j, cache))
j += 1
}
cache(i) = result
return result
}
def jump(nums: Array[Int]): Int = {
val cache = scala.collection.mutable.Map[Int, Int]()
return minJumps(nums, 0, cache)
}
}
The Scala details worth a closer look:
- The cache is a mutable map. Scala's default
Mapis immutable.scala.collection.mutable.Mapsupportscache(i) = result, which calls the map'supdatemethod, and reading withcache(i). - Check before reading.
cache(i)on a missing key throwsNoSuchElementException. That is whycontainscomes first. Alternatively,cache.get(i)returns anOption. - Array indexing uses parentheses.
nums(i), notnums[i];nums.lengthhas no parentheses. varversusval.resultandjchange, so they arevar; the cache reference never changes, so it is aval, even though the map's contents do.- Short-circuit
&&. The loop condition checksj < nums.lengthfirst, andj <= i + nums(i)second, so the two bounds are tested in order. - Explicit
return. The lesson uses it; in idiomatic Scala the last expression of a block is already its value.
Complexity
Time: O(n^2). There are at most n distinct values of i, and each is computed once. A computation loops over at most n - 1 cells, and every recursive call inside it either returns at once (cache hit or base case) or computes a new cell. The total is at most n * n loop steps.
Space: O(n). The cache holds one entry per cell, and the recursion can go as deep as n calls (for example when every nums(i) is 1), so the stack is O(n) as well. A deep chain of calls is also the reason the iterative version is useful for large arrays.
Edge cases and common mistakes
- A single element.
[0]is already at the last index, so the answer is 0. - The example.
[2, 3, 1, 1, 4]returns 2. - All ones.
[1, 1, 1, 1]needs 3 jumps, one per step. - One long jump.
[5, 0, 0, 0, 0, 0]returns 1: one jump of 5 lands on the last index. If the number were larger, the checkj < nums.lengthwould keep the loop inside the array. - Stuck cells. A cell with
nums(i) = 0has no loop iterations, so its answer isnums.length, the "infinity" value. For[1, 0, 3]the last cell can't be reached, and the method returnsnums.length, 3, rather than a real jump count. The lesson's tests don't use such arrays. - Forgetting to store the result. Without
cache(i) = result, the cache never fills and the running time returns to exponential. - Letting the loop pass the end. Without
j < nums.length, a largenums(i)would read past the array and throwArrayIndexOutOfBoundsException.
Testing
[2, 3, 1, 1, 4]gives2.[0]gives0.[1, 1, 1, 1]gives3.[5, 0, 0, 0, 0, 0]gives1.[2, 0, 1]gives1.
