Jump Game II

TIP103 Unit 9 Session 1 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Arrays, Greedy Algorithms, Breadth-First Search (BFS) Intuition

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does nums[i] represent?

  • A: The maximum number of steps you can jump forward from index i. You may jump any distance from 1 up to nums[i].

• Q: Are we guaranteed that the last index can be reached?

  • A: Yes, the problem states we can assume the last index is always reachable, so we never need to handle an "impossible" case.

• Q: What should we return if the array has only one element?

  • A: We start at index 0, which is already the last index, so the answer is 0 jumps.

HAPPY CASE
Input: nums = [2, 3, 1, 1, 4]
Output: 2
Explanation: Jump 1 step from index 0 to index 1, then 3 steps from index 1 to the last index.

Input: nums = [2, 3, 0, 1, 4]
Output: 2
Explanation: Jump from index 0 to index 1, then from index 1 straight to the last index.

EDGE CASE
Input: nums = [0]
Output: 0
Explanation: We start at the last index, so no jumps are needed.

Input: nums = [1, 1, 1, 1]
Output: 3
Explanation: Every jump can only advance one step, so it takes 3 jumps to reach the last index.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Minimum Steps / Reachability Problems on an array, we can consider the following approaches:

• Greedy (Jump Ranges): At each "level" of jumps, track the farthest index reachable. When we exhaust the current level's range, take one more jump and extend to the new farthest point.
• BFS Intuition: Each jump count defines a "layer" of reachable indices, just like levels in a breadth-first search. The greedy solution is an implicit BFS over index ranges.
• Dynamic Programming: Compute the minimum jumps to reach each index, but this costs O(N^2) and is unnecessary here since the greedy approach is optimal.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Sweep the array once while tracking two boundaries: current_end, the farthest index reachable with the jumps taken so far, and farthest, the farthest index reachable if we take one more jump. Whenever the sweep reaches current_end, we are forced to take another jump, so we increment the jump count and extend current_end to farthest.

1) Initialize `jumps = 0`, `current_end = 0`, and `farthest = 0`.
2) Iterate over each index `i` from 0 up to (but not including) the last index:
   a) Update `farthest = max(farthest, i + nums[i])`.
   b) If `i == current_end`, we have used up the current jump's range:
      i)  Increment `jumps`.
      ii) Set `current_end = farthest`.
3) Return `jumps`.

⚠️ Common Mistakes

• Iterating all the way through the last index, which can add a phantom extra jump when the last index sits exactly on the current boundary.
• Incrementing jumps every time farthest grows instead of only when the sweep reaches current_end.
• Jumping greedily to i + nums[i] from each position instead of choosing the position within the current range that reaches farthest.
• Forgetting that a single-element array needs 0 jumps.

4: I-mplement

Implement the code to solve the algorithm.

def jump(nums):
    jumps = 0          # Total jumps taken so far
    current_end = 0    # Farthest index reachable with the current number of jumps
    farthest = 0       # Farthest index reachable with one more jump

    # We never need to jump FROM the last index, so stop before it
    for i in range(len(nums) - 1):
        # Track the farthest index reachable from any position seen so far
        farthest = max(farthest, i + nums[i])

        # If we've reached the end of the current jump's range, we must jump again
        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: nums = [2, 3, 1, 1, 4]

  • i = 0: farthest = 2; i == current_end (0), so jumps = 1, current_end = 2.
  • i = 1: farthest = max(2, 1 + 3) = 4.
  • i = 2: farthest = 4; i == current_end (2), so jumps = 2, current_end = 4.
  • i = 3: farthest stays 4; loop ends before the last index.
  • Output: 2

• Input: nums = [2, 3, 0, 1, 4]

  • i = 0: farthest = 2; i == current_end (0), so jumps = 1, current_end = 2.
  • i = 1: farthest = max(2, 1 + 3) = 4.
  • i = 2: farthest = 4; i == current_end (2), so jumps = 2, current_end = 4.
  • i = 3: farthest = max(4, 3 + 1) = 4; loop ends.
  • Output: 2

• Input: nums = [0]

  • The loop body never runs since there is only one index.
  • Output: 0

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the length of the nums array.

• Time Complexity: O(N) because we make a single pass over the array, doing constant work per index.
• Space Complexity: O(1) because we only use three integer variables regardless of input size.