Start learning free

LESSON 272 OF 348 · MEMOIZATION

Jump Game in TypeScript: O(n^2) with Memoization

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

Apply memoization to the previous soltuion. Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 10
    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 you can make from index i: you may jump any distance from 1 up 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 from index 0 to index 1, then 3 steps from index 1 to the last index. No single jump reaches the end, since nums[0] is only 2.

    Approach: recursion plus a cache

    Define minJumps(i) as the minimum number of jumps to reach the last index when starting from index i. Then:

    • if i is the last index, the answer is 0;
    • otherwise, try every cell j you can reach in one jump, that is, i + 1 up to i + nums[i] (without leaving the array), and take the best of 1 + minJumps(j).

    Without any caching, the recursion reaches the same cell through many different paths and recomputes its answer every time. With a large array of 1s and big values, the number of calls grows exponentially.

    The fix is memoization: the answer for a cell depends only on the cell, so store it the first time it is computed. Every cell gets computed once, and each computation loops over at most n reachable cells. That gives O(n^2) time, the budget the statement sets. A greedy approach can get this down to O(n), but this lesson is about turning plain recursion into memoized recursion.

    Step by step

    1. Create the cache in jump: an empty object typed { [key: number]: number }, an index signature that maps a cell index to its answer once known.
    2. Call the helper first and write it afterwards: jump returns this.minJumps(nums, 0, cache), since the answer starts from cell 0. Methods of a class call each other through this.
    3. Declare minJumps with nums: number[], i: number and the cache, returning a number. The cache is passed through every recursive call, so they all share the same stored answers.
    4. Base case. When i is nums.length - 1, you are already on the last cell, so return 0. Every recursive call moves to a larger index, so every chain of calls ends here or runs out of reachable cells.
    5. Cache hit. If i in cache, return cache[i] at once. This check is what makes memoization pay off.
    6. Start result at nums.length. No path needs that many jumps (at most nums.length - 1), so it acts as infinity, and any real path will beat it.
    7. Loop over the reachable cells. j starts at i + 1 and runs while j < nums.length and j <= i + nums[i]. The first condition keeps the loop inside the array, the second respects the jump length.
    8. Try each first jump. Going from i to j costs 1 jump plus the best from j, so update result with Math.min(result, 1 + this.minJumps(nums, j, cache)).
    9. Save the answer with cache[i] = result before returning, so this cell is never computed again.
    10. Return result.

    The solution in TypeScript

    class Solution {
    minJumps(nums: number[], i: number, cache: { [key: number]: number }): number {
        if (i === nums.length - 1) {
            return 0;
        }
        if (i in cache) {
            return cache[i];
        }
        let result = nums.length;
        for (let j = i + 1; j < nums.length && j <= i + nums[i]; ++j) {
            result = Math.min(result, 1 + this.minJumps(nums, j, cache));
        }
        cache[i] = result;
        return result;
    }

    jump(nums: number[]): number {
        let cache: { [key: number]: number } = {};
        return this.minJumps(nums, 0, cache);
    }
}

    Details worth a closer look:

    • The cache is a plain object. Its number keys are turned into strings by JavaScript, which doesn't matter here. The annotation describes the shape for the compiler and is erased when the code is compiled.
    • in asks about the key. i in cache is true when an entry for i exists, whatever value it holds. That is the right question for a cache: it separates "not computed yet" from "computed", without relying on the stored value being truthy.
    • Objects are passed by reference. The helper changes the same cache object that jump created, which is how the answers are shared between calls.
    • let versus const. The lesson declares cache with let. The variable is never reassigned, so const would work equally well; the object's contents change either way.
    • Chained condition. In j < nums.length && j <= i + nums[i], the check against the array length comes first, so the loop never uses an index outside the array.

    Complexity

    Time: O(n^2). There are n cells. The body of minJumps for one cell runs once, because later calls for that cell return from the cache, and its loop visits at most n - 1 cells. The calls that hit the cache cost O(1) each, and there are at most n of them per computed cell.

    Space: O(n). The cache holds at most one entry per cell, and the recursion goes at most n calls deep, because every call moves to a larger index. For very long arrays, a deep recursion can exhaust the call stack. In a quick check an array of 5,000 ones ran fine.

    Edge cases and common mistakes

    • One element. [0] starts on the last index, so the answer is 0.
    • Zeros in the middle. [2, 3, 0, 1, 4] returns 2: the zero is simply never worth jumping onto.
    • Large first value. [5, 1, 1, 1, 1, 1] returns 1, because the first jump already reaches the end. The loop stops at the array's end instead of running to i + 5.
    • Unreachable end. The lesson assumes the last index can be reached. If it can't, as in [1, 0, 1], the stand-in value nums.length flows through the calculation and the method returns 3 rather than a real jump count.
    • Forgetting to store the result. Without cache[i] = result, the code is correct but exponentially slow.
    • Not passing the cache. If the recursive call omitted cache, nothing would be shared and the memoization would do nothing.
    • Dropping the length check. Using only j <= i + nums[i] would read nums[j] beyond the array for large values.

    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