Problem overview
The function jump receives an IntArray of non-negative integers. You start at index 0, and each value is the maximum jump length from that position. The goal is to reach the last index in as few jumps as possible, and the function returns that minimum number of jumps.
For [2, 3, 1, 1, 4] the answer is 2: jump one step from index 0 to index 1, then three steps from index 1 to the last index. No single jump can cover the whole array, because the first value is only 2.
The statement asks for memoization applied to the plain recursive solution, with O(n^2) time and O(n) extra space.
Approach: ask the same question from every cell
Define minJumps(i) as the minimum number of jumps needed to reach the last cell starting from cell i. Then the answer is minJumps(0). From cell i, the first jump lands on any cell j between i + 1 and i + nums[i], as long as j is inside the array. A path starting with that jump costs 1 + minJumps(j), so minJumps(i) is the smallest of those values.
Written as plain recursion, this works but repeats work. Many different paths reach the same cell j, and each time the recursion recomputes minJumps(j) from scratch. The fix is memoization: the answer for a cell does not depend on how you got there, so compute it once, store it under the key i, and return the stored value afterwards.
That bounds the work. There are n cells, each computed once, and computing one cell loops over at most n landing cells. That gives O(n^2) time. The cache holds one entry per cell, which gives O(n) space.
Step by step
- Create the cache in
jumpas an emptyHashMap<Int, Int>that maps each index to its answer once known. - Delegate to a helper. Return
minJumps(nums, 0, cache), since every path starts at cell 0. The helper is written next. - Declare
minJumpswith the array, the indexiand the cache. It returns anInt. - Base case. When
iis the last index, you are already there, so the answer is 0. Every recursive call moves to a larger index, so all chains of calls end here or at a cell with no moves. - Check the cache. If the key
iis present, return the stored answer. - Start
resultatnums.size. No path needs that many jumps (at mostnums.size - 1), so any real path beats it. It plays the role of infinity. - Loop over the landing cells. Start
jati + 1and continue whilej < nums.sizeandj <= i + nums[i]. - Update the best. For each
j, take the smaller ofresultand1 + minJumps(nums, j, cache). - Save and return. Store
resultin the cache underibefore returning it.
The solution in Kotlin
class Solution {
fun minJumps(nums: IntArray, i: Int, cache: HashMap<Int, Int>): Int {
if (i == nums.size - 1) {
return 0
}
if (cache.containsKey(i)) {
return cache[i]!!
}
var result = nums.size
var j = i + 1
while (j < nums.size && j <= i + nums[i]) {
result = Math.min(result, 1 + minJumps(nums, j, cache))
j++
}
cache[i] = result
return result
}
fun jump(nums: IntArray): Int {
val cache = HashMap<Int, Int>()
return minJumps(nums, 0, cache)
}
}
The Kotlin details worth a closer look:
valandvar. The cache is aval, because the variable always refers to the same map even though the map's contents change.resultandjarevar, since they are reassigned.cache[i]!!. A map lookup returnsInt?, withnullfor a missing key. AftercontainsKeyhas confirmed the key,!!turns the value into a plainInt.Math.min. This is Java'sjava.lang.Math, available because Kotlin on the JVM can call Java classes directly. Kotlin's ownminOf(a, b)does the same job and is the more idiomatic choice.- Short-circuit
&&. The loop checksj < nums.sizefirst. Oncejleaves the array, the second part is not evaluated, so the loop never indexes outside the array. - Passing the cache. A
HashMapis an object, so every call receives a reference to the same map. This sharing is what makes the stored answers visible to later calls.
Complexity
Time: O(n^2). The body of minJumps runs fully once per cell, because after that the cache answers. One run loops over at most n landing cells, and each landing is either a cache lookup or the one computation of that cell. Summed over all cells, the work is at most n * n.
Space: O(n). The cache has one entry per cell. The recursion can go as deep as the array is long, when every jump is a single step, so the call stack also takes O(n). A very long array of 1s can exhaust the stack, which the iterative version in the next lesson avoids.
Edge cases and common mistakes
- One element.
[0]starts on the last index, so the answer is 0 with no jumps. - Exactly one jump.
[3, 1, 1, 1]returns 1, because the first value reaches the last cell directly. - Zeros in the middle.
[2, 0, 1, 1]returns 2: jump from index 0 to index 2, then to index 3. The loop from cell 1 never runs, so the stored answer for that cell stays atnums.size, a value larger than any real answer. Paths through it never win. - An unreachable end. The lesson assumes the last index can be reached. For
[1, 0, 5]the function returns 3, which is only a leftover of the infinity marker and not a real number of jumps. - Jumping past the end. Without the
j < nums.sizecheck, a big value likenums[0] = 100in a short array would read outside it. - Forgetting to store. If the result is never put into the cache, the function stays correct but takes exponential time on arrays with many overlapping paths.
- Off-by-one in the loop. A maximum jump of
nums[i]reaches celli + nums[i]itself, so the condition is<=, not<.
Testing
[2, 3, 1, 1, 4]gives2.[0]gives0.[3, 1, 1, 1]gives1.[2, 0, 1, 1]gives2.[1, 1, 1, 1]gives3.