Jump Game II

LeetCode 45 | Difficulty: Medium

Medium

Problem Description

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at index i, you can jump to any index (i + j) where:

- `0 <= j <= nums[i]` and

- `i + j < n`

Return the minimum number of jumps to reach index n - 1. The test cases are generated such that you can reach index n - 1.

Example 1:

Input: nums = [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.

Example 2:

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

Constraints:

- `1 <= nums.length <= 10^4`

- `0 <= nums[i] <= 1000`

- It's guaranteed that you can reach `nums[n - 1]`.

Topics: Array, Dynamic Programming, Greedy

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 128 ms)

Metric	Value
Runtime	128 ms
Memory	N/A
Date	2018-03-08

Solution

public class Solution {
    public int Jump(int[] nums) {
    int step_count = 0;
    int last_jump_max = 0;
    int current_jump_max = 0;
    for (int i = 0; i < nums.Length-1; i++)
    {
        current_jump_max = Math.Max(current_jump_max, i+nums[i]);
        if(i==last_jump_max) {
            step_count++;
            last_jump_max = current_jump_max;
        }
    
    }
    return step_count;
}
}

📜 1 more C# submission(s)

Submission (2021-12-16) — 195 ms, 38.2 MB

public class Solution {
    public int Jump(int[] nums) {
        int end=0, farCanReach = 0, count = 0;
    int n = nums.Length;
    for (int i = 0; end < n-1; end = farCanReach)
    {
        count++;
        while(i<n && i<=end)
        {
            farCanReach = Math.Max(farCanReach, i+ nums[i]);
            i++;
        }
        if(end == farCanReach) return -1;
    }
    
    return count;
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.