LESSON 331 OF 348 · GREEDY

Jump Game in Kotlin: Greedy Minimum Jumps in O(n)

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.

STEP 1 OF 8

Guided

Ctrl + Enter to check

Jump Game in Kotlin, explained

Problem overview

The function jump receives an IntArray named nums of non-negative integers. You start on index 0, and each value is the maximum jump length from that index: nums[i] = 3 lets you land on any of the next three indices, or on any nearer one. The function returns the minimum number of jumps needed to reach the last index.

For nums = [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. A single jump from index 0 can't do it, because it reaches index 2 at best.

Approach: widen the reach only when you must

A brute-force search tries every jump length from every index, which grows exponentially, and dynamic programming over the indices still costs O(n²). The greedy idea needs a single pass.

Think of the jumps as layers. With k jumps you can reach every index up to some boundary. Each index inside that boundary offers a further reach of i + nums[i]. The best boundary for k + 1 jumps is the largest of those values. You never have to decide which index to jump from in advance: you only need the farthest reach seen so far, and you spend a new jump at the moment you meet an index that the current boundary doesn't cover.

The solution keeps two numbers: curMax, the farthest index reachable with the jumps counted so far, and nextMax, the farthest index reachable with one more jump from any index seen so far. This lesson solves the version where every index can be reached, so the answer is always found by one scan.

On [2, 3, 1, 1, 4]: the first jump is counted right away, so result = 1 and curMax = nextMax = 2. Index 1 is covered, and it raises nextMax to 4. Index 2 is covered and changes nothing. Index 3 is beyond curMax, so a second jump is needed: result becomes 2 and curMax becomes 4. Index 4 is covered. The answer is 2.

Step by step

Handle the trivial case. With zero or one element you are already on the last index, so no jump is needed and the function returns 0.
Start the jump counter at 1. With at least two indices, at least one jump is required, and the first one is counted immediately.
Set curMax to nums[0]. That is how far the first jump can go.
Set nextMax to nums[0] too. It is the best reach for one more jump among the indices seen so far, and so far only index 0 has been seen.
Loop from index 1 up to the last index. Index 0 was handled by the initial values.
Add a jump when the index is out of reach. If curMax < i, the counted jumps don't cover index i. Increment result and move the boundary to nextMax, the farthest reach found so far.
Update nextMax with the current index. Do this for every index, including the one that just triggered a jump, because it may start the next jump.
Return result.

The solution in Kotlin

class Solution {
    fun jump(nums: IntArray): Int {
        if (nums.size <= 1) {
            return 0
        }
        var result = 1
        var curMax = nums[0]
        var nextMax = nums[0]
        for (i in 1 until nums.size) {
            if (curMax < i) {
                result++
                curMax = nextMax
            }
            nextMax = maxOf(nextMax, i + nums[i])
        }
        return result
    }
}

The Kotlin details worth a closer look:

1 until nums.size is a range that excludes its end, so it visits indices 1 to nums.size - 1. Writing 1..nums.size would include nums.size and throw ArrayIndexOutOfBoundsException on nums[i].
var versus val. result, curMax and nextMax change during the loop, so they are var. A val can't be reassigned, and the compiler rejects the attempt.
maxOf(a, b) is a standard-library function that returns the larger of two values. It works for Int without any import.
result++ is a statement here. It increases the variable by one, and it is the same as result = result + 1.
Int is 32 bits. i + nums[i] could wrap around for values near two billion. Realistic inputs for this lesson are far from that limit.
Early return. The function body is a block with explicit return statements, so every path must end in one, and the final line returns result.

Complexity

Time: O(n). The loop visits each index once and does constant work for each one: a comparison, maybe an increment, and one maxOf.

Space: O(1). The function stores three integers and the loop index, whatever the size of the array.

Edge cases and common mistakes

One element or none. [5] and an empty array both return 0, thanks to the first check. Without it, nums[0] would fail on an empty array.
Starting the counter at 0. The count starts at 1 because the first jump is counted up front. With two or more elements, zero jumps is never right.
A huge first value. [10, 1, 1] returns 1: the first jump already covers every index.
Updating nextMax only inside the if. Every index must contribute its reach, or the boundary would not grow.
Jumping to the farthest index. The jump doesn't actually land on the farthest index. The algorithm only tracks how far the best choice would reach, and counts a jump when it is forced.
Unreachable ends. The lesson assumes the last index can be reached. An array such as [0, 1] has no solution, and this code doesn't detect that.

Testing

[2, 3, 1, 1, 4] gives 2.
[2, 3, 0, 1, 4] gives 2.
[1, 1, 1, 1] gives 3.
[1, 2, 1, 1, 1] gives 3.
[1, 2] gives 1.
[5] gives 0.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free