LeetCode 55: Jump Game — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Medium — Array | Greedy | Dynamic Programming

The Problem

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

Approach

Use a greedy approach to track the maximum reachable index as we iterate through the array. At each position, check if the current index is reachable, and update the maximum reachable position based on the current jump length.

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

Code

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reachable = 0

        for i, jump_length in enumerate(nums):
            if i > max_reachable:
                return False
            max_reachable = max(max_reachable, i + jump_length)

        return True