LeetCode Solutions Blog

Jump Game

Number: 55

Difficulty: Medium

Paid? No

Problem Description

Given an integer array nums where each element represents the maximum jump length from that position, determine if you can reach the last index starting from the first index.

Key Insights

The greedy approach is optimal for this problem.
Track the furthest index reachable as you iterate through the array.
If the current index exceeds the maximum reachable index, it is impossible to proceed further.
The solution only requires constant extra space.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1)

Solution

The solution uses a greedy algorithm. As you iterate through each array element, you maintain a variable (maxReach) that represents the furthest index you can reach so far. For each index i, if i is greater than maxReach then it is not possible to reach index i and hence return false immediately. Otherwise, update maxReach to the maximum of its current value and i + nums[i]. If you can iterate through the array without i exceeding maxReach, then you can reach the end and return true.

Code Solutions

# Function to determine if you can reach the last index of the array
def canJump(nums):
    # Initialize maxReach which is the max index reachable at start (index 0)
    maxReach = 0
    # Iterate through each element and its index
    for i, jump in enumerate(nums):
        # If current index is greater than maximum reachable index, return False
        if i > maxReach:
            return False
        # Update maxReach with the maximum of current maxReach and i + jump length at index i
        maxReach = max(maxReach, i + jump)
        # If current maxReach is already at or beyond the last index, return True
        if maxReach >= len(nums) - 1:
            return True
    # Return True if the end is reachable after processing all indices
    return True

# Example usage:
# print(canJump([2,3,1,1,4]))  # Expected output: True
# print(canJump([3,2,1,0,4]))  # Expected output: False