Problem overview
The method jump receives an array of non-negative integers, nums. You start at index 0, and nums[i] is the longest jump you can make from index i: any length from 1 up to nums[i] is allowed. The method returns the smallest number of jumps needed to reach the last index.
For nums = [2, 3, 1, 1, 4] the answer is 2: jump 1 step from index 0 to index 1, then 3 steps to the last index. Jumping 2 steps first lands on index 2, which needs two more jumps, so that route takes 3.
Approach: try every first jump
This lesson sits in the backtracking chapter, so it solves the problem in the most direct way: try every possible first jump, and for each one ask the same question again from the cell you land on.
Define minJumps(nums, i) as the fewest jumps needed to get from cell i to the last cell. From cell i you can land on any cell j between i + 1 and i + nums[i], as long as j is inside the array. Choosing j costs one jump, and then you need minJumps(nums, j) more. The best choice is the smallest total:
minJumps(i) = 0 if i is the last cell
minJumps(i) = 1 + min of minJumps(j) over reachable j otherwiseEvery jump moves to a larger index, so a call can only recurse into later cells and the recursion always ends at the last cell (or at a cell with nowhere to go).
This tries every route, so it is slow on long arrays, as the complexity section explains. Other lessons on this problem make it faster. Here the goal is to see the recursive structure first.
Step by step
- Delegate from
jump. The answer starts at cell 0, so returnthis.minJumps(nums, 0). Methods call each other throughthis. - Declare
minJumpswithnums: number[]andi: number, returning anumber. - Base case. When
iisnums.length - 1, you are already on the last cell, so return 0. - Keep a running best in
result, starting atnums.length. No real route needs that many jumps (at mostnums.length - 1), so it plays the part of infinity: any real route beats it. - Loop over the reachable cells.
jstarts ati + 1and runs whilej < nums.lengthandj <= i + nums[i]. The first condition keeps you inside the array and the second respects the jump length. - Update the best. Inside the loop, the route that jumps to
jfirst costs1 + this.minJumps(nums, j), andMath.minkeeps the smaller of that andresult. - Return
resultafter every first jump has been tried.
The solution in TypeScript
class Solution {
minJumps(nums: number[], i: number): number {
if (i === nums.length - 1) {
return 0;
}
let result: number = nums.length;
for (let j = i + 1; j < nums.length && j <= i + nums[i]; ++j) {
result = Math.min(result, 1 + this.minJumps(nums, j));
}
return result;
}
jump(nums: number[]): number {
return this.minJumps(nums, 0);
}
}
Tracing [2, 3, 1, 1, 4]: from index 0 the loop tries index 1 and index 2. From index 1 (value 3) it can reach indices 2, 3 and 4, and index 4 is the last cell, so minJumps(nums, 1) is 1. From index 2 the best route is 2 more jumps, so that first jump would total 3. The smaller total, 1 + 1, gives 2.
TypeScript details worth knowing:
- The loop condition has two parts.
&&stops as soon as the first part is false.j < nums.lengthcomes first, so the loop never uses an index past the end. Math.minwith plain numbers. It returns the smaller of its arguments. There is no integer overflow in TypeScript'snumber, and the values here are tiny anyway.- The annotation on
result(: number) is not needed, because the compiler infers it fromnums.length. The annotation disappears from the JavaScript that runs. - Methods and
this. The helper is called asthis.minJumps. Writing a bareminJumps(nums, j)would look for a function with that name outside the class and fail.
Complexity
Let n be the length of nums.
Time: exponential in the worst case. Nothing remembers an answer, so the same cell is solved again every time a different route reaches it. If every element is large enough to reach the last cell, each cell can be reached through every subset of the cells before it, and the number of calls is 2^(n-1). A test run with every element equal to the array length counted 512 calls for n = 10, 16,384 for n = 15 and 16,777,216 for n = 25. Arrays of a few dozen cells with big jumps are already too slow. When the jumps are small, there are far fewer routes.
Space: O(n). The only memory used is the recursion stack. Each call moves at least one cell right, so the depth is at most n.
Edge cases and common mistakes
- A single cell.
[0]starts on the last cell, so the answer is 0. - A jump length of 0. The loop does not run, so
resultstays atnums.length. That value marks a dead end, and it is large enough that the caller's1 + ...never beats a real route. - Unreachable last cell. The lesson's tests only give arrays where the last cell can be reached. For
[1, 0, 1]the method returns 3, which isnums.lengthand not a real jump count; handle that case yourself if it can occur. - Greedy jumping. Always taking the longest jump is wrong. In
[2, 3, 1, 1, 4]it goes to index 2 and needs 3 jumps, while the answer is 2. Trying every first jump avoids guessing. - Going past the end. Without
j < nums.lengththe loop would readnums[j]from an index that does not exist. TypeScript givesundefinedthere instead of an error, so a bug like this can go unnoticed. - Starting
jati. A jump of length 0 would callminJumpson the same cell, forever.
Testing
[2, 3, 1, 1, 4]gives2.[0]gives0.[1, 1, 1, 1]gives3.[3, 0, 0, 0]gives1.[5, 1, 1, 1, 1, 1]gives1.