Jump Game II

Medium
78.

Jump Game II

Jump Game II is a medium coding problem on arrays, dynamic programming and greedy, asked in Atlassian and PhonePe interviews.

You start at index 0 of array nums, where nums[i] is the maximum jump length from i. Return the minimum number of jumps to reach the last index. The tests guarantee you can always reach it.

Example 1

Input
nums = [2,3,1,1,4]
Output
2
Explanation
Index 0 → 1 → 4.

Example 2

Input
nums = [2,3,0,1,4]
Output
2

Constraints

  • 1 <= nums.length <= 30
  • 1 <= nums[i] <= 5
  • Reaching the last index is always possible.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var jump = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Jump Game II — Solution in Python, Java & C++

Jump Game II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Jump Game II is a medium coding problem on arrays, dynamic programming and greedy, asked in Atlassian and PhonePe interviews.

Problem statement

You start at index 0 of array nums, where nums[i] is the maximum jump length from i. Return the minimum number of jumps to reach the last index. The tests guarantee you can always reach it.

Example 1

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: Index 0 → 1 → 4.

Example 2

Input: nums = [2,3,0,1,4]
Output: 2

Constraints

  • 1 <= nums.length <= 30
  • 1 <= nums[i] <= 5
  • Reaching the last index is always possible.

Hints for Jump Game II

  1. Hint 1

    Think in BFS levels: everything reachable in j jumps forms a window.

  2. Hint 2

    When you walk past the current window's end, you must take another jump.

How to solve Jump Game II

Think of it as breadth-first search on a line. Everything you can reach in exactly one jump forms a contiguous window; everything reachable in two jumps forms the next window, and so on. You never need a queue — just track where the current window ends and how far the next one will stretch.

Approach

  1. Track jumps, curEnd (the last index of the current window) and farthest (the furthest index reachable from anything seen so far).
  2. Walk i from 0 up to but not including the last index.
  3. Update farthest = max(farthest, i + nums[i]).
  4. When i == curEnd, you have exhausted the current window: take a jump, and let the next window end at farthest.
  5. jumps is the minimum count when the walk finishes.

Why it works

This is BFS with the levels collapsed into indices. Reachability from a window is monotone — the union of what its members reach is itself a contiguous range ending at farthest — so a level is fully described by its endpoint. Since BFS visits nodes in non-decreasing distance, the level at which the last index first falls inside the window is its shortest jump count.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Stop the loop before the last index. Including it counts one jump too many when the last index happens to close a window.
  • Bump jumps when i reaches curEnd, not when i reaches farthest.
  • A single-element array needs 0 jumps, which falls out because the loop never runs.

Reference solution

Python

from typing import List

def jump(nums: List[int]) -> int:
    jumps = 0
    end = 0
    far = 0
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == end:
            jumps += 1
            end = far
    return jumps

Java

public static int jump(int[] nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i + 1 < nums.length; i++) {
        if (i + nums[i] > farthest) farthest = i + nums[i];
        if (i == curEnd) {
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}

C++

int jump(vector<int>& nums) {
    int jumps = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i + 1 < (int) nums.size(); i++) {
        if (i + nums[i] > farthest) farthest = i + nums[i];
        if (i == curEnd) {
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}

JavaScript

var jump = function(nums) {
    let jumps = 0, end = 0, far = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        far = Math.max(far, i + nums[i]);
        if (i === end) {
            jumps++;
            end = far;
        }
    }
    return jumps;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming