Start learning free

LESSON 264 OF 348 · BACKTRACKING

Jump Game in Kotlin: Minimum Jumps with Recursion

Practice O(2n) Read the full explanation

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
             Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 7
    Ctrl + Enter to check

    KOTLIN · BACKTRACKING

    Jump Game in Kotlin, explained

    Problem overview

    You stand on the first index of an IntArray named nums. The value nums[i] is the longest jump you can make from index i, and you may also jump any shorter distance, as long as it's at least 1. jump 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 to the last index. Starting with a 2-step jump to index 2 would need three jumps in total.

    Approach

    Ask the question from each cell: how many jumps does it take to reach the end starting here? Call that minJumps(nums, i). Then:

    • From the last cell the answer is 0, because we are already there.
    • From any other cell i, the first jump lands on some cell j between i + 1 and i + nums[i], and then we continue from j. That costs 1 + minJumps(nums, j). The best choice of j gives the answer.

    This is backtracking in its simplest form: try every first jump, solve the smaller problem that remains, and keep the smallest total. The main function just asks the question for cell 0.

    This lesson is the plain recursive version. It repeats work, because the same cell is reached through many different paths and its answer is computed again every time. Later solutions to this problem remove that repetition. Here the goal is to get the recursive idea right first.

    Step by step

    1. Use the helper. jump returns minJumps(nums, 0), because every journey starts at the first cell.
    2. Declare minJumps with the array and an index i, returning an Int.
    3. Base case. If i == nums.size - 1, return 0. Every recursive call moves to a larger index, so the calls always reach a stopping point.
    4. Start with a large result. var result = nums.size acts as infinity. Any real path needs at most nums.size - 1 jumps, so any real path beats it. If no cell is reachable from i, result stays this large, which marks a dead end.
    5. Loop over the possible landing cells. j starts at i + 1 and the loop runs while j < nums.size and j <= i + nums[i]. The first condition keeps us inside the array, the second respects the jump length.
    6. Try each jump. Update result with minOf(result, 1 + minJumps(nums, j)): one jump to j plus the best continuation from there.
    7. Return result once every first jump has been tried.

    The solution in Kotlin

    class Solution {
    fun minJumps(nums: IntArray, i: Int): Int {
        if (i == nums.size - 1) {
            return 0
        }
        var result = nums.size
        var j = i + 1
        while (j < nums.size && j <= i + nums[i]) {
            result = minOf(result, 1 + minJumps(nums, j))
            j++
        }
        return result
    }

    fun jump(nums: IntArray): Int {
        return minJumps(nums, 0)
    }
}

    Kotlin details:

    • minOf(a, b) is a standard function that returns the smaller of two values. It works for Int and other comparable types.
    • var for result and j. Both change during the loop. A val can't be reassigned, and the compiler would reject result = ....
    • while and &&. The second condition is checked only if the first is true. Because j < nums.size comes first, the code never reads outside the array in the loop condition itself.
    • Return in the base case. An Int function must return a value on every path, and here every path ends in a return.

    Following the example

    For [2, 3, 1, 1, 4], minJumps(nums, 0) may jump to index 1 or 2. From index 1 it can jump to index 2, 3 or 4, and the jump to index 4 is the last cell, which costs 1 + 0, so minJumps(nums, 1) is 1. Then the jump from index 0 to index 1 costs 1 + 1 = 2. The jump from index 0 to index 2 leads to index 3 and then index 4, which costs 3. The minimum is 2.

    Complexity

    The lesson states O(n²) time and O(n) space. The space part is right: the recursion goes at most n levels deep, since every call moves to a larger index. The time is a different matter for this version. It has no memory, so it recomputes the same cells again and again. On an array like [4, 3, 2, 1, 0], where every cell can reach every later cell, the number of calls doubles with each extra cell: 16 calls for 5 cells, 512 for 10, 16384 for 15, 524288 for 20 and 16777216 for 25. That is exponential, O(2ⁿ) in the worst case.

    On friendlier inputs it is fast. For an array of twenty 1s, each cell has only one choice and there are just 20 calls. The faster solutions to this problem keep the same recursive idea and avoid the repetition.

    Edge cases and common mistakes

    • A single cell. jump(intArrayOf(0)) is 0, because the start is already the last index.
    • Zeros. A cell holding 0 allows no jump, so its loop doesn't run and it returns nums.size. For [1, 0] the answer is 1, because the last cell is reachable from the first.
    • Unreachable end. For [3, 2, 1, 0, 4] the last cell can't be reached. The function returns 5, which is nums.size, the value that stands for infinity here, not a real jump count. Inputs where the end is always reachable don't hit this case.
    • Using < instead of <= in the loop. Then the longest jump nums[i] is never tried, and the answer for [2, 3, 1, 1, 4] becomes 3 instead of 2, because the 3-step jump from index 1 is lost.
    • Forgetting the array bound. Without j < nums.size, a large nums[i] sends j past the end and nums[j] throws ArrayIndexOutOfBoundsException.
    • Starting j at i. A jump of length 0 would recurse on the same cell forever.
    • Greedy shortcuts. Always taking the longest jump isn't correct: in [2, 3, 1, 1, 4] it picks index 2 and needs three jumps. Trying every option is what makes this version correct.

    Testing

    • [2, 3, 1, 1, 4] returns 2.
    • [0] returns 0.
    • [1, 1, 1, 1] returns 3.
    • [1, 0] returns 1.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free