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

👁 Watch the algorithm run step by step

👁 Watch the algorithm run step by step

Open interactive visualization

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

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