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. You have a circular route with gas stations, each providing some gas and requiring some cost to travel to the next station. You want to find a starting station to complete the full circle without running out of gas. Which algorithmic approach guarantees finding the correct starting station efficiently?

easy

A. Divide and conquer by splitting the circle into halves and solving recursively

B. Dynamic Programming to store maximum gas reachable from each station

C. Brute force by simulating the trip starting from each station until success or failure

D. Greedy approach that checks total gas vs total cost and resets start when tank goes negative

Solution

1. Step 1: Understand problem constraints

   The problem requires finding a single start station to complete a circular route without running out of gas, which can be solved efficiently by a greedy approach.

2. Step 2: Identify the correct approach

   The greedy method that first checks if total gas is at least total cost ensures a solution exists, then resets the start whenever the tank goes negative, guaranteeing an O(n) solution.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Greedy reset approach is optimal and widely accepted [OK]

Hint: Check total gas vs cost, then reset start on negative tank [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Using DP which is unnecessary
• Trying divide and conquer which doesn't fit circular nature

2. You are given arrival and departure times of trains at a station. You need to find the minimum number of platforms required so that no train waits. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Sort trains by arrival time and use a min-heap to track earliest departure times

B. Dynamic Programming to find the maximum number of overlapping intervals

C. Greedy approach by always assigning the next available platform without sorting

D. Brute force nested loops checking all pairs of trains for overlaps

Solution

1. Step 1: Understand the problem requires tracking overlapping intervals

   We need to find the maximum number of trains simultaneously at the station, which corresponds to the maximum overlap of intervals.

2. Step 2: Identify the optimal approach

   Sorting trains by arrival time and using a min-heap to track the earliest departure allows efficient detection of overlaps and platform reuse, guaranteeing an optimal solution.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Min-heap approach efficiently tracks platform usage [OK]

Hint: Min-heap tracks earliest departure for platform reuse [OK]

Common Mistakes:

• Assuming greedy without sorting works optimally
• Thinking DP is needed for interval overlaps
• Using brute force for large inputs

3. Identify the bug in the following code snippet for the Minimum Domino Rotations problem:

def minDominoRotations(A, B):
    def check(x):
        rotations_a = rotations_b = 0
        for i in range(len(A)):
            if A[i] != x and B[i] != x:
                return 0  # Bug here
            elif A[i] != x:
                rotations_a += 1
            elif B[i] != x:
                rotations_b += 1
        return min(rotations_a, rotations_b)

    rotations = check(A[0])
    if rotations != -1:
        return rotations
    else:
        return check(B[0])

medium

A. Incorrect initialization of rotations_a and rotations_b

B. Not incrementing rotations when both sides equal x

C. Returning rotations without checking both candidates

D. The return value 0 instead of -1 when no domino can be rotated to x

Solution

1. Step 1: Analyze early return condition

   If neither side matches candidate x, the function should return -1 to indicate failure, not 0.

2. Step 2: Impact of returning 0

   Returning 0 falsely indicates zero rotations needed, causing incorrect positive results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Returning -1 signals no solution; 0 misleads caller [OK]

Hint: Return -1 on failure, not 0 [OK]

Common Mistakes:

• Returning 0 instead of -1 on failure
• Overcounting rotations when both sides equal candidate

4. Suppose the problem is modified so that children can have equal ratings but must still have strictly more candies than neighbors with lower ratings. Which modification to the optimal algorithm correctly handles this variant?

hard

A. Change comparison from '>' to '>=' in both passes to handle equal ratings

B. Keep '>' comparisons but initialize candies with zeros and adjust accordingly

C. Use the same two-pass greedy with '>' comparisons but do not update candies if ratings are equal

D. Replace two-pass greedy with a sorting-based approach to assign candies in rating order

Solution

1. Step 1: Understand new requirement

   Children with equal ratings do not require more candies than each other, only strictly higher ratings require more candies.

2. Step 2: Adjust comparisons in algorithm

   Keep '>' comparisons to ensure only strictly higher ratings get more candies; do not update candies when ratings are equal.

3. Step 3: Avoid changing to '>=' which would incorrectly increase candies for equal ratings

   Changing to '>=' breaks minimality and correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Strict '>' comparisons preserve problem constraints with equal ratings [OK]

Hint: Strict '>' comparisons handle equal ratings correctly [OK]

Common Mistakes:

• Changing '>' to '>=' causing over-assignment
• Initializing candies with zeros
• Using sorting unnecessarily

5. Suppose the problem is modified so that the input list can contain negative integers as well. Which of the following approaches correctly adapts the algorithm to handle negatives and still produce the largest concatenated number?

hard

A. Convert negatives to positive strings before sorting with the comparator, then prepend '-' to those in final output

B. Filter out negative numbers since they cannot contribute to the largest concatenation

C. Separate negatives and positives, sort positives with comparator, sort negatives by absolute value descending, then concatenate positives followed by negatives

D. Convert all numbers to strings including negatives, then sort with the same comparator comparing concatenations

Solution

1. Step 1: Recognize negatives affect ordering and concatenation semantics

   Negative numbers cannot be treated the same as positives because concatenation with '-' changes lex order.

2. Step 2: Separate positives and negatives, sort positives with original comparator, sort negatives by absolute value descending

   Concatenate positives first (largest number), then negatives to maintain largest overall concatenation.

3. Step 3: This approach preserves ordering logic and handles negatives correctly

   Other options either ignore negatives or mishandle signs causing incorrect results.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Separating and sorting by sign handles negatives correctly [OK]

Hint: Negatives require separate handling, not just string comparison [OK]

Common Mistakes:

• Treating negatives as strings directly
• Ignoring negatives
• Converting negatives to positives incorrectly