Jump Game II (Minimum Jumps)

🎯

Jump Game II (Minimum Jumps)

mediumGREEDYAmazonGoogle

Imagine you are trying to cross a series of stepping stones across a river, but each stone lets you jump only a limited distance forward. How do you minimize the number of jumps to reach the other side?

💡 This problem asks for the minimum number of jumps to reach the end of an array where each element indicates the maximum jump length from that position. Beginners often struggle because a naive approach tries all jump combinations, leading to exponential time, and they miss the greedy insight that lets us jump optimally by tracking the furthest reachable index.

📋

Problem Statement

Given an array of non-negative integers nums, where each element represents your maximum jump length at that position, return the minimum number of jumps required to reach the last index. You can assume that you can always reach the last index.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^5It is guaranteed that you can reach the last index.

💡

Example

Input"[2,3,1,1,4]"

Output2

Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input"[2,3,0,1,4]"

Output2

Jump from index 0 to 1, then directly to the last index.

• Single element array [0] → 0 jumps needed
• Array with all ones [1,1,1,1] → n-1 jumps needed
• Array with a large jump at start [10,1,1,1] → 1 jump needed
• Array where last jump is exactly 1 [1,2,3,4,1] → minimal jumps calculated correctly

⚠️

Common Mistakes

Not stopping iteration before last index in greedy approach

Extra unnecessary jumps counted or index out of range errors

✅ Iterate only up to len(nums) - 2 in the greedy loop

Forgetting to update current_end after incrementing jumps

Infinite loop or incorrect jump count

✅ Always update current_end to furthest after incrementing jumps

Using BFS without visited set

Repeated processing of same indices, leading to TLE

✅ Maintain a visited set or array to avoid revisiting indices

Trying to jump beyond array bounds without min check

Index out of range runtime errors

✅ Use min(pos + nums[pos], len(nums) - 1) to limit jump range

🧠

Brute Force (Pure Recursion)

💡 This approach exists to build intuition by exploring all possible jump paths recursively. It helps understand the problem's exponential nature and why optimization is necessary.

Intuition

From each position, try every possible jump length and recursively find the minimum jumps to the end. The minimum among all these paths is the answer.

Algorithm

1. Start at index 0.
2. If at the last index, return 0 jumps needed.
3. For each jump length from 1 to nums[current], recursively compute jumps needed from the new position.
4. Return 1 plus the minimum jumps from all recursive calls.

💡 The recursion tree grows exponentially because from each position, multiple jumps are possible, making it hard to track without optimization.

</>

Code

def jump(nums):
    def dfs(pos):
        if pos >= len(nums) - 1:
            return 0
        min_jumps = float('inf')
        furthest_jump = min(pos + nums[pos], len(nums) - 1)
        for next_pos in range(pos + 1, furthest_jump + 1):
            jumps = dfs(next_pos)
            if jumps != float('inf'):
                min_jumps = min(min_jumps, jumps + 1)
        return min_jumps
    return dfs(0)

# Example usage
if __name__ == '__main__':
    print(jump([2,3,1,1,4]))  # Output: 2

Line Notes

def dfs(pos):Defines a recursive helper to compute min jumps from position pos

if pos >= len(nums) - 1:Base case: if at or beyond last index, no more jumps needed

for next_pos in range(pos + 1, furthest_jump + 1):Try all possible jumps from current position

min_jumps = min(min_jumps, jumps + 1)Update minimum jumps including current jump

public class Solution {
    public int jump(int[] nums) {
        return dfs(nums, 0);
    }
    private int dfs(int[] nums, int pos) {
        if (pos >= nums.length - 1) return 0;
        int minJumps = Integer.MAX_VALUE;
        int furthestJump = Math.min(pos + nums[pos], nums.length - 1);
        for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            int jumps = dfs(nums, nextPos);
            if (jumps != Integer.MAX_VALUE) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }
        return minJumps;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.jump(new int[]{2,3,1,1,4})); // Output: 2
    }
}

Line Notes

public int jump(int[] nums)Entry point calling recursive dfs from index 0

if (pos >= nums.length - 1) return 0;Base case: no jumps needed if at or beyond last index

for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++)Try all jumps from current position

minJumps = Math.min(minJumps, jumps + 1);Update minimum jumps including current jump

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int dfs(const vector<int>& nums, int pos) {
    if (pos >= (int)nums.size() - 1) return 0;
    int minJumps = INT_MAX;
    int furthestJump = min(pos + nums[pos], (int)nums.size() - 1);
    for (int nextPos = pos + 1; nextPos <= furthestJump; ++nextPos) {
        int jumps = dfs(nums, nextPos);
        if (jumps != INT_MAX) {
            minJumps = min(minJumps, jumps + 1);
        }
    }
    return minJumps;
}

int jump(vector<int>& nums) {
    return dfs(nums, 0);
}

int main() {
    vector<int> nums = {2,3,1,1,4};
    cout << jump(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int dfs(const vector<int>& nums, int pos)Recursive helper to find min jumps from pos

if (pos >= (int)nums.size() - 1) return 0;Base case: no jumps needed if at or beyond last index

for (int nextPos = pos + 1; nextPos <= furthestJump; ++nextPos)Try all possible jumps from current position

minJumps = min(minJumps, jumps + 1);Update minimum jumps including current jump

function jump(nums) {
    function dfs(pos) {
        if (pos >= nums.length - 1) return 0;
        let minJumps = Infinity;
        let furthestJump = Math.min(pos + nums[pos], nums.length - 1);
        for (let nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
            let jumps = dfs(nextPos);
            if (jumps !== Infinity) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }
        return minJumps;
    }
    return dfs(0);
}

// Example usage
console.log(jump([2,3,1,1,4])); // Output: 2

Line Notes

function dfs(pos) {Recursive helper to compute min jumps from pos

if (pos >= nums.length - 1) return 0;Base case: no jumps needed if at or beyond last index

for (let nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {Try all jumps from current position

minJumps = Math.min(minJumps, jumps + 1);Update minimum jumps including current jump

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

At each index, we try all possible jumps leading to an exponential number of recursive calls.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem's nature and motivate better solutions.

🧠

Greedy Approach (Tracking Furthest Reach and Current End)

💡 This approach uses a greedy strategy to jump as far as possible within the current jump range, minimizing total jumps. It is efficient and intuitive once you understand the problem's structure.

Intuition

At each step, track the furthest index reachable within the current jump. When you reach the end of the current jump range, increase the jump count and update the range to the furthest reachable index.

Algorithm

1. Initialize jumps to 0, current_end to 0, and furthest to 0.
2. Iterate through the array up to the second last element.
3. Update furthest to the maximum reachable index from current position.
4. If current index reaches current_end, increment jumps and update current_end to furthest.
5. Return jumps after iteration.

💡 The key insight is to jump only when you have to, i.e., when you reach the end of the current jump range.

</>

Code

def jump(nums):
    jumps = 0
    current_end = 0
    furthest = 0
    for i in range(len(nums) - 1):
        furthest = max(furthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = furthest
    return jumps

# Example usage
if __name__ == '__main__':
    print(jump([2,3,1,1,4]))  # Output: 2

Line Notes

jumps = 0Initialize jump count to zero

for i in range(len(nums) - 1):Iterate through array except last index because no jump needed from last

furthest = max(furthest, i + nums[i])Update furthest reachable index from current position

if i == current_end:When we reach the end of current jump range, we must jump

public class Solution {
    public int jump(int[] nums) {
        int jumps = 0, currentEnd = 0, furthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            furthest = Math.max(furthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = furthest;
            }
        }
        return jumps;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.jump(new int[]{2,3,1,1,4})); // Output: 2
    }
}

Line Notes

int jumps = 0, currentEnd = 0, furthest = 0;Initialize counters and pointers

for (int i = 0; i < nums.length - 1; i++) {Iterate through array except last index

furthest = Math.max(furthest, i + nums[i]);Track furthest reachable index

if (i == currentEnd) {When current index reaches end of current jump range, increment jumps

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

int main() {
    vector<int> nums = {2,3,1,1,4};
    cout << jump(nums) << endl; // Output: 2
    return 0;
}

Line Notes

int jumps = 0, currentEnd = 0, furthest = 0;Initialize jump count and pointers

for (int i = 0; i < (int)nums.size() - 1; ++i)Iterate through array except last index

furthest = max(furthest, i + nums[i]);Update furthest reachable index

if (i == currentEnd)When current index reaches current jump boundary, increment jumps

function jump(nums) {
    let jumps = 0, currentEnd = 0, 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;
}

// Example usage
console.log(jump([2,3,1,1,4])); // Output: 2

Line Notes

let jumps = 0, currentEnd = 0, furthest = 0;Initialize counters and pointers

for (let i = 0; i < nums.length - 1; i++) {Iterate through array except last index

furthest = Math.max(furthest, i + nums[i]);Track furthest reachable index

if (i === currentEnd) {When current index reaches end of current jump range, increment jumps

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass through the array with constant extra space.

💡 For n=10^5, this means 100,000 operations, which is efficient and fast.

Interview Verdict: Accepted

This is the optimal and most commonly accepted solution in interviews.

🧠

BFS Level Order Traversal (Queue Based)

💡 This approach models the problem as a graph traversal where each index is a node and edges represent jumps. BFS finds the shortest path (minimum jumps) to the last index.

Intuition

Use a queue to explore all reachable indices at the current jump level before moving to the next jump level, ensuring the first time we reach the end is the minimum jumps.

Algorithm

1. Initialize a queue with the starting index 0 and a visited set.
2. While queue is not empty, iterate over all nodes at current level.
3. For each node, enqueue all reachable indices within jump range that are not visited.
4. Increment jump count after processing each level.
5. Return jump count when last index is reached.

💡 BFS ensures the shortest path by exploring all nodes at the current jump distance before moving further.

</>

Code

from collections import deque

def jump(nums):
    n = len(nums)
    if n == 1:
        return 0
    queue = deque([0])
    visited = set([0])
    jumps = 0
    while queue:
        size = len(queue)
        jumps += 1
        for _ in range(size):
            pos = queue.popleft()
            furthest_jump = min(pos + nums[pos], n - 1)
            for next_pos in range(pos + 1, furthest_jump + 1):
                if next_pos == n - 1:
                    return jumps
                if next_pos not in visited:
                    visited.add(next_pos)
                    queue.append(next_pos)
    return jumps

# Example usage
if __name__ == '__main__':
    print(jump([2,3,1,1,4]))  # Output: 2

Line Notes

queue = deque([0])Initialize queue with starting index

visited = set([0])Track visited indices to avoid repeats

for _ in range(size):Process all nodes at current BFS level

if next_pos == n - 1:Return jumps immediately when last index is reached

import java.util.*;

public class Solution {
    public int jump(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        queue.offer(0);
        visited[0] = true;
        int jumps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            jumps++;
            for (int i = 0; i < size; i++) {
                int pos = queue.poll();
                int furthestJump = Math.min(pos + nums[pos], n - 1);
                for (int nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
                    if (nextPos == n - 1) return jumps;
                    if (!visited[nextPos]) {
                        visited[nextPos] = true;
                        queue.offer(nextPos);
                    }
                }
            }
        }
        return jumps;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.jump(new int[]{2,3,1,1,4})); // Output: 2
    }
}

Line Notes

Queue<Integer> queue = new LinkedList<>();Initialize queue for BFS

boolean[] visited = new boolean[n];Track visited indices to prevent cycles

for (int i = 0; i < size; i++) {Process all nodes at current BFS level

if (nextPos == n - 1) return jumps;Return jumps immediately when last index is reached

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int jump(vector<int>& nums) {
    int n = nums.size();
    if (n == 1) return 0;
    queue<int> q;
    vector<bool> visited(n, false);
    q.push(0);
    visited[0] = true;
    int jumps = 0;
    while (!q.empty()) {
        int size = q.size();
        jumps++;
        for (int i = 0; i < size; ++i) {
            int pos = q.front(); q.pop();
            int furthestJump = min(pos + nums[pos], n - 1);
            for (int nextPos = pos + 1; nextPos <= furthestJump; ++nextPos) {
                if (nextPos == n - 1) return jumps;
                if (!visited[nextPos]) {
                    visited[nextPos] = true;
                    q.push(nextPos);
                }
            }
        }
    }
    return jumps;
}

int main() {
    vector<int> nums = {2,3,1,1,4};
    cout << jump(nums) << endl; // Output: 2
    return 0;
}

Line Notes

queue<int> q;Initialize queue for BFS traversal

vector<bool> visited(n, false);Track visited indices to avoid revisiting

for (int i = 0; i < size; ++i)Process all nodes at current BFS level

if (nextPos == n - 1) return jumps;Return jumps immediately when last index is reached

function jump(nums) {
    const n = nums.length;
    if (n === 1) return 0;
    const queue = [0];
    const visited = new Array(n).fill(false);
    visited[0] = true;
    let jumps = 0;
    while (queue.length > 0) {
        const size = queue.length;
        jumps++;
        for (let i = 0; i < size; i++) {
            const pos = queue.shift();
            const furthestJump = Math.min(pos + nums[pos], n - 1);
            for (let nextPos = pos + 1; nextPos <= furthestJump; nextPos++) {
                if (nextPos === n - 1) return jumps;
                if (!visited[nextPos]) {
                    visited[nextPos] = true;
                    queue.push(nextPos);
                }
            }
        }
    }
    return jumps;
}

// Example usage
console.log(jump([2,3,1,1,4])); // Output: 2

Line Notes

const queue = [0];Initialize queue with starting index

const visited = new Array(n).fill(false);Track visited indices to avoid repeats

for (let i = 0; i < size; i++) {Process all nodes at current BFS level

if (nextPos === n - 1) return jumps;Return jumps immediately when last index is reached

⏱

Complexity

TimeO(n^2) in worst case

SpaceO(n)

In worst case, BFS explores many nodes and edges, leading to quadratic time.

💡 For n=10^5, this approach is too slow, but it clearly models the problem as shortest path.

Interview Verdict: Accepted but inefficient

This approach works but is less efficient than the greedy solution and rarely coded in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, the greedy approach is the best to code due to its optimal time and space. Brute force is useful to explain problem complexity, and BFS is a conceptual alternative but less practical.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes	Yes	Mention only - never code
2. Greedy	O(n)	O(1)	No	No (without modification)	Code this approach
3. BFS	O(n^2) worst case	O(n)	No	Yes	Mention as alternative, rarely code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the greedy solution as the optimal method. Finally, discuss BFS as an alternative. Practice coding the greedy approach and testing edge cases.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Describe the brute force recursive approach and its inefficiency.Step 3: Introduce the greedy approach with current_end and furthest pointers.Step 4: Optionally mention BFS as a shortest path analogy.Step 5: Code the greedy solution and test with examples.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify the greedy pattern, optimize from brute force, and implement a clean, efficient solution with correct edge case handling.

Common Follow-ups

• What if you want to return the actual jump path? → Use backtracking or store predecessors.
• What if jumps can be backward? → Problem becomes more complex, BFS or DP needed.

💡 These follow-ups test your ability to extend the solution beyond minimum jumps count to path reconstruction or handle more complex jump rules.

🔍

Pattern Recognition

When to Use

1) Problem asks for minimum jumps or steps to reach end of array. 2) Each element indicates max jump length. 3) You can always reach the end. 4) Greedy or BFS shortest path pattern applies.

Signature Phrases

'minimum number of jumps to reach the last index''maximum jump length at that position'

NOT This Pattern When

Problems asking for maximum jumps or counting all possible paths are different patterns.

Similar Problems

Jump Game I - checks reachability instead of minimum jumpsMinimum Number of Refueling Stops - similar greedy jump optimizationCoin Change - minimum steps to reach target with different moves

Practice

1. Consider the following Python code snippet implementing the optimal solution to remove k digits from a number string to get the smallest number. What is the output of removeKdigits("1432", 2)?

def removeKdigits(num: str, k: int) -> str:
    builder = []
    for digit in num:
        while k > 0 and builder and builder[-1] > digit:
            builder.pop()
            k -= 1
        builder.append(digit)
    while k > 0:
        builder.pop()
        k -= 1
    result = ''.join(builder).lstrip('0')
    return result if result else '0'

easy

A. "14"

B. "13"

C. "12"

D. "32"

Solution

1. Step 1: Trace builder and k during iteration

   Start with builder = [], k=2 - digit='1': builder=['1'], k=2 - digit='4': '4' > '1', append: builder=['1','4'], k=2 - digit='3': '3' < '4', pop '4', k=1; append '3': builder=['1','3'] - digit='2': '2' < '3', pop '3', k=0; append '2': builder=['1','2']

2. Step 2: Remove remaining k and finalize

   k=0, no more pops. Result = '12' after stripping leading zeros.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected smallest number after removing 2 digits [OK]

Hint: Pop larger digits when smaller digit found until k=0 [OK]

Common Mistakes:

• Not popping enough digits when smaller digit appears
• Removing digits from front only
• Forgetting to strip leading zeros

2. The following code attempts to form the largest number from a list of integers. Which line contains a subtle bug that causes incorrect output on inputs like [0, 0, 0]?

medium

A. Line 8: Returning concatenated string without zero check

B. Line 4-6: Custom comparator function

C. Line 7: Sorting with custom comparator

D. Line 3: Converting integers to strings

Solution

1. Step 1: Trace output for input [0,0,0]

   After sorting, nums_str is ['0', '0', '0'], concatenation is '000'.

2. Step 2: Identify missing check for all zeros

   Without checking if first element is '0', the function returns '000' instead of '0'.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding a check to return '0' if nums_str[0] == '0' fixes the bug [OK]

Hint: Check if first string is '0' to handle all-zero case [OK]

Common Mistakes:

• Forgetting all-zero check
• Incorrect comparator logic
• Sorting without custom comparator

3. Identify the bug in the following code snippet for the Maximum Units on a Truck problem:

def maximumUnits(boxTypes, truckSize):
    boxTypes.sort(key=lambda x: x[1])  # Sort ascending instead of descending
    totalUnits = 0
    for boxes, units in boxTypes:
        if truckSize == 0:
            break
        take = min(boxes, truckSize)
        totalUnits += take * units
        truckSize -= take
    return totalUnits

medium

A. Line 2: Sorting boxTypes in ascending order instead of descending

B. Line 5: Missing check for truckSize == 0

C. Line 7: Incorrect calculation of take using min(boxes, truckSize)

D. Line 8: Incorrect update of totalUnits by multiplying take and units

Solution

1. Step 1: Examine sorting order

   Sorting ascending by units per box causes picking boxes with lowest units first, leading to suboptimal total units.

2. Step 2: Verify other lines

   Check for early stopping (line 5) is correct; min calculation and totalUnits update are correct.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting order is critical for greedy correctness [OK]

Hint: Sort descending by units per box to maximize units [OK]

Common Mistakes:

• Sorting ascending instead of descending
• Forgetting to break when truckSize=0
• Off-by-one in min calculation

4. The following code attempts to compute the minimum cost to connect sticks using a min-heap. Identify the bug that causes incorrect results or infinite loops.

medium

A. Line 3: Incorrect base case check for single stick

B. Line 9: Adding cost before popping sticks

C. Line 6: Not heapifying the sticks before processing

D. Line 11: Not pushing the merged stick back into the heap

Solution

1. Step 1: Review the merge loop

   The loop pops two smallest sticks and sums their lengths as cost.

2. Step 2: Check if merged stick is reinserted

   The merged stick must be pushed back into the heap to continue merging. Missing this causes infinite loop or incorrect cost.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Without pushing merged stick, heap shrinks incorrectly -> infinite loop or wrong result [OK]

Hint: Merged sticks must be pushed back to heap [OK]

Common Mistakes:

• Forgetting to push merged stick back
• Incorrect base case handling
• Misordering heap operations

5. Suppose the Gas Station problem is modified so that you can refill gas multiple times at the same station (i.e., unlimited reuse), and you want to find if any start station allows completing the circle with this new rule. Which approach correctly adapts to this variant?

hard

A. Check if total gas is at least total cost; if yes, return any station since reuse allows completion

B. Modify the algorithm to allow multiple passes over the stations until tank is non-negative

C. Use a graph cycle detection algorithm to find a feasible cycle with unlimited refills

D. Use the original greedy approach without changes; it still works correctly

Solution

1. Step 1: Understand unlimited refill effect

   With unlimited refills, the only constraint is total gas >= total cost; any station can be start.

2. Step 2: Simplify solution

   Since reuse removes the need to track tank drops, just check total gas vs cost and return any index if feasible.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Unlimited refill means any station works if total gas suffices [OK]

Hint: Unlimited refill means total gas check suffices [OK]

Common Mistakes:

• Trying to simulate multiple passes
• Using original greedy without adaptation
• Overcomplicating with graph algorithms