LeetCode 55: Jump Game Solution in Python Explained

Problem Statement

LeetCode 55, Jump Game, 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 determine if you can reach the last index starting from index 0, returning true if possible, false otherwise.

Constraints

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

Example

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Can jump from 0 to 1 (2 steps), then 1 to 4 (3 steps).

Input: nums = [3,2,1,0,4]
Output: false
Explanation: Stuck at index 3 (jump 0), cannot reach 4.

Input: nums = [1]
Output: true
Explanation: Already at the last index.

Understanding the Problem

How do you solve LeetCode 55: Jump Game in Python? For nums = [2,3,1,1,4], check if you can reach index 4 from index 0—here, it’s possible with jumps 0→1→4, so return true. For [3,2,1,0,4], you get stuck at index 3 (jump 0), so return false. We need an efficient way to determine reachability. We’ll explore two approaches: a Greedy Solution (optimal and primary) and an Alternative with Dynamic Programming (systematic but less efficient). The greedy method runs in O(n) time by tracking the furthest reachable index.

Solution 1: Greedy Approach (Primary)

Explanation

Use a greedy strategy: maintain the furthest index you can reach (max_reach) as you traverse the array. At each position, update max_reach based on the current jump capability. If you can’t reach the current position or the last index, return false; otherwise, return true.

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

i=0: max_reach = 2
i=1: max_reach = 4
i=2: max_reach = 4
i=3: max_reach = 4
Reach last index (4), return true

Initialize Max Reach.

Start with max_reach = 0.

Iterate Array.

Check if current index is reachable, update max_reach.

Return Result.

true if max_reach ≥ last index, false if stuck.

Step-by-Step Example

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

We need true.

Goal: Check if last index is reachable.
Result for Reference: true.
Start: nums = [2,3,1,1,4], max_reach = 0, last = 4.
Step 1: i = 0, nums[0] = 2.

i ≤ max_reach (0 ≤ 0), max_reach = max(0, 0+2) = 2.

Step 2: i = 1, nums[1] = 3.

i ≤ max_reach (1 ≤ 2), max_reach = max(2, 1+3) = 4.

Step 3: i = 2, nums[2] = 1.

i ≤ max_reach (2 ≤ 4), max_reach = max(4, 2+1) = 4.

Step 4: i = 3, nums[3] = 1.

i ≤ max_reach (3 ≤ 4), max_reach = max(4, 3+1) = 4.

Step 5: max_reach = 4 ≥ last = 4, can reach end.
Finish: Return true.

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

We need false.

Start: max_reach = 0, last = 4.
Step 1: i = 0, nums[0] = 3.

max_reach = 3.

Step 2: i = 1, nums[1] = 2.

max_reach = max(3, 1+2) = 3.

Step 3: i = 2, nums[2] = 1.

max_reach = max(3, 2+1) = 3.

Step 4: i = 3, nums[3] = 0.

max_reach = max(3, 3+0) = 3.

Step 5: i = 4 > max_reach = 3, cannot reach 4.
Finish: Return false.

How the Code Works (Greedy)

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

def canJump(nums: list[int]) -> bool:
    # Line 1: Initialize max reach
    max_reach = 0
    last = len(nums) - 1

    # Line 2: Iterate through array
    for i in range(len(nums)):
        # Line 3: Check if current index is reachable
        if i > max_reach:
            return False
        # Line 4: Update max reach
        max_reach = max(max_reach, i + nums[i])
        # Line 5: Early exit if last index reached
        if max_reach >= last:
            return True

    # Line 6: Return true if loop completes (single element case)
    return True

Alternative: Dynamic Programming Approach

Explanation

Use DP where dp[i] indicates if index i is reachable from 0. Start with dp[0] = true, then for each position, check if any previous reachable position can jump to it. This is O(n^2) but provides a different perspective.

Initialize DP Array.
Fill Table.

Check jumps from all prior reachable positions.

3. Return Result.

dp[n-1] indicates if last index is reachable.

Step-by-Step Example (Alternative)

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

Start: dp = [true, false, false, false, false].
Step 1: i = 0, nums[0] = 2.

dp[1] = true, dp[2] = true.

Step 2: i = 1, nums[1] = 3.

dp[2] = true, dp[3] = true, dp[4] = true.

Step 3: i = 2, nums[2] = 1.

dp[3] = true.

Step 4: i = 3, nums[3] = 1.

dp[4] = true.

Finish: dp[4] = true, return true.

How the Code Works (DP)

def canJumpDP(nums: list[int]) -> bool:
    # Line 1: Initialize DP array
    n = len(nums)
    dp = [False] * n
    dp[0] = True

    # Line 2: Fill DP table
    for i in range(n):
        if dp[i]:
            # Line 3: Mark reachable positions
            for j in range(1, nums[i] + 1):
                if i + j < n:
                    dp[i + j] = True

    # Line 4: Return if last index is reachable
    return dp[n - 1]

Complexity

Greedy:

Time: O(n) – Single pass through array.
Space: O(1) – Only one variable.

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 55. DP is O(n^2) time and O(n) space, less efficient but shows a comprehensive approach.

Key Insights

Tips to master LeetCode 55:

Max Reach: Track furthest point greedily.
Early Fail: Stop if current index is unreachable.
Single Pass: Optimize with O(n) traversal.

Additional Example

For nums = [1,2,3]:

Goal: true.
Greedy: max_reach = 1, 3, 3, reaches 2, return true.
Result: true.

Edge Cases

Single Element: [1] – Return true.
All Zeros: [0] – Return true; [0,1] – Return false.
Max Jumps: [5,0,0,0] – Return true.

Final Thoughts

The Greedy solution is a slam dunk for LeetCode 55 in Python—fast, simple, and space-efficient. For a related challenge, try LeetCode 54: Spiral Matrix to explore matrix traversal! Ready to jump? Solve LeetCode 55 on LeetCode now and test it with [2,3,1,1,4] or [3,0,0,4] to perfect your reachability skills. Leap in and make it to the end!