Jump Game I Solution Explanations

Problem Statement

Given an array of non-negative integers, nums, where each element represents the maximum number of steps that can be jumped forward, determine if you can reach the last index starting from the first index.

Caategory: Greedy

---

1. Brute-Force Solution

The brute-force approach is to recursively explore all possible jumps from each index to see if we can reach the last index.

1. Recursive Exploration: For each position, we recursively try each possible jump up to the maximum allowed by the number at the current index.
2. Base Case: If we reach the last index, we return True.
3. Return Condition: If any recursive call returns True, it means we can reach the end, so we return True. If we exhaust all jumps from the current position without success, we return False.

Time Complexity

• This approach has an exponential time complexity, (O(2^n)), since each index can lead to two recursive calls.

Example Walkthrough

For an array like [2, 3, 1, 1, 4], starting at index 0 with value 2:

• We explore positions 1 and 2.
• If we reach the end in any branch, we return True.

---

Python Java C++

def can_jump_from_position(position, nums):
    """Check if you can jump to the end starting from the current position."""
    if position == len(nums) - 1:
        return True
    furthest_jump = min(position + nums[position], len(nums) - 1)
    for next_position in range(position + 1, furthest_jump + 1):
        if can_jump_from_position(next_position, nums):
            return True
    return False

def can_jump(nums):
    """Wrapper function to check if we can jump to the last index."""
    return can_jump_from_position(0, nums)
    

public class JumpGame {
    public static boolean canJumpFromPosition(int position, int[] nums) {
        // Check if current position is the last index
        if (position == nums.length - 1) return true;
        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) return true;
        }
        return false;
    }

    public static boolean canJump(int[] nums) {
        return canJumpFromPosition(0, nums);
    }
}
    

#include <vector>
using namespace std;

bool canJumpFromPosition(int position, const vector<int>& nums) {
    // Check if current position is the last index
    if (position == nums.size() - 1) return true;
    int furthestJump = min(position + nums[position], (int)nums.size() - 1);
    for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
        if (canJumpFromPosition(nextPosition, nums)) return true;
    }
    return false;
}

bool canJump(const vector<int>& nums) {
    return canJumpFromPosition(0, nums);
}
    

---

2. Dynamic Programming Solution

The dynamic programming (DP) approach optimizes by storing intermediate results to avoid redundant calculations. We use a memo array where each element represents whether that index can reach the last index.

1. Initialization: Set memo[-1] to True because the last index is always reachable from itself.
2. Backwards Iteration: Iterate from the second-to-last index backward. For each index:
   • Determine the furthest reachable index based on the current number of jumps.
   • Check if any index within this range can reach the end (as indicated by memo[j]).
3. Final Return: If memo[0] is True, it means the start can reach the end.

Time Complexity

• The DP approach has a time complexity of (O(n^2)) due to the nested loops.

Example Walkthrough

For an array [2, 3, 1, 1, 4], we check from the end to start, marking indices as reachable or not, and use this information to make decisions more efficiently.

---

Python Java C++

def can_jump(nums):
    """Check if you can reach the last index using dynamic programming."""
    memo = [False] * len(nums)
    memo[-1] = True  # Base case: last index is always reachable from itself
    for i in range(len(nums) - 2, -1, -1):
        furthest_jump = min(i + nums[i], len(nums) - 1)
        for j in range(i + 1, furthest_jump + 1):
            if memo[j]:
                memo[i] = True
                break
    return memo[0]
    

public class JumpGame {
    public static boolean canJump(int[] nums) {
        boolean[] memo = new boolean[nums.length];
        memo[nums.length - 1] = true;  // Base case: last index is always reachable
        for (int i = nums.length - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], nums.length - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (memo[j]) {
                    memo[i] = true;
                    break;
                }
            }
        }
        return memo[0];
    }
}
    

#include <vector>
using namespace std;

bool canJump(const vector<int>& nums) {
    vector<bool> memo(nums.size(), false);
    memo[nums.size() - 1] = true;  // Base case
    for (int i = nums.size() - 2; i >= 0; i--) {
        int furthestJump = min(i + nums[i], (int)nums.size() - 1);
        for (int j = i + 1; j <= furthestJump; j++) {
            if (memo[j]) {
                memo[i] = true;
                break;
            }
        }
    }
    return memo[0];
}
    

---

3. Greedy Solution

The greedy approach is the most efficient, leveraging the concept of “reachable” indices by always keeping track of the furthest index we can reach.

1. Tracking Reachability: Initialize a variable reachable to 0 (the furthest index we can currently reach).
2. Iterate Through Array: For each index i, check:
   • If i is greater than reachable, it means we cannot reach this index, so we return False.
   • Update reachable to the maximum of reachable and i + nums[i].
3. Final Return: If the loop completes, it means we can reach the last index.

Time Complexity

• The greedy approach has a linear time complexity, (O(n)), since it only requires a single pass through the array.

Example Walkthrough

For [2, 3, 1, 1, 4], starting with reachable = 0, we update it as we move through each index based on the possible jumps. If reachable ends up covering the last index, we return True.

---

Python Java C++

def can_jump(nums):
    """Check if you can reach the last index using a greedy approach."""
    reachable = 0
    for i in range(len(nums)):
        if i > reachable:
            return False
        reachable = max(reachable, i + nums[i])
    return True
    

public class JumpGame {
    public static boolean canJump(int[] nums) {
        int reachable = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > reachable) return false;
            reachable = Math.max(reachable, i + nums[i]);
        }
        return true;
    }
}
    

#include <vector>
using namespace std;

bool canJump(const vector<int>& nums) {
    int reachable = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (i > reachable) return false;
        reachable = max(reachable, i + nums[i]);
    }
    return true;
}