Problem overview
The method jump receives an array of non-negative integers, nums. You start at index 0, and each value says the maximum jump length from that position: from index i you can land on any index from i + 1 to i + nums[i]. The method returns the minimum number of jumps needed to reach the last index.
In the example, nums = [2, 3, 1, 1, 4] and 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 reaches index 4 from index 0, so one jump is not enough.
Approach: try every first jump and recurse
This is the Backtracking chapter, so the lesson tries all the possibilities. Define minJumps(nums, i) as the minimum number of jumps to reach the last index from index i. The answer to the problem is minJumps(nums, 0).
From index i, the first jump goes to some index j in i + 1 ... i + nums[i] (limited by the end of the array). After landing on j, the best continuation takes minJumps(nums, j) more jumps, so that choice costs 1 + minJumps(nums, j) in total. The best answer from i is the smallest cost over all choices of j. The recursion stops at the last index, where no jump is needed.
For [2, 3, 1, 1, 4], index 0 can go to index 1 or 2. From index 1 the options are indices 2, 3 and 4, and index 4 is the target, so minJumps(nums, 1) is 1. From index 2 (value 1) the only move is to index 3, and from there to index 4, so minJumps(nums, 2) is 2. The result is the smaller of 1 + 1 and 1 + 2, which is 2.
Step by step
- Delegate from
jump: returnminJumps(nums, 0), since the journey starts at the first cell. - Declare
minJumpsabovejump, taking the array and the indexiwithout labels and returning anInt. - Base case: if
iis the last index,nums.count - 1, return 0. - Start
resultatnums.count. A path to the last index needs at mostnums.count - 1jumps, so this plays the role of infinity: any real path beats it. It is avarbecause it will be updated. - Loop over the landing spots. Start a
var jati + 1. Thewhileloop runs whilej < nums.countandj <= i + nums[i], which keeps every jump inside both the array and the allowed length. Add 1 tojat the end of each pass. - Update the best cost:
result = min(result, 1 + minJumps(nums, j)). - Return
resultafter all first jumps have been tried.
The solution in Swift
class Solution {
func minJumps(_ nums: [Int], _ i: Int) -> Int {
if i == nums.count - 1 {
return 0
}
var result = nums.count
var j = i + 1
while j < nums.count && j <= i + nums[i] {
result = min(result, 1 + minJumps(nums, j))
j += 1
}
return result
}
func jump(_ nums: [Int]) -> Int {
return minJumps(nums, 0)
}
}
The Swift details worth a closer look:
- Global
min.min(a, b)is a free function in the standard library that works on any two comparable values, so it needs no import. Inside a class that has no method namedmin, the call resolves directly to it. - A
whileloop with two conditions.&&stops evaluating as soon as the left side is false. Afor j in i + 1...i + nums[i]loop would also need a separate bound for the array end, and it crashes when the upper bound is smaller than the lower one, which happens whennums[i]is 0. Thewhileform simply doesn't run in that case. - Passing the array.
[Int]is a value type, but the method never changes it, so Swift doesn't copy the storage when calling recursively. - No
++. Swift has no increment operator, so the loop usesj += 1. - Safe arithmetic. Swift's integer overflow stops the program. The values here are small (indices and counts), so
1 + minJumps(nums, j)andi + nums[i]don't get near the limit.
Complexity
Time: exponential in the worst case. Nothing remembers earlier answers, so minJumps(nums, j) is recomputed every time a different path reaches j. When every value is large enough to reach the end, as in [10, 9, 8, ..., 1], the number of calls doubles with each extra element: 16 calls for 5 elements, 512 for 10, and 524,288 for 20. That makes this version suitable for small inputs and for understanding the idea. Caching the answer for each index brings the time down to O(n²), and later lessons on this problem improve it further.
Space: O(n). The recursion goes at most one index deeper per call, so the stack holds at most n frames. Nothing else grows.
Edge cases and common mistakes
- One element.
[5]starts on the last index, so the answer is 0, whatever the value is. - All ones.
[1, 1, 1, 1]forces a jump per step, so the answer is 3. - Zeros in the middle. A cell holding 0 can't move anywhere, because its loop range is empty. The recursion then returns
nums.count, which stands for "no path". Such results are only meaningful when the last index can be reached some other way. For[3, 2, 1, 0, 4]the last index can't be reached, and the method returns 5, which is not a number of jumps. The lesson assumes the last index is reachable. - Stepping past the end. Without the
j < nums.countcondition, a large value would make the loop index run beyond the array, and readingnums[j]would crash. - Counting the final landing twice. The base case returns 0, not 1. The
1 +in the loop already counts the jump into the last index. - Greedy mistakes. Always taking the longest jump isn't optimal. In
[2, 3, 1, 1, 4]the longest jump from index 0 reaches index 2, which then needs two more jumps for a total of 3, while jumping to index 1 reaches the end in 2.
Testing
[2, 3, 1, 1, 4]gives2.[5]gives0.[1, 1, 1, 1]gives3.[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]gives1.
