Jump Game - Python Solution

1. Introduction

"Jump Game" is a captivating problem that blends array traversal with decision-making. It's a common challenge in coding interviews and competitive programming. The problem involves determining whether it's possible to reach the end of an array, given that each element represents the maximum jump length from that position. This task tests one's ability to devise a strategy for navigating through the array based on dynamic conditions.

Problem

Given an integer array nums, where you start at the first index, and each element in the array represents your maximum jump length at that position, the task is to return true if you can reach the last index, or false otherwise.

2. Solution Steps

1. Initialize a variable to keep track of the farthest reachable index.

2. Iterate through each element of the array.

3. Update the farthest reachable index based on the current position and the jump length from that position.

4. If at any point the farthest reachable index is less than the current index, return false as it's not possible to move forward.

5. If the farthest reachable index reaches or exceeds the last index, return true.

6. Continue until the end of the array is reached or it's determined that the end cannot be reached.

3. Code Program

def canJump(nums):
    farthest = 0

    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])

    return True

# Example Usage
print(canJump([2,3,1,1,4]))
print(canJump([3,2,1,0,4]))

Output:

True
False

Explanation:

1. Farthest Reachable Index: The variable farthest is used to keep track of the farthest index that can be reached.

2. Iterative Traversal: The function iterates through the array, checking if each position is reachable.

3. Reachability Check: If the current position is greater than the farthest reachable index, it means the end cannot be reached, and the function returns false.

4. Updating Reachable Index: The farthest reachable index is updated based on the current position and the jump length.

5. Completion Check: If the farthest reachable index reaches or goes beyond the last index, the function returns true.

6. Result: The function determines whether it's possible to reach the end of the array.