LESSON 331 OF 348 · GREEDY

Jump Game in TypeScript: Minimum Jumps with a Greedy 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

TYPESCRIPT · GREEDY

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 farthest you can jump forward from index i: any jump of 1 up to nums[i] steps is allowed. The method returns the minimum number of jumps needed to reach the last index.

For nums = [2, 3, 1, 1, 4] the answer is 2. From index 0 you can reach index 1 or 2. Jump to index 1, whose value is 3, and from there the last index (4) is exactly three steps away. One jump can't do it, because index 0 reaches no farther than index 2.

An array with one element, or none, needs no jumps: you are already on the last index.

Approach: jump only when you must

A brute-force solution tries every possible jump from every position, which blows up quickly. A dynamic-programming version stores, for each index, the fewest jumps to get there, and costs O(n²) if it looks at every earlier index. The greedy idea is faster and needs no table.

Think of the jumps as waves. With k jumps you can reach some farthest index. Every index up to that point is reachable with k jumps or fewer. Only when the scan passes that frontier do you need jump number k + 1, and the best place to take it from is whichever stone seen so far reaches farthest. So the scan keeps 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 stone already visited.

Walk through [2, 3, 1, 1, 4]. The first jump is counted at the start, so result is 1 and both maxima are 2. Then, for each i, after the check and the update:

i	result	curMax	nextMax
1	1	2	4
2	1	2	4
3	2	4	4
4	2	4	8

At i = 3 the frontier curMax = 2 is behind the index, so a second jump is counted and the frontier moves to 4, which was set up by index 1 (1 + 3). The last value of nextMax, 8, is meaningless once the end is reached; only result matters.

Step by step

Handle the trivial case. With at most one element there is nothing to jump to, so return 0 before reading nums[0].
Start result at 1. With two or more elements at least one jump is needed, and counting it now lets curMax start as that jump's reach.
Set curMax to nums[0]. The first jump can land anywhere up to that index.
Set nextMax to nums[0] as well. At this point the only stone seen is index 0, so the best reach for one more jump is the same value.
Loop from index 1 to the end. Each stone is visited once.
Check curMax < i. If the stone is beyond the current reach, the jumps counted so far can't get here. Count another jump and move the frontier to nextMax.
Update nextMax with Math.max(nextMax, i + nums[i]). This runs for every stone, including one that just caused a jump, because it can start the jump after that.
Return result.

The solution in TypeScript

class Solution {
    jump(nums: number[]): number {
        if (nums.length <= 1) {
            return 0;
        }
        let result = 1;
        let curMax = nums[0];
        let nextMax = nums[0];
        for (let i = 1; i < nums.length; ++i) {
            if (curMax < i) {
                ++result;
                curMax = nextMax;
            }
            nextMax = Math.max(nextMax, i + nums[i]);
        }
        return result;
    }
}

Some details worth noticing:

Types. nums: number[] and the number return type are annotations for the compiler. They are removed when TypeScript compiles to JavaScript. The variables result, curMax and nextMax need no annotation, since TypeScript infers number from the starting values.
let, not const. All three counters change during the loop, so they must be declared with let.
++result. The prefix and postfix forms do the same thing here, because the value of the expression is not used.
number arithmetic. i + nums[i] is a plain addition of doubles. Array sizes are far below 2^53, so there is no overflow to worry about.
Reading past the end. The loop stops at nums.length, so nums[i] is always a real element. Reading outside a JavaScript array would give undefined and turn the sums into NaN.

Complexity

Time: O(n). One pass over the array, with constant work per element.

Space: O(1). Three numbers and the loop index, regardless of the input size.

Edge cases and common mistakes

One element. [0] and [5] both return 0. Without the early return, result would start at 1 and be wrong.
Two elements. [1, 0] returns 1: the first jump is counted up front and the loop never needs another.
All ones. [1, 1, 1, 1] returns 3, since every jump moves one step.
A big first jump. [5, 1, 1] returns 1.
Updating nextMax inside the if. The stone that triggers a jump would then not count towards the next reach, and the answer can come out too large.
Counting a jump at every stone. Jumps happen when the frontier is crossed, not at each index. The answer for [3, 1, 1, 1, 1] is 2, not 4.
Unreachable ends. The method assumes the last index can be reached. For something like [1, 0, 5] the scan still produces a number, but it isn't a count of real jumps.

Testing

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