Jump Game

Problem Statement

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Examples

Example 1:

Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Approaches

1. Simple Approach (Recursive)

This approach uses recursion to try all possible jump combinations.

Time Complexity: O(2^n), where n is the length of the array Space Complexity: O(n) for the recursion stack

2. Optimal Approach (Greedy)

The optimal approach uses a greedy strategy, working backwards from the last index.

Time Complexity: O(n) Space Complexity: O(1)

Solutions

Java Solution

// Simple Approach (Recursive)
class Solution {
    public boolean canJump(int[] nums) {
        return canJumpFromPosition(0, nums);
    }

    private boolean canJumpFromPosition(int position, int[] nums) {
        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;
    }
}

// Optimal Approach (Greedy)
class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

C++ Solution

// Simple Approach (Recursive)
class Solution {
public:
    bool canJump(vector<int>& nums) {
        return canJumpFromPosition(0, nums);
    }

private:
    bool canJumpFromPosition(int position, vector<int>& nums) {
        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;
    }
};

// Optimal Approach (Greedy)
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int lastPos = nums.size() - 1;
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
};

Explanation

Simple Approach (Recursive)

1. Start from the first position (index 0).
2. For each position, try all possible jumps from 1 to the maximum jump length at that position.
3. Recursively check if any of these jumps can lead to the last index.
4. If we reach the last index, return true.
5. If we can't reach the last index from any position, return false.

This approach is intuitive but inefficient for large inputs due to its exponential time complexity.

Optimal Approach (Greedy)

This approach works backwards from the last index:

1. Initialize the last position as the last index of the array.
2. Iterate through the array from right to left:
   • If we can reach the last position from the current index (i + nums[i] >= lastPos), update the last position to the current index.
3. After the iteration, if the last position is 0, it means we can reach the end from the start.

This method is efficient as it only requires a single pass through the array and has a linear time complexity.

Test Cases

1. Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

2. Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

3. Input: nums = [0] Output: true Explanation: The array has only one element, and we are already at the last index.

4. Input: nums = [2,0,0] Output: true Explanation: Jump 2 steps from index 0 to reach the last index.

5. Input: nums = [1,1,1,0] Output: true Explanation: Jump 1 step at a time to reach the last index.

These test cases cover scenarios with possible jumps, impossible jumps, single-element arrays, arrays with zeros, and arrays requiring multiple small jumps.