LESSON 356 OF 415 · GREEDY

Jump Game in Swift: Minimum Jumps with a Greedy Linear Scan

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

SWIFT · GREEDY

Jump Game in Swift, explained

Problem overview

The method jump receives nums, an array of non-negative integers. You start on index 0. The value at each index is the farthest you can jump forward from there, and you may also jump any shorter distance. The goal is the minimum number of jumps needed to reach the last index.

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. The lesson's tests only give arrays where the last index can be reached.

Approach: jump only when you must

A brute-force search tries every possible jump from every position, which grows exponentially. A dynamic-programming table that stores the best jump count for every index brings it to O(n²). The greedy idea gets it to O(n) in a single pass.

Think of the jumps as layers. With k jumps you can reach every index up to some boundary. All the indices past that boundary, up to the next one, need exactly k + 1 jumps. To know the next boundary, you only need the farthest point reachable from any index inside the current layer.

The solution tracks two numbers:

curMax: the farthest index reachable with the jumps counted so far.
nextMax: the farthest index reachable with one more jump, starting from any index seen so far.

Scan the indices from left to right. When the scan reaches an index beyond curMax, the jumps so far can't get there, so one more jump is needed. That jump starts from whichever earlier index reaches farthest, which is exactly what nextMax remembers, so curMax becomes nextMax.

On [2, 3, 1, 1, 4]: the first jump covers up to index 2 (curMax = 2). Index 1 offers a reach of 1 + 3 = 4, so nextMax becomes 4. Index 2 is within reach. At index 3, curMax is 2, so a second jump is counted and curMax becomes 4. Index 4 is within reach, and the result is 2.

Step by step

Handle the trivial case. With zero or one element you are already on the last index, so return 0.
Start result at 1. With at least two elements you need at least one jump, and it is counted from the start.
Set curMax to nums[0]. The first jump can take you that far.
Set nextMax to nums[0] as well. Index 0 is the only index seen so far, and it is the only starting point for the next jump.
Loop over indices 1 up to the end. The range 1..<nums.count skips the first element and stops before nums.count. Each index is visited once.
Check whether the index is out of reach. If curMax < i, add one jump and move curMax forward to nextMax.
Update nextMax for every index with max(nextMax, i + nums[i]). This includes the index that just caused a jump, because the next jump may start there.
Return result.

The solution in Swift

class Solution {
    func jump(_ nums: [Int]) -> Int {
        if nums.count <= 1 {
            return 0
        }
        var result = 1
        var curMax = nums[0]
        var nextMax = nums[0]
        for i in 1..<nums.count {
            if curMax < i {
                result += 1
                curMax = nextMax
            }
            nextMax = max(nextMax, i + nums[i])
        }
        return result
    }
}

The Swift details worth a closer look:

The guard against short arrays matters. The range 1..<nums.count is fine for a single element, because 1..<1 is an empty range. For an empty array, nums[0] would crash the program, and so would the range 1..<0, since Swift rejects a range whose upper bound is below its lower bound. The early return 0 avoids both.
Half-open ranges. 1..<n excludes n, so i stays a valid index. The closed range 1...n would run one step too far.
Overflow traps. i + nums[i] is ordinary Int addition, which is 64-bit. Swift stops the program if an addition overflows, but with realistic array values this can't happen.
var for values that change. result, curMax and nextMax are all reassigned inside the loop. A let would not compile.
The loop variable is a constant. i is a new constant on each pass and can't be modified inside the body.

Complexity

Time: O(n). The loop touches each index once and does a constant amount of work each time.

Space: O(1). The solution keeps three integers and never builds a table.

Edge cases and common mistakes

Single element. [0] returns 0, because you already stand on the last index.
Two elements. [1, 2] returns 1: the first jump covers index 1 and no second jump is counted.
One big first jump. [5, 1, 1] returns 1, since index 0 already reaches the end.
All ones. [1, 1, 1, 1] returns 3, one jump per step.
Zeros in the middle. [2, 3, 0, 1, 4] returns 2: the zero is jumped over, never landed on.
Unreachable ends. For input like [0, 1] the solution returns 2, which is not meaningful, because the last index can't be reached at all. The solution doesn't detect this, and the lesson's tests don't include such arrays.
Updating nextMax only inside the if. Every index must feed nextMax, otherwise a far-reaching stone in the middle of a layer is ignored.
Counting a jump when curMax == i. The condition is strictly curMax < i. An index exactly at the boundary is still reachable.

Testing

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

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

Start learning free