medium Jump Game II

Problem Statement

You are given an array nums containing n integers, where nums[i] represents the maximum length of a forward jump you can make from index i. You are initially positioned at nums[0].

Return the minimum number of jumps needed to reach from the start to the end of the array.

Examples

Example 1:

• Input: nums = [2, 3, 2, 2, 1]
• Expected Output: 2
• Justification: Start at index 0 and jump to index 1 (jump size 1). Then, jump from index 1 to the end (jump size 3).

Example 2:

• Input: nums = [1, 2, 3, 4, 5]
• Expected Output: 3
• Justification: Start at index 0, jump to index 1 (jump size 1). Then, jump to index 3 (jump size 2). Finally, jump to the end (jump size 2).

Example 3:

• Input: nums = [2, 3, 1, 2, 4, 1]
• Expected Output: 3
• Justification: Start at index 0, jump to index 1 (jump size 1). Then, jump to index 4 (jump size 2). Finally, jump to the end (jump size 1).

Constraints:

• 1 <= nums.length <= 10⁴
• 0 <= nums[i] <= 1000
• It's guaranteed that you can reach nums[n - 1].

Solution

To solve this problem, we need to keep track of the farthest point we can reach with each jump and count how many jumps we need. The strategy is to iterate through the array while updating the farthest point we can reach. Whenever we reach the end of the current jump range, we increment our jump count and update the current jump range to the farthest point we can reach. This method ensures that we use the fewest jumps possible to get to the end.

This approach works effectively because it uses a greedy algorithm to always make the optimal choice at each step. By focusing on the farthest reachable point, we minimize the number of jumps needed.

Step-by-Step Algorithm

1. Initialize Variables:

   • Create a variable jumps and set it to 0. This will count the number of jumps needed.
   • Create a variable currentEnd and set it to 0. This will mark the end of the range for the current jump.
   • Create a variable farthest and set it to 0. This will track the farthest point that can be reached.

2. Loop Through the Array:

   • Iterate through the array from the first element to the second-to-last element (from index 0 to n-2):
     • Update farthest to be the maximum of farthest and the current index plus the jump length at that index (farthest = max(farthest, i + nums[i])).
     • If the current index is equal to currentEnd:
       • Increment the jumps count (jumps++).
       • Update currentEnd to be farthest (currentEnd = farthest).

3. Return Result:

   • After the loop ends, return the value of jumps as the result.

Algorithm Walkthrough

Using the input nums = [2, 3, 1, 2, 4, 1].

Initialization:

• jumps = 0
• currentEnd = 0
• farthest = 0

Iteration 1:

• Index i = 0
  • farthest = max(0, 0 + 2) = 2
  • Since i == currentEnd (0 == 0):
    • jumps++ (jumps = 1)
    • currentEnd = farthest (currentEnd = 2)

Iteration 2:

• Index i = 1
  • farthest = max(2, 1 + 3) = 4
  • i != currentEnd (1 != 2), so do nothing

Iteration 3:

• Index i = 2
  • farthest = max(4, 2 + 1) = 4
  • Since i == currentEnd (2 == 2):
    • jumps++ (jumps = 2)
    • currentEnd = farthest (currentEnd = 4)

Iteration 4:

• Index i = 3
  • farthest = max(4, 3 + 2) = 5
  • i != currentEnd (3 != 4), so do nothing

Iteration 5:

• Index i = 4
  • farthest = max(5, 4 + 4) = 8
  • Since i == currentEnd (4 == 4):
    • jumps++ (jumps = 3)
    • currentEnd = farthest (currentEnd = 8)

Return Result:

• Return jumps which is 3.

Code

public class Solution {

  public int jump(int[] nums) {
    int jumps = 0; // To count the number of jumps
    int currentEnd = 0; // To mark the end of the range for the current jump
    int farthest = 0; // To mark the farthest point that can be reached

    // Loop through the array
    for (int i = 0; i < nums.length - 1; i++) {
      farthest = Math.max(farthest, i + nums[i]); // Update the farthest point
      if (i == currentEnd) { // If reached the end of the current jump range
        jumps++; // Increment jump count
        currentEnd = farthest; // Update the end of the range to the farthest point
      }
    }

    return jumps; // Return the number of jumps
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test examples
    int[] example1 = { 2, 3, 2, 2, 1 };
    int[] example2 = { 1, 2, 3, 4, 5 };
    int[] example3 = { 2, 3, 1, 2, 4, 1 };

    // Print the results
    System.out.println(solution.jump(example1)); // Expected Output: 2
    System.out.println(solution.jump(example2)); // Expected Output: 3
    System.out.println(solution.jump(example3)); // Expected Output: 3
  }
}

Complexity Analysis

• Time Complexity: The algorithm runs in time, where n is the length of the array. This is because we iterate through the array once, and each operation inside the loop (like updating the farthest point) takes constant time.
• Space Complexity: The algorithm uses additional space since we are only using a few extra variables (jumps, currentEnd, and farthest) regardless of the input size.

Pattern Transfer — GREEDY FARTHEST-REACH as BFS LAYERS (Jump II)

Pattern: treat indices as an unweighted graph; each jump is a BFS layer. currentEnd is the layer boundary; farthest is the farthest reach discoverable in this layer; when i hits currentEnd, start a new jump.

Template:

jumps = 0
end = 0
far = 0
for i in 0 .. n-2:          # last index needs no outbound jump
  far = max(far, i + nums[i])
  if i == end:
    jumps += 1
    end = far
return jumps

Assumption: the end is reachable (LeetCode 45 style). If not guaranteed, run Jump I first or detect when end cannot advance.

When NOT: only reachability → Jump I (simpler loop). Weighted jumps → Dijkstra/DP. Naive DP min-jumps O(n²).

Complexity: one pass over n−1 indices → Θ(n) time, O(1) space.

Verified walkthrough: [2,3,1,2,4,1] layer ends 0→2→4→≥5, jumps=3 (no 2-jump path to last index).

Edge hand-runs

• [1]: loop range 0..−1 empty → jumps 0. Explains loop bound n-2: last index never needs an outbound jump.
• [1,1,1] → 2.

Drill: Why is this BFS shortest path without a queue? (Each layer’s frontier is the contiguous index range (prevEnd, end].)