Problem overview
The method jump receives an array nums of non-negative integers. You start at index 0, and nums[i] is the farthest you can jump forward from index i: any distance from 1 up to nums[i] is allowed. The method returns the minimum number of jumps needed to land on 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 from index 1 to the last index. No single jump from index 0 can reach index 4, since nums[0] is only 2.
Approach: label each cell with its jump count, left to right
Let dp[k] be the minimum number of jumps to reach cell k. Then dp[0] is 0, and the answer is dp[nums.count - 1]. A slow way to fill the table is to check, for each cell, every earlier cell that can reach it. That is O(n²) work.
A key fact makes it linear: the values of dp never decrease from left to right. A cell further along never needs fewer jumps than one before it. So for a cell k, the first cell i (the leftmost) that can reach it gives the smallest count, dp[i] + 1. Later cells that also reach k have a dp that is equal or larger, so they can't improve on it.
That suggests a single pointer j: the first cell that no earlier cell has reached yet. Cells are processed left to right. When the loop is at cell i, the cells j up to i + nums[i] are exactly the ones this cell can reach for the first time. Each gets dp[i] + 1, and j moves forward past them. The pointer never moves backward, so the total work is linear.
For [2,3,1,1,4]: cell 0 reaches cells 1 and 2, so both get 1. Cell 1 reaches up to index 4, so cells 3 and 4 get dp[1] + 1 = 2. The last entry is 2.
Step by step
- Create
dpas avararray of zeros withnums.countentries. The entry for cell 0 is correctly 0, and every other entry gets overwritten when its cell is first reached. - Create
jwith the value 1. It is the first cell not yet reached, because the start cell 0 is already in place. - Loop over every cell
iwith0..<nums.count. - Add the inner
whileloop. It runs whilejis reachable fromi, that isj <= nums[i] + i, andjis still inside the array,j < nums.count. - Label the cell. Inside it, cell
jis reached for the first time with one jump fromi, so setdp[j]todp[i] + 1and then increasej. - Return
dp[nums.count - 1], the jump count for the last cell.
The solution in Swift
class Solution {
func jump(_ nums: [Int]) -> Int {
var dp = [Int](repeating: 0, count: nums.count)
var j = 1
for i in 0..<nums.count {
while j <= nums[i] + i && j < nums.count {
dp[j] = dp[i] + 1
j += 1
}
}
return dp[nums.count - 1]
}
}
The Swift details worth knowing:
- Creating a zero-filled array.
[Int](repeating: 0, count: n)builds an array ofnzeros. It is a value type, sodpbelongs to this call alone. - No
++. Swift removed the increment operator, so the pointer moves withj += 1, on its own line. - Ranges.
0..<nums.countis a half-open range, soitakes the values 0 tonums.count - 1. For an empty array the range is empty and the loop body never runs. - Safe arithmetic.
nums[i] + iis anIntsum. Swift traps on overflow instead of wrapping, but with array-sized values it is nowhere near the limit. - Out-of-range index.
dp[nums.count - 1]on an empty array would read index -1 and crash. The problem always gives at least one cell.
Complexity
Time: O(n). The outer loop runs n times. The pointer j starts at 1, only moves forward and never passes n, so the inner loop's body runs at most n - 1 times across the whole call.
Space: O(n). The dp array has one entry per cell. A version that tracks only the current reach and the next reach would use O(1), but this lesson keeps the table so the idea is visible.
Edge cases and common mistakes
- One cell.
[0]gives 0. The inner loop never runs, becausej = 1is not belownums.count, anddp[0]is returned. - One big jump.
[5,1,1,1,1,1]gives 1: cell 0 reaches every other cell at once. - Steps of one.
[1,1,1,1]gives 3. - Unreachable end. The solution assumes the last cell can be reached. For
[0,1]the pointer never advances,dp[1]stays at its initial 0, and the method returns 0, which looks like a valid answer. The lesson's inputs always allow reaching the end. - Treating
nums[i]as an exact distance. It is a maximum. Any jump from 1 tonums[i]is allowed, which is why a whole run of cells gets labeled at once. - Reading the pointer as a position.
jis not where you stand. It is the boundary between cells that already have a jump count and cells that don't. - Allowing
jpast the array. Withoutj < nums.count, a largenums[i]would make the code write beyond the end ofdpand crash.
Testing
[2,3,1,1,4]gives2.[2,3,0,1,4]gives2.[1,1,1,1]gives3.[5,1,1,1,1,1]gives1.[0]gives0.
