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

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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

Comments