Jump Game II

Leetcode Problem 45: Jump Game II

Problem Summary

You are positioned at the first index of a zero-indexed integer array. Each element nums[i] represents the maximum length of a forward jump from index i, meaning you can jump to any index from i + 1 to i + nums[i]. Return the minimum number of jumps needed to reach the last index. It is guaranteed that the last index is always reachable.

The array length is at most 10,000 and each element is a non-negative integer up to 1,000.

Techniques

• Array
• Dynamic Programming
• Greedy

Solution

function jump(nums: number[]): number {
    let jumps = 0
    let currentEnd = 0
    let furthest = 0

    for (let i = 0; i < nums.length - 1; i++) {
        furthest = Math.max(furthest, i + nums[i])

        if (i === currentEnd) {
            jumps++
            currentEnd = furthest
        }
    }

    return jumps
}