Jump game

XXX.Jump Game

Greedy

Problem Statement:

Given an array of non-negative integers nums, where each element represents your maximum jump length at that position, determine if you can reach the last index starting from the first index.

Algorithm:

1. Initialize a variable maxReach to track the furthest index reachable from the current position.
2. Iterate through the array:
   • If the current index exceeds maxReach, return false since it's not possible to proceed further.
   • Update maxReach to the maximum of its current value and i + nums[i] (furthest position reachable from index i).
3. If the loop completes, return true as the last index is reachable.

Complexity:

Time: O(n), where n is the length of the array, as we iterate through the array once. | Space: O(1), as no extra space is used.

Java Implementation:

public boolean canJump(int[] nums) {
    int maxReach = nums[0]; // Maximum reachable index from the start

    // Iterate through the array
    for (int i = 1; i < nums.length; i++) {
        if (i > maxReach) return false; // If current index is beyond maxReach, return false
        maxReach = Math.max(maxReach, i + nums[i]); // Update maxReach
    }

    return true; // If loop completes, last index is reachable
}
                

Python Implementation:

def can_jump(nums):
    max_reach = nums[0] # Maximum reachable index from the start

    for i in range(1, len(nums)):
        if i > max_reach:
            return False # If current index is beyond max_reach, return False
        max_reach = max(max_reach, i + nums[i]) # Update max_reach

    return True # If loop completes, last index is reachable
                

C++ Implementation:

bool canJump(vector& nums) {
    int maxReach = nums[0]; // Maximum reachable index from the start

    for (int i = 1; i < nums.size(); i++) {
        if (i > maxReach) return false; // If current index is beyond maxReach, return false
        maxReach = max(maxReach, i + nums[i]); // Update maxReach
    }

    return true; // If loop completes, last index is reachable
}