Problem overview
The method Jump receives an int[] named nums of non-negative integers. You start on index 0, and each value is the maximum jump length from that cell: standing on a cell holding 3, you can move 1, 2 or 3 cells to the right. The method returns the minimum number of jumps needed to land on the last index.
In the example, nums = [2, 3, 1, 1, 4] has the answer 2. Jump 1 step from index 0 to index 1, then 3 steps from index 1 to the last index, which is index 4. No single jump reaches the end from index 0, since the largest jump there is 2, so 2 is the minimum.
Approach: try every first jump
This lesson solves the problem by plain recursion, the backtracking way of thinking. Let MinJumps(nums, i) be the minimum number of jumps needed to reach the last cell from cell i. Then:
- If
iis the last cell, the answer is 0: you are already there. - Otherwise, every cell from
i + 1up toi + nums[i]can be the target of the first jump. For each one, the cost is 1 (that jump) plusMinJumpsfrom the new cell. The answer is the smallest of these costs.
The same question is asked again from the new cell with a shorter remaining array. That repeated, smaller question is what makes the recursive solution short. The recursion always ends because every call moves to a larger index and the last index is the base case.
For [2, 3, 1, 1, 4], the call from index 0 tries index 1 and index 2. From index 1 it can reach indexes 2, 3 and 4. Reaching index 4 costs 1 jump from there, so index 1 has the answer 1, and the first jump to it makes a total of 2. Index 2 leads only to index 3, then to index 4, which costs 2 more jumps from index 2, so a first jump to index 2 gives 3. The smaller total, 2, wins.
The recursion tries every path, so it is only practical for short arrays. The cost section below shows how quickly the number of calls grows.
Step by step
- Delegate to the helper.
JumpreturnsMinJumps(nums, 0), because the journey starts at cell 0. - Declare
MinJumps. It is apublicmethod that returns anintand takes the array and the current indexi. - Base case. If
iisnums.Length - 1, you are on the last cell, so return 0. - Start with a large "infinity".
resultbegins atnums.Length. No path needs that many jumps, since the longest possible path usesnums.Length - 1, so any real path beats it. If no cell can be reached fromi,resultstays at this large value, which marks a dead end. - Loop over the reachable cells.
jstarts ati + 1and continues whilej < nums.Lengthandj <= i + nums[i]. The first condition keeps the loop inside the array and the second respects the jump limit. - Keep the best option. For each
j, the first jump costs 1 plus the best fromj.Math.Minkeeps the smaller of that and the best so far. - Return
resultafter every first jump has been tried.
The solution in C#
class Solution {
public int MinJumps(int[] nums, int i) {
if (i == nums.Length - 1) {
return 0;
}
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));
}
return result;
}
public int Jump(int[] nums) {
return MinJumps(nums, 0);
}
}
The C# details worth a closer look:
- The loop condition. It combines two tests with
&&: the first keepsjinside the array and the second respects the jump limit. Both must hold for the loop to continue. Math.Min. It is in theSystemnamespace and has overloads for every numeric type; with twointarguments it returns anint.- Method order doesn't matter.
JumpcallsMinJumps, andMinJumpscalls itself. C# doesn't need a method to be declared before another method uses it, unlike C. - Recursion is not tail-optimised. Each call waits for its children, so the stack holds one frame per cell along the current path. For this problem that is at most the array length.
- No overflow. The values added are small:
1 + MinJumps(...)is at mostnums.Length + 1.
Complexity
Time: exponential in the worst case. Each call loops over every reachable cell and recurses into each, and the same cell is reached again and again by different paths. When every value is large enough to reach the end, as in an array of 20 cells that all hold 20, the recursion makes 524,288 calls (that is 2 to the power 19). With 22 cells the count is 2,097,152, four times as many. Every extra cell doubles the work. The recursion computes the answer for the same cell many times, and the faster lessons on this problem avoid that.
On the example [2, 3, 1, 1, 4], the recursion makes just 11 calls, so short arrays are no problem.
Space: O(n). Nothing is allocated, but the call stack can be as deep as the number of cells: an array of ones makes a chain of calls that goes from index 0 to the last index.
Edge cases and common mistakes
- A single cell.
[0]returns 0, because index 0 is already the last index. - All ones.
[1, 1, 1, 1]returns 3: each jump moves one cell, so only one path exists. - Zeros in the middle. A cell holding 0 has no way forward. Its call skips the loop and returns
nums.Length, and1 + nums.Lengthnever beats a real answer, so paths through dead ends lose automatically. - An end that can't be reached. For
[3, 0, 0, 0, 0, 1], no path reaches the last index, and the method returns 6, the placeholdernums.Length, instead of a real count. Inputs where the end is reachable avoid this. - Looping to
nums.Lengthwithout the second condition. Using onlyj < nums.Lengthwould let the first jump be longer thannums[i], and the answer would be too small. - Off-by-one in the bound. The farthest reachable cell is
i + nums[i], inclusive. Using<there would forbid the longest jump. - Starting
resultat 0. ThenMath.Minwould always keep 0.
Testing
[2, 3, 1, 1, 4]gives 2.[0]gives 0.[1, 1, 1, 1]gives 3.[5, 0, 0, 0, 0, 0]gives 1, since the first jump reaches the end.