LESSON 298 OF 415 · MEMOIZATION

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

Practice O(n²) - 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

Guided

Ctrl + Enter to check

SWIFT · MEMOIZATION

Jump Game in Swift, explained

Problem overview

The method jump(_ nums: [Int]) -> Int gets an array of non-negative integers. You begin at index 0, and each nums[i] is the longest jump you may make forward from index i. The method returns the fewest jumps needed to land on the last index.

For [2, 3, 1, 1, 4] the answer is 2: jump one step to index 1 (which holds 3), then three steps to index 4. The lesson asks for an iterative solution with O(n^2) time and O(n) extra space, which is the memoized recursion turned into loops.

Approach: fill a table from right to left

The recursive solution computes minJumps(i), the fewest jumps from index i to the end, and caches it. That function depends only on indices to the right of i. So instead of recursing and remembering, you can fill an array dp in an order that guarantees those indices are already finished: start at the right end and move left.

Here dp[i] holds the fewest jumps from i to the last index. The last index needs no jumps, so dp[n - 1] = 0. For any earlier index, a first jump lands on some j between i + 1 and i + nums[i] and costs 1 + dp[j] in total. The answer for i is the smallest of these. The result is dp[0].

On [2, 3, 1, 1, 4]: dp[4] = 0. Index 3 (value 1) can reach only index 4, so dp[3] = 1. Index 2 (value 1) reaches only index 3, so dp[2] = 2. Index 1 (value 3) reaches indices 2, 3 and 4, and the best is 1 + dp[4] = 1. Index 0 (value 2) reaches indices 1 and 2: 1 + dp[1] = 2 beats 1 + dp[2] = 3. So dp[0] = 2.

The two versions do the same work in the same order of magnitude: the same n answers, each from a loop over its landing cells. The recursive one finds the order of evaluation by itself, as the calls unfold, while the iterative one fixes the order in advance. Choosing the order yourself removes the recursion, the dictionary and the lookups, and a plain array replaces them.

Step by step

Record the length in let n = nums.count, and create var dp = [Int](repeating: n, count: n). The value n is bigger than any real answer (at most n - 1 jumps), so it stands for "no route found yet".
Set dp[n - 1] = 0. The last cell is the goal.
Walk the indices backwards. A var i starts at n - 2, the loop runs while i >= 0, and the body ends with i -= 1. Every dp[i] only uses cells to its right, which are final by then.
Visit the reachable cells. Inside, a var j starts at i + 1 and an inner while runs while j < n and j <= i + nums[i], finishing each pass with j += 1.
Update the table: dp[i] = min(dp[i], 1 + dp[j]).
Return dp[0] after both loops.

The solution in Swift

class Solution {
    func jump(_ nums: [Int]) -> Int {
        let n = nums.count
        var dp = [Int](repeating: n, count: n)
        dp[n - 1] = 0
        var i = n - 2
        while i >= 0 {
            var j = i + 1
            while j < n && j <= i + nums[i] {
                dp[i] = min(dp[i], 1 + dp[j])
                j += 1
            }
            i -= 1
        }
        return dp[0]
    }
}

Swift details worth a closer look:

[Int](repeating:count:). This initializer builds an array holding count copies of one value. The statement dp[i] = ... changes the array in place, which is why dp is a var while n is a let.
while instead of for. Swift has no C-style for (i = n - 2; i >= 0; i--) loop. You can count down with stride(from: n - 2, through: 0, by: -1), or use a while loop like this one. A range such as 0...(n - 2) can only count up, and when n is 1 it would be the invalid range 0...(-1), which crashes.
The loop condition does the bounds check. j < n && j <= i + nums[i] stops at the end of the array or at the farthest jump, whichever comes first. Swift's && skips the right side when the left is false, but both sides here are safe to evaluate anyway.
Arithmetic can't wrap silently. Int is 64 bits and overflow stops the program. The values here (indices and small counts) stay far from that limit.

Complexity

Time: O(n^2). The outer loop visits each index once, and the inner loop visits up to n - 1 landing cells, so the total is at most about n^2 / 2 steps.

Space: O(n). The dp array has n entries and nothing else grows. There is no recursion, so deep inputs can't exhaust the call stack, which is the main practical gain over the memoized version.

Edge cases and common mistakes

One element. For [5], dp[0] is the goal cell itself. The outer loop starts at n - 2 = -1 and doesn't run, so the method returns 0.
Wrong direction. Filling from left to right reads entries of dp that haven't been computed yet and still hold n.
Starting dp at 0. With zeros, min would always pick 0 and every answer would be wrong. The initial value must be larger than any real answer.
A blocked path. If a 0 cuts off every route, dp[0] stays at n. For [0, 1] the method returns 2. The lesson's tests only use arrays whose last index can be reached.
Index out of range. Without the j < n test, a big nums[i] would send j past the array and crash on dp[j].
Forgetting i -= 1. The loop would never finish.

Testing

[2, 3, 1, 1, 4] gives 2.
[1, 1, 1, 1] gives 3.
[2, 3, 0, 1, 4] gives 2.
[5, 1, 1, 1, 1, 1] gives 1.
[5] 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