LESSON 273 OF 348 · MEMOIZATION

Jump Game in TypeScript: O(n^2) Iterative 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

TYPESCRIPT · MEMOIZATION

Jump Game in TypeScript, explained

Problem overview

The method jump receives an array nums of non-negative integers. You start at index 0, and nums[i] is the longest jump allowed from index i: any distance from 1 to nums[i], forward only. The method 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 to index 1, then 3 steps to the last index. Index 0 can reach at most index 2, so one jump is never enough.

Approach: fill a table from right to left

The recursive memoized solution defines minJumps(i), the fewest jumps to reach the end from cell i, in terms of the answers for the cells to its right. This lesson turns that recursion into a loop, which is the usual step from memoization to dynamic programming.

Make an array dp where dp[i] holds that same answer. Two facts fill it in:

dp[n - 1] is 0, since the last cell needs no jumps;
for any other cell, dp[i] is the minimum of 1 + dp[j] over all cells j reachable in one jump, which are i + 1 up to i + nums[i].

Each entry depends only on entries to its right. So if the loop walks from right to left, every value it needs is already final when it is needed. No recursion is required, and the call stack no longer limits the array's size.

The time is still O(n^2), as the statement requires: n cells, each looking at up to n - 1 neighbours. The extra space is the dp array, O(n). A greedy scan can solve the problem in O(n) time, but this lesson practises the table.

Take [2, 3, 1, 1, 4] with n = 5. The table starts as [5, 5, 5, 5, 0]. Cell 3 reaches cell 4, so dp[3] = 1. Cell 2 reaches only cell 3, so dp[2] = 2. Cell 1 reaches cells 2, 3 and 4, and the best is 1 + dp[4] = 1, so dp[1] = 1. Cell 0 reaches cells 1 and 2, and the best is 1 + dp[1] = 2. The answer is dp[0] = 2.

Step by step

Store the length in a constant n and create dp with n slots, each filled with n. No route needs more than n - 1 jumps, so n works as "infinity": any real path will beat it.
Set dp[n - 1] to 0. This is the base case.
Loop i from n - 2 down to 0. Going right to left guarantees that the cells to the right of i are final.
Loop over the reachable cells. j starts at i + 1 and runs while j < n and j <= i + nums[i]: the first condition keeps it inside the array, the second respects the jump length.
Relax the entry. A first jump from i to j costs one jump plus dp[j], so set dp[i] to Math.min(dp[i], 1 + dp[j]).
Return dp[0], the answer when starting at the first cell.

The solution in TypeScript

class Solution {
    jump(nums: number[]): number {
        const n = nums.length;
        let dp = new Array(n).fill(n);
        dp[n - 1] = 0;
        for (let i = n - 2; i >= 0; --i) {
            for (let j = i + 1; j < n && j <= i + nums[i]; ++j) {
                dp[i] = Math.min(dp[i], 1 + dp[j]);
            }
        }
        return dp[0];
    }
}

Details worth a closer look:

new Array(n).fill(n). new Array(n) creates an array of length n with empty slots, not zeros, and fill(n) sets every slot to n and returns the array. Without fill, 1 + dp[j] would be NaN, because an empty slot reads as undefined.
The element type. Called with a number, new Array(n) gives an any[], so dp is not checked for element types. Writing const dp: number[] = new Array(n).fill(n) would give the compiler more to check. The types are erased in the compiled JavaScript either way.
Counting down. i is a plain number, so --i and the test i >= 0 are safe. There is no unsigned wrap-around as in some other languages.
Both bounds on j. Without j < n, a large nums[i] would send the loop past the array, and the extra cells would read as undefined.
Numbers are doubles. The counts are small whole numbers, so there is no overflow to worry about.

Complexity

Time: O(n^2). The outer loop runs n - 1 times and the inner loop up to n - 1 times, and each step does constant work. The same bound held for the memoized version, but here there are no recursive calls or cache lookups.

Space: O(n). The dp array has n entries. The loops use only a few extra variables, and there is no recursion. In a quick check, an array of 20,000 ones ran fine and returned 19999.

Edge cases and common mistakes

One element. [0] gives 0: dp[0] is the base case, and the outer loop starts at -1 and doesn't run.
Empty array. The method returns undefined, because dp[0] doesn't exist. The lesson doesn't test an empty array, but a caller who passes one should expect that.
Unreachable end. The lesson assumes the end can be reached. For [1, 0, 1] the stand-in n spreads through the table, and the method returns 3, not a real jump count.
Wrong direction. Looping i from left to right would read entries still holding n, and the answers would be wrong.
Forgetting the base case. If dp[n - 1] stayed at n, every answer would be at least n + 1 before the minimum, which never beats the stand-in.
Using 0 as the initial value. The minimum would stay at 0 forever. The table needs a value larger than any real answer.
Large first jump. [5, 1, 1, 1, 1, 1] gives 1, because cell 0 reaches the last cell directly.

Testing

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

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

Start learning free