Problem overview
The method jump(_ nums: [Int]) -> Int receives an array of non-negative integers. You start at index 0, and nums[i] is the maximum length of a jump from index i: you may move forward by any distance from 1 to nums[i]. The method returns the minimum number of jumps needed to reach the last index.
For [2, 3, 1, 1, 4] the answer is 2. From index 0 you can jump 1 step to index 1, which holds 3, and from there 3 steps reach index 4, the last one. No single jump gets from index 0 to index 4, so one jump is not enough.
The lesson asks you to add memoization to the plain recursive solution, with O(n^2) time and O(n) extra space.
Approach: the best answer from each index, remembered
Define minJumps(i) as the minimum number of jumps needed to reach the last index starting from index i. Then:
- If
iis the last index, the answer is 0. - Otherwise, try every landing cell
jfromi + 1up toi + nums[i](without leaving the array). A first jump tojcosts 1 plusminJumps(j). The answer is the smallest of these.
Without memoization this recursion is very slow, because many different paths reach the same index j, and each time the answer for j is recomputed from scratch. The number of calls can grow exponentially with the length of the array.
The fix is to store each index's answer the first time it is computed. Every later request is a dictionary lookup. There are n indices, and each is computed once with a loop of up to n steps, which gives O(n^2) time. The dictionary holds at most n entries and the recursion is at most n calls deep, so the extra space is O(n).
Step by step
- Create the cache in
jumpasvar cache = [Int: Int](), mapping an index to its answer. It's avarbecause the helper will add entries to it. - Call the helper for the start:
return minJumps(nums, 0, &cache). The ampersand passescacheas aninoutargument. You can write this line before the helper exists. - Declare the helper
minJumps(_ nums: [Int], _ i: Int, _ cache: inout [Int: Int]) -> Int. Dictionaries are values in Swift, soinoutis what lets the helper's writes reach the caller's dictionary. - Base case: if
i == nums.count - 1, return 0. You are already on the last cell. Every call moves to a larger index, so every chain of calls ends here or at a cell with no moves. - Look in the cache:
if let cached = cache[i] { return cached }. This is the line that makes memoization pay off. - Start
resultatnums.count. No route needs that many jumps (at mostnums.count - 1), so it acts as infinity that any real route beats. - Loop over the landing cells. A
var jstarts ati + 1, and awhileloop runs as long asj < nums.countandj <= i + nums[i], ending each pass withj += 1. - Take the minimum:
result = min(result, 1 + minJumps(nums, j, &cache)). The same cache goes into the recursive call. - Store the answer with
cache[i] = resultbefore returning, so this index is never computed again. - Return
result.
The solution in Swift
class Solution {
func minJumps(_ nums: [Int], _ i: Int, _ cache: inout [Int: Int]) -> Int {
if i == nums.count - 1 {
return 0
}
if let cached = cache[i] {
return cached
}
var result = nums.count
var j = i + 1
while j < nums.count && j <= i + nums[i] {
result = min(result, 1 + minJumps(nums, j, &cache))
j += 1
}
cache[i] = result
return result
}
func jump(_ nums: [Int]) -> Int {
var cache = [Int: Int]()
return minJumps(nums, 0, &cache)
}
}
Swift details worth a closer look:
inoutand&. The caller marks the argument with&, and the callee declares itinout. The changes made inside the call are copied back to the caller's variable when the call returns, so all recursive calls work on one shared dictionary. The variable must be avar.if leton a dictionary lookup.cache[i]is anInt?:nilwhen the key is missing.if let cached = cache[i]runs its body only when a value exists and gives it a name, with no force unwrap. This also handles a stored value of 0 correctly.- Passing
numsis cheap. Arrays are values, but Swift copies the storage only when one of the copies is changed. The helper never modifiesnums, so passing it down the recursion copies nothing. min. The globalmin(a, b)works for any two values of the same comparable type. Both arguments here areInt.- Why
whileand not a range. The upper limit is the smaller ofnums.count - 1andi + nums[i]. The loop condition checks both, so it never leaves the array. A range such as(i + 1)...(i + nums[i])would crash whennums[i]is 0, because the upper bound would be below the lower bound.
Complexity
Time: O(n^2). Each index is computed once. Computing it loops over at most n - 1 landing cells, and each of those is a cache hit or a recursive computation that is itself counted once. In total, that is at most about n loop passes per index.
Space: O(n). The cache has up to n entries and the recursion is at most n frames deep. For very long arrays, a deep recursion eventually exhausts the stack, which crashes the program. The iterative version in a later lesson avoids that.
Edge cases and common mistakes
- One element.
[1]returns 0: the start is already the last index. - Big first jump.
[5, 1, 1, 1, 1, 1]returns 1, since the first jump can reach the last index directly, and the loop never goes past the end of the array. - Zeros in the middle.
[2, 3, 0, 1, 4]returns 2: the route through index 2 is a dead end, and the minimum picks the route through index 1. - Unreachable end. Cells with 0 that block every route leave
resultatnums.countor more. For[0, 1]the method returns 2, not a "no route" value. The lesson's tests only use arrays whose last index can be reached. - Not storing the answer. Reading the cache without ever writing
cache[i] = resultmakes the code correct but exponentially slow. - Using a fresh cache in each call. The cache must be created once in
jumpand passed down. Creating a new dictionary inside the helper would reuse nothing. - Forgetting
&orinout. Swift rejects a call that passes aninoutparameter without the ampersand.
Testing
[2, 3, 1, 1, 4]gives2.[1, 1, 1, 1]gives3.[2, 3, 0, 1, 4]gives2.[5, 1, 1, 1, 1, 1]gives1.[1]gives0.
