Problem overview
The method jump receives an Array[Int] called nums. You start at index 0, and nums(i) is the longest jump you can make from index i: any distance from 1 up to that value is allowed. The method returns the minimum number of jumps needed to reach the last index.
For [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, because its limit is 2.
Approach: reach every cell for the first time, left to right
Let dp(k) be the minimum number of jumps to reach cell k. A slow way to fill dp checks, for each cell, every earlier cell that could jump onto it. A key observation removes that work: the values of dp never decrease from left to right. Take two cells k < m and a best path to m. Some jump on that path starts left of k and lands on k or beyond it. A jump may be any length up to its limit, so the same starting cell could also land exactly on k. Reaching k therefore never needs more jumps than reaching m.
That monotonic shape means the first cell that can reach a given cell j gives its best answer. Cells are processed from left to right, so the first one that covers j is also the one with the smallest dp. Once j has its value, nobody needs to set it again.
A single pointer j records the first cell that no jump has reached yet. For each cell i, the cells from j up to i + nums(i) are exactly the cells that i reaches for the first time. They all get dp(i) + 1, and j moves past them. The pointer only moves forward, so the work for all values of i adds up to one pass over the array.
Following the example
For [2,3,1,1,4], dp starts as five zeros and j is 1. At i = 0 the reach is 0 + 2 = 2, so cells 1 and 2 get dp = 1 and j becomes 3. At i = 1 the reach is 1 + 3 = 4, so cells 3 and 4 get dp(1) + 1 = 2 and j becomes 5. The remaining iterations find j already past the end. The array is [0,1,1,2,2] and the answer is its last entry, 2.
Step by step
- Create
dp.Array.fill(nums.length)(0)makes an array of zeros.dp(0)really is 0, since you start there, and every other entry is overwritten the first time its cell is reached. - Declare
var j = 1. It is the first cell that no jump has reached. Cell 0 is the start. - Loop over the cells with
for (i <- nums.indices). - Add the inner
while. It runs whilej <= nums(i) + i, meaning celljis within reach of celli, andj < nums.length, meaningjis still inside the array. - Assign and advance. Cell
jis reached for the first time with one more jump than celli, sodp(j) = dp(i) + 1, and thenj += 1. - Return
dp(nums.length - 1), the last entry. It is the final expression, so noreturnis needed.
The solution in Scala
class Solution {
def jump(nums: Array[Int]): Int = {
val dp = Array.fill(nums.length)(0)
var j = 1
for (i <- nums.indices) {
while (j <= nums(i) + i && j < nums.length) {
dp(j) = dp(i) + 1
j += 1
}
}
dp(nums.length - 1)
}
}
Scala details worth a closer look:
nums.indices. It is the range0 until nums.length, the valid indices of the array. It reads more clearly than writing the bounds out.- Parentheses for indexing. Arrays are indexed as
nums(i)and written asdp(j) = .... Square brackets are for type parameters, as inArray[Int]. valversusvar.val dpfixes the array reference, and its elements can still change.jis avarbecause the variable itself is reassigned.- No
++. Scala has no increment operator, so the pointer moves withj += 1.
Complexity
Time: O(n). The outer loop makes n iterations. The pointer j moves forward by one each time the inner body runs and never moves back, and it stops at n, so the inner body runs at most n - 1 times in total.
Space: O(n). The dp array has one number per cell.
Edge cases and common mistakes
- One element. For
[0], no jump is needed, and the answer isdp(0), which is 0. You are already at the last index. - A huge first jump. For
[10,1,1], cell 0 reaches the end at once and the answer is 1. Thej < nums.lengthtest stops the loop at the array's end instead of writing outside it. - Zeros in the middle. For
[2,3,0,1,4]the answer is 2: jump from index 0 to 1, then from 1 to 4. The zero is only a problem if every route is forced to land on it. - Unreachable end. This solution assumes that the last cell can be reached. For
[3,2,1,0,4]it returns 1, which is not a real answer, because the last cell can't be reached at all. Check reachability separately if the input may not guarantee it. - Empty array.
dp(nums.length - 1)isdp(-1), which throwsArrayIndexOutOfBoundsException. - Starting
jat 0. That would overwritedp(0)withdp(0) + 1, and every answer would be one too large.
Testing
[2,3,1,1,4]gives2.[2,3,0,1,4]gives2.[0]gives0.[1,1,1,1]gives3.[10,1,1]gives1.
