LeetCode 45: Jump Game II Solution in Python Explained

Problem Statement

LeetCode 45, Jump Game II, is a medium-level problem where you’re given an array of non-negative integers nums. Each element nums[i] represents the maximum number of steps you can jump forward from index i. Your task is to return the minimum number of jumps needed to reach the last index of the array, starting from index 0. You can always reach the last index.

Constraints

  • 1 <= nums.length <= 10^4: Array length is between 1 and 10,000.
  • 0 <= nums[i] <= 1000: Each element is between 0 and 1000.

Example

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: Jump from 0 to 1 (2 steps), then 1 to 4 (3 steps), total 2 jumps.

Input: nums = [2,3,0,1,4]
Output: 2
Explanation: Jump from 0 to 1 (2 steps), then 1 to 4 (3 steps), total 2 jumps.

Input: nums = [1,2]
Output: 1
Explanation: Jump from 0 to 1 (1 step), total 1 jump.

Understanding the Problem

How do you solve LeetCode 45: Jump Game II in Python? For nums = [2,3,1,1,4], find the fewest jumps to reach index 4—here, 2 jumps (0→1→4). Each position offers a range of possible jumps, and we need the minimum. We’ll explore two approaches: a Greedy Solution (optimal and primary) and an Alternative with Dynamic Programming (systematic but slower). The greedy method minimizes jumps by maximizing reach per step in O(n) time.

Solution 1: Greedy Approach (Primary)

Explanation

Use a greedy strategy: at each step, jump to the position that allows the furthest reach in the next jump. Track the current end of the jump range (curr_end) and the furthest reachable position (curr_farthest). When you reach curr_end, increment jumps and update the range.

Here’s a flow for [2,3,1,1,4]:

Jump 1: From 0, max reach = 2, jump to 1 (curr_farthest = 4)
Jump 2: From 1, reach 4 directly
Total = 2 jumps
  1. Initialize Variables.
  • jumps, curr_end, curr_farthest.
  1. Iterate Array.
  • Update furthest reach, jump when hitting end.
  1. Return Jumps.
  • Minimum jumps to last index.

Step-by-Step Example

Example 1: nums = [2,3,1,1,4]

We need 2.

  • Goal: Minimize jumps to last index.
  • Result for Reference: 2.
  • Start: nums = [2,3,1,1,4], jumps = 0, curr_end = 0, curr_farthest = 0.
  • Step 1: i = 0, nums[0] = 2.
    • curr_farthest = max(0, 0+2) = 2, i = curr_end = 0, jumps = 1, curr_end = 2.
  • Step 2: i = 1, nums[1] = 3.
    • curr_farthest = max(2, 1+3) = 4.
  • Step 3: i = 2, nums[2] = 1.
    • curr_farthest = max(4, 2+1) = 4, i = curr_end = 2, jumps = 2, curr_end = 4.
  • Step 4: i = 3, nums[3] = 1.
    • curr_farthest = 4, i < curr_end, continue.
  • Step 5: i = 4, reached end.
  • Finish: Return jumps = 2.

Example 2: nums = [2,3,0,1,4]

We need 2.

  • Start: jumps = 0, curr_end = 0, curr_farthest = 0.
  • Step 1: i = 0, curr_farthest = 2, jumps = 1, curr_end = 2.
  • Step 2: i = 1, curr_farthest = 4.
  • Step 3: i = 2, i = curr_end, jumps = 2, curr_end = 4.
  • Finish: Return 2.

How the Code Works (Greedy)

Here’s the Python code with line-by-line explanation:

def jump(nums: list[int]) -> int:
    # Line 1: Handle single-element case
    if len(nums) <= 1:
        return 0

    # Line 2: Initialize variables
    jumps = 0
    curr_end = 0
    curr_farthest = 0

    # Line 3: Iterate until second-to-last index
    for i in range(len(nums) - 1):
        # Line 4: Update furthest reachable
        curr_farthest = max(curr_farthest, i + nums[i])

        # Line 5: Reached current jump’s end
        if i == curr_end:
            jumps += 1
            curr_end = curr_farthest
            # Line 6: Early exit if end reached
            if curr_end >= len(nums) - 1:
                break

    # Line 7: Return minimum jumps
    return jumps

Alternative: Dynamic Programming Approach

Explanation

Use DP where dp[i] is the minimum jumps to reach index i. Build the table by considering all possible jumps from previous positions. This is O(n^2) and less efficient but shows the full solution space.

  1. Initialize DP Array.
  2. Fill Table.
  • For each position, check all prior jumps.

3. Return dp[n-1].

Step-by-Step Example (Alternative)

For nums = [2,3,1,1,4]:

  • Start: dp = [0,inf,inf,inf,inf].
  • Step 1: i = 0, nums[0] = 2.
    • dp[1] = 1, dp[2] = 1.
  • Step 2: i = 1, nums[1] = 3.
    • dp[2] = min(1, dp[1]+1) = 1, dp[3] = 2, dp[4] = 2.
  • Step 3: i = 2, dp[3] = min(2, dp[2]+1) = 2.
  • Step 4: i = 3, dp[4] = min(2, dp[3]+1) = 2.
  • Finish: dp[4] = 2.

How the Code Works (DP)

def jumpDP(nums: list[int]) -> int:
    # Line 1: Initialize DP array
    n = len(nums)
    dp = [float('inf')] * n
    dp[0] = 0

    # Line 2: Fill DP table
    for i in range(n):
        # Line 3: Try all possible jumps from i
        for j in range(1, nums[i] + 1):
            if i + j < n:
                dp[i + j] = min(dp[i + j], dp[i] + 1)

    # Line 4: Return minimum jumps to end
    return dp[n - 1]

Complexity

  • Greedy:
    • Time: O(n) – Single pass through array.
    • Space: O(1) – Only variables.
  • Dynamic Programming:
    • Time: O(n * m) – n positions, m = max(nums[i]), up to O(n^2).
    • Space: O(n) – DP array.

Efficiency Notes

Greedy is O(n) time and O(1) space, optimal for LeetCode 45. DP is O(n^2) time and O(n) space, overkill but comprehensive.

Key Insights

Tips to master LeetCode 45:

  • Maximize Reach: Greedy jumps to furthest point per step.
  • Range Tracking: Use curr_end and curr_farthest.
  • Early Exit: Stop when last index is reachable.

Additional Example

For nums = [3,2,1,0,4]:

  • Goal: 2.
  • Greedy: Jump 0→1 (max reach 3), 1→4, return 2.
  • Result: 2.

Edge Cases

  • Single Element: [5] – Return 0.
  • All Ones: [1,1,1] – Return 2.
  • Zeros: [1,0,0,1] – Return 2.

Final Thoughts

The Greedy solution is a sleek choice for LeetCode 45 in Python—fast, simple, and space-efficient. For a related challenge, try LeetCode 44: Wildcard Matching to tackle a hard pattern problem! Ready to jump in? Solve LeetCode 45 on LeetCode now and test it with [2,3,1,4] or [1,2,3] to hone your greedy skills. Leap in and reach the end!