Jump Game II - Greedy Range Expansion

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approaches
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

Input guarantees that the end is reachable.

Example 1:
Input: [2,3,1,1,4]
Output: 2

Example 2:
Input: [2,3,0,1,4]
Output: 2

🎯 Real-World Analogy

Level-by-Level Network Coverage

Treat each jump count as a layer. Within current layer [start,end], compute farthest index reachable by one more jump. Then move to next layer.

💡 Key Insights

Greedy works by taking best reachable frontier per layer.
When index reaches current boundary, one jump is committed.
Track farthest seen in current layer.
Equivalent to BFS on implicit graph, but O(1) extra space.

💻 Solution Approaches

Approach 1: DP (Too Slow)

Time: O(N²) | Space: O(N)

Approach 2: Greedy Layer Sweep (Recommended)

Time: O(N) | Space: O(1)

Python Implementation

from typing import List


def jump(nums: List[int]) -> int:
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

JavaScript Implementation

function jump(nums) {
  let jumps = 0;
  let currentEnd = 0;
  let farthest = 0;

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);

    if (i === currentEnd) {
      jumps += 1;
      currentEnd = farthest;
    }
  }

  return jumps;
}

🔍 Step-by-Step Walkthrough

Trace [2,3,1,1,4]:

i=0 -> farthest=2, boundary hit -> jumps=1, currentEnd=2
i=1 -> farthest=4
i=2 -> farthest=4, boundary hit -> jumps=2, currentEnd=4
Reached/passed last index in 2 jumps.

⚡ Complexity Analysis

Time: O(N), one pass through indices.

Space: O(1), only counters and boundaries.

🔧 Edge Cases

Single element -> 0 jumps
Large first jump reaching end immediately
Zeros inside array but still reachable
Monotonic small steps

🧪 Test Cases

Python

def test_jump():
    assert jump([2,3,1,1,4]) == 2
    assert jump([2,3,0,1,4]) == 2
    assert jump([0]) == 0
    assert jump([1,1,1,1]) == 3

    print("✅ all tests passed")

JavaScript

function testJump() {
  console.assert(jump([2,3,1,1,4]) === 2, "test 1");
  console.assert(jump([2,3,0,1,4]) === 2, "test 2");
  console.assert(jump([0]) === 0, "test 3");

  console.log("✅ all tests passed");
}

💼 Interview Tips

Frame as BFS layers on an implicit graph.
Explain why committing jump at boundary is optimal.
Distinguish from Jump Game I (reachability only).

🎓 Key Takeaways

Greedy frontier expansion gives minimal jumps in linear time.
Boundary and farthest pointers are the core invariant pair.

← Back to All Algorithms