Start learning free

LESSON 273 OF 348 · MEMOIZATION

Jump Game in Kotlin: O(n^2) Iterative Dynamic Programming

Practice O(n2) - DP 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:

Convert the previous solution to an iterative one. Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 6
    Ctrl + Enter to check

    KOTLIN · MEMOIZATION

    Jump Game in Kotlin, explained

    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 function returns the minimum number of jumps needed to reach the last index.

    For [2, 3, 1, 1, 4] the answer is 2: one step from index 0 to index 1, then three steps from index 1 to the last index. The statement asks for an iterative solution in O(n^2) time and O(n) extra space, so this lesson turns the memoized recursion into loops.

    Approach: fill a table from right to left

    The recursive solution defines the answer for a cell in terms of the cells to its right: from cell i, a first jump lands on some cell j between i + 1 and i + nums[i], and the rest costs whatever cell j costs. The memoized version fills its cache on demand, in the order the recursion happens to visit cells.

    The iterative version fills a table in a fixed order, so no recursion is needed. Let dp[i] be the minimum number of jumps from cell i to the last cell. The last cell needs 0 jumps. Every other entry depends only on entries to its right, so if the loop runs from right to left, every entry it needs is already final when it is read. Then dp[i] is the minimum of 1 + dp[j] over all reachable cells j, and the answer is dp[0].

    The cost matches the memoized version: a table of n entries, each computed with a loop over at most n cells. What changes is that the call stack no longer grows with the input.

    On [2, 3, 1, 1, 4] the table fills as follows, starting from the right. dp[4] = 0. Cell 3 can reach cell 4, so dp[3] = 1. Cell 2 can reach cell 3, so dp[2] = 2. Cell 1 can reach cells 2, 3 and 4, and the best is 1 + dp[4] = 1. Cell 0 can reach cells 1 and 2, and the best is 1 + dp[1] = 2, so dp[0] = 2.

    Step by step

    1. Store the length in n and create dp, an IntArray of size n. Initialise every entry to n with a lambda. This is larger than any real answer (at most n - 1 jumps), so it acts as infinity until a real path is found.
    2. Set dp[n - 1] to 0. The last cell needs no jumps.
    3. Loop from n - 2 down to 0 with an index i. Going right to left guarantees that the cells to the right are final.
    4. Loop over the landing cells. Inside, start j at i + 1 and continue while j < n and j <= i + nums[i], increasing j at the end of the body.
    5. Improve dp[i]. A first jump from i to j costs 1 plus dp[j], so set dp[i] to the smaller of its current value and 1 + dp[j].
    6. Return dp[0] once both loops finish, since the answer starts at the first cell.

    The solution in Kotlin

    class Solution {
    fun jump(nums: IntArray): Int {
        val n = nums.size
        val dp = IntArray(n) { n }
        dp[n - 1] = 0
        for (i in n - 2 downTo 0) {
            var j = i + 1
            while (j < n && j <= i + nums[i]) {
                dp[i] = minOf(dp[i], 1 + dp[j])
                j++
            }
        }
        return dp[0]
    }
}

    The Kotlin details worth a closer look:

    • The initializer lambda. IntArray(n) { n } calls the lambda once per position to compute the starting value. This lambda ignores the index and always gives n. Without it, IntArray(n) would fill the array with zeros, which would look like "no jumps needed" for every cell.
    • downTo. n - 2 downTo 0 counts down and includes 0. A plain 0..n - 2 counts upwards and would read dp[j] before it is final. When n is 1, the range -1 downTo 0 is empty, so the loop body never runs.
    • minOf. This built-in function returns the smaller of its arguments, and the compiler picks the version for Int. It is the idiomatic replacement for Math.min.
    • Arrays are mutable. val dp fixes the reference, and dp[i] = ... changes an element. The array itself is not copied or reassigned.

    Complexity

    Time: O(n^2). The outer loop runs n - 1 times and the inner loop visits at most n - 1 cells for each one. In the worst case, such as every value being large, the total is about n^2 / 2 steps.

    Space: O(n). The only extra memory is the dp array. There is no recursion, so there is no call stack to grow with the input.

    Edge cases and common mistakes

    • One element. [7] returns 0: the loop does not run, and dp[0] is the last cell, already set to 0.
    • An empty array. dp[n - 1] would be dp[-1], which throws an ArrayIndexOutOfBoundsException. The lesson assumes at least one element.
    • Going left to right. Reading dp[j] before it is computed gives the placeholder n, and the result is wrong.
    • Initialising with 0. A zero-filled table lets minOf keep the 0 and return 0 for everything.
    • Unreachable end. For [1, 0, 5] the function returns 3, which is the infinity placeholder leaking through, not a count of jumps. The lesson assumes the last index is reachable.
    • Off-by-one at the reach. The farthest cell is i + nums[i], inclusive, so the condition is <=.

    Testing

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