loading

45. Jump Game II — Step-by-Step Visualization

mediumLeetCode #45ArrayDynamic ProgrammingGreedy

You are given a **0-indexed** array of integers `nums` of length `n`. You are initially positioned at `nums[0]`. Each element `nums[i]` represents the maximum length of a forward jump from index `i`. In other words, if you are at index `i`, you can jump to any index `i + j` where: - `0 <= j <= nums[i]` - `i + j < n` Return the minimum number of jumps to reach index `n - 1`. The test cases are generated such that you can reach index `n - 1`. **Example 1:** Input: `nums = [2,3,1,1,4]` Output: `2` Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index. **Example 2:** Input: `nums = [2,3,0,1,4]` Output: `2`

Algorithm Pattern

Greedy / Level-by-Level Exploration (BFS)

Key Idea

We can think of this as finding the minimum number of 'jump levels' to reach the end. At each jump level, we maintain a reachable range `[l, r]` and find the farthest index we can reach from anywhere within that range for the next level.

Step-by-Step Approach

  1. Initialize `jumps = 0`, `l = 0`, and `r = 0`.
  2. While the current range `r` has not reached the last index:
  3. 1. Scan every index `i` from `l` to `r`.
  4. 2. Calculate the maximum reachable index from `i`: `i + nums[i]`.
  5. 3. Update `farthest = max(farthest, i + nums[i])`.
  6. 4. Once the scan is complete, 'leap' to the next level: `l = r + 1`, `r = farthest`, and `jumps += 1`.
  7. Return the total jumps.

Common Gotchas

  • The greedy property works because reaching any index in a later level will always take more jumps than reaching any index in an earlier level.
  • The scan must cover the *entire* current range to find the best possible launchpad for the next jump.

Related Problems

← All problems