Problem overview
The function jump receives an IntArray named nums of non-negative integers. You start at index 0, and nums[i] is the farthest you can jump forward from index i: any jump of 1 up to nums[i] steps is allowed. The function returns the smallest number of jumps that takes you to 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, 4. No single jump from index 0 reaches the end, because it covers at most 2 steps.
Approach: fill in the cheapest cost of each cell, left to right
Let dp[k] be the minimum number of jumps needed to reach index k. Then dp[0] = 0, and the answer is dp[nums.size - 1].
A direct way to fill the table would be to check, for every index k, every earlier index i that can reach it, and take the smallest dp[i] + 1. That is O(n²). One observation removes the inner search: dp never decreases from left to right. Take any cell k' to the right of k, and an optimal route to k'. Somewhere on that route, a jump starts left of k and lands at some cell q at or beyond k. The same jump could have been shortened to land exactly on k, so dp[k] <= dp[q] <= dp[k'].
That means the first index that can reach a cell gives the best value for it. Process indices in order, and let each one claim every cell it can reach that nobody has claimed yet. A single pointer j, the first unclaimed cell, is enough: cells are claimed from left to right, so everything before j is already done. Because j only moves forward, the inner loop runs at most n times in total, and the whole algorithm is O(n).
The lesson has other solutions to the same problem, such as a greedy scan that tracks the current farthest reach. This one keeps the full table, which makes the reasoning easy to follow.
Step by step
- Create the table.
val dp = IntArray(nums.size)holds one count per index. A newIntArrayis filled with zeros. That is already right fordp[0], and every other entry is overwritten when its cell is first reached. - Create the pointer.
var j = 1marks the first cell not yet reached by any jump. Cell 0 is the start, so the unreached cells begin at 1. - Loop over the indices. A
forloop withiovernums.indicesvisits each cell as a jump origin, in order. - Loop over what
ican newly reach. Awhileloop continues as long asj <= nums[i] + i, meaningjis within reach ofi, andj < nums.size, meaningjis still inside the array. - Claim the cell. Cell
jis reached for the first time, with one more jump than it took to reachi. Setdp[j]todp[i] + 1and advancej. Writing the index asj++does both in one statement. - Return
dp[nums.size - 1], the minimum number of jumps to the last cell.
The solution in Kotlin
class Solution {
fun jump(nums: IntArray): Int {
val dp = IntArray(nums.size)
var j = 1
for (i in nums.indices) {
while (j <= nums[i] + i && j < nums.size) {
dp[j++] = dp[i] + 1
}
}
return dp[nums.size - 1]
}
}
The Kotlin details worth a closer look:
IntArray(n)is zero-filled. The constructor with only a size creates an array of primitiveintvalues, all 0. No loop is needed to initialise it.valversusvar.dpis aval: the variable always refers to the same array, although its elements change.jis avarbecause it moves.dp[j++] = dp[i] + 1. Post-increment uses the old value ofjas the index and then adds 1. Forj = 1, it writes intodp[1]and leavesjequal to 2. Kotlin allows this inside an index expression.nums.indicesis the range0 until nums.size, so the loop never reads past the end.
Complexity
Time: O(n). The outer loop runs n times. The pointer j starts at 1, never moves backward and stops at nums.size, so the inner while body runs at most n - 1 times across the whole call. The total work is linear.
Space: O(n). The dp array has one entry per index. A greedy version that tracks only the current and next reach would use O(1) extra space.
Edge cases and common mistakes
- A single element. For
nums = [0], you already stand on the last index.dphas one entry, the loops claim nothing, and the function returns 0. - A jump that overshoots. For
[5, 1, 1], index 0 reaches beyond the end. Thej < nums.sizecheck stops the loop at the last cell, and the answer is 1. - Forgetting
j < nums.size. Large values then pushjpast the array, anddp[j++]throwsArrayIndexOutOfBoundsException. - Resetting
jfor eachi. Startingjati + 1each time re-claims cells and loses the linear bound. Cells already claimed must keep their first, smaller value. - The end must be reachable. The approach assumes you can get to the last index. For
[1, 0, 5], index 1 cannot move, so the end cannot be reached, but the loop still treats index 2 as a jump origin and the function returns 1. That input has no valid answer, and the function does not report it. - Counting indices instead of jumps. The answer is the number of jumps, not the number of cells visited. A path that visits three cells has made two jumps.
Testing
[2, 3, 1, 1, 4]gives2.[0]gives0.[1, 1, 1, 1]gives3.[5, 1, 1]gives1.[2, 3, 0, 1, 4]gives2.[1, 2, 3, 1, 1, 1]gives3.