LeetCode 45: Jump Game Ii — Step-by-Step Visual Trace

#leetcode #algorithms #python #dynamicprogramming

Medium — Greedy | Array | Dynamic Programming

The Problem

Find the minimum number of jumps needed to reach the last index of an array, where each element represents the maximum jump length from that position.

Approach

Use a greedy algorithm that tracks the farthest reachable position and increments jumps only when reaching the end of the current jump range. This ensures we always make the optimal choice at each step by maximizing our reach before committing to the next jump.

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

Code

class Solution:
    def jump(self, nums: List[int]) -> int:
        jumps = 0
        cur_end = 0
        farthest_reachable = 0

        for i in range(len(nums) - 1):
            farthest_reachable = max(farthest_reachable, i + nums[i])
            if i == cur_end:
                jumps += 1
                cur_end = farthest_reachable

        return jumps