Common Greedy Patterns - Learning Module

Loading content...

0/276

Jump Game Variations

The Array Traversal Challenge

Imagine standing at the beginning of an array. Each element tells you the maximum distance you can jump forward from that position. Your goal: reach the end. Can you make it?

This simple premise—the Jump Game—has become one of the most instructive greedy problem families in algorithm design. It tests your ability to think about reachability, resource management, and optimization in a clean, abstract setting.

What makes jump games fascinating is their layered complexity. The basic "can you reach the end?" question yields to "what's the minimum number of jumps?" which extends to variations involving costs, backward jumps, and circular arrays. Each variation teaches a new facet of greedy reasoning.

What You Will Learn

By the end of this page, you will master the jump game family: the basic reachability problem, the minimum jumps optimization, the greedy interval extension technique, multiple variations, and the pattern recognition skills to handle novel jump-style problems.

Jump Game I: Can You Reach the End?

Problem Statement (LeetCode #55):

Input: An array nums of non-negative integers where nums[i] represents the maximum jump length from position i.

Output: Return true if you can reach the last index starting from index 0, otherwise false.

Constraints:

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵

Examples:

nums = [2, 3, 1, 1, 4]

Positions:  0   1   2   3   4
Values:     2   3   1   1   4

From 0: can jump to 1 or 2
From 1: can jump to 2, 3, or 4 ✓

Answer: true (0 → 1 → 4)

nums = [3, 2, 1, 0, 4]

Positions:  0   1   2   3   4
Values:     3   2   1   0   4

From 0: can reach up to index 3
From 1: can reach up to index 3
From 2: can reach up to index 3
From 3: can only stay at 3 (value is 0)

Index 3 is a dead end - can never reach index 4.
Answer: false

The Greedy Insight

Track the farthest position we can reach. As we iterate through the array, if we're ever at a position beyond our reach, we're stuck. If our reach extends to or past the last index, we can make it.

jump_game_1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from typing import List
 
def can_jump(nums: List[int]) -> bool:
    """
    Determine if you can reach the last index.
    
    Greedy approach: track the farthest reachable position.
    Time: O(n), Space: O(1)
    """
    n = len(nums)
    max_reach = 0  # Farthest position we can reach
    
    for i in range(n):
        # If current position is beyond our reach, we're stuck
        if i > max_reach:
            return False
        
        # Update farthest reachable position
        max_reach = max(max_reach, i + nums[i])
        
        # Early exit: if we can already reach the end
        if max_reach >= n - 1:
            return True
    
    return True  # Made it through the array
 
 
def can_jump_verbose(nums: List[int]) -> bool:
    """Same algorithm with detailed tracing."""
    n = len(nums)
    max_reach = 0
    
    print(f"\nJump Game I: {nums}")
    print("=" * 50)
    print(f"{'i':>3} | {'nums[i]':>7} | {'i+nums[i]':>9} | {'max_reach':>9} | Status")
    print("-" * 50)
    
    for i in range(n):
        if i > max_reach:
            print(f"{i:>3} | {nums[i]:>7} | {'-':>9} | {max_reach:>9} | STUCK!")
            return False
        
        old_reach = max_reach
        max_reach = max(max_reach, i + nums[i])
        update = "↑" if max_reach > old_reach else "-"
        
        print(f"{i:>3} | {nums[i]:>7} | {i+nums[i]:>9} | {max_reach:>9} | {update}")
        
        if max_reach >= n - 1:
            print("-" * 50)
            print(f"✓ Can reach end (index {n-1}) from position {i}")
            return True
    
    return True
 
 
# Test cases
can_jump_verbose([2, 3, 1, 1, 4])  # True
can_jump_verbose([3, 2, 1, 0, 4])  # False

Why This Works:

The greedy strategy maintains an invariant: max_reach is the farthest index reachable using positions 0 to i-1. When we visit position i:

If i > max_reach, position i is unreachable—we've hit a gap
Otherwise, we can extend max_reach to i + nums[i] (potentially)
If max_reach ever reaches the last index, we're done

Complexity:

Time: O(n) — single pass through the array
Space: O(1) — only one variable (max_reach)

Jump Game II: Minimum Jumps to Reach End

Problem Statement (LeetCode #45):

Input: An array nums of non-negative integers. You start at index 0 and the problem guarantees you can always reach the last index.

Output: Return the minimum number of jumps needed to reach the last index.

Key Difference from Jump Game I:

We're not just checking reachability—we're optimizing jump count
The problem guarantees a solution exists

Example:

nums = [2, 3, 1, 1, 4]

Positions:  0   1   2   3   4
Values:     2   3   1   1   4

Option 1: 0 → 1 → 4 (2 jumps)
Option 2: 0 → 2 → 3 → 4 (3 jumps)

Minimum: 2 jumps

The BFS Intuition

Think of this as finding the shortest path in an unweighted graph where each index i has edges to indices i+1, i+2, ..., i+nums[i]. BFS would give O(n + edges), but edges can be O(n²). The greedy approach exploits the structure for O(n).

The Greedy Approach: Level-by-Level Expansion

Imagine the array as levels of a BFS tree:

Level 0: index 0 (starting position)
Level 1: all indices reachable in 1 jump from level 0
Level 2: all indices reachable in 1 jump from level 1 (but not already in level 0 or 1)
etc.

The key insight: we can compute each level's boundary without explicitly tracking all indices.

Algorithm:

MINIMUM-JUMPS(nums):
    n = length(nums)
    jumps = 0
    current_end = 0      // End of current level
    farthest = 0         // Farthest we can reach
    
    FOR i = 0 TO n-2:    // Don't need to jump from last index
        farthest = max(farthest, i + nums[i])
        
        IF i == current_end:
            // Must take a jump to continue
            jumps += 1
            current_end = farthest
            
            // Early exit if already reached
            IF current_end >= n-1:
                BREAK
    
    RETURN jumps

jump_game_2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def jump(nums: List[int]) -> int:
    """
    Find minimum number of jumps to reach the last index.
    
    Greedy BFS-like approach: expand level by level.
    Time: O(n), Space: O(1)
    """
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0    # End boundary of current jump level
    farthest = 0       # Farthest reachable position seen so far
    
    for i in range(n - 1):  # Don't process last index
        # Update farthest reachable from any position in current level
        farthest = max(farthest, i + nums[i])
        
        # When we reach the end of current level, we must jump
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # Early termination
            if current_end >= n - 1:
                break
    
    return jumps
 
 
def jump_verbose(nums: List[int]) -> int:
    """Same algorithm with detailed level-by-level visualization."""
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    print(f"\nMinimum Jumps: {nums}")
    print("=" * 60)
    
    for i in range(n - 1):
        old_farthest = farthest
        farthest = max(farthest, i + nums[i])
        
        if i == current_end:
            jumps += 1
            print(f"\nLevel {jumps}:")
            print(f"  Positions in this level: indices up to {current_end}")
            print(f"  Farthest reachable after this level: {farthest}")
            current_end = farthest
            
            if current_end >= n - 1:
                print(f"  ✓ Reached last index!")
                break
    
    print(f"\nTotal jumps: {jumps}")
    return jumps
 
 
# Example
jump_verbose([2, 3, 1, 1, 4])

Visual Trace:

nums = [2, 3, 1, 1, 4]
       i=0  1  2  3  4

Level 0: [0]
  From index 0, can reach up to index 0+2=2
  
Level 1: [1, 2]  (indices reachable from level 0)
  From index 1, can reach up to 1+3=4
  From index 2, can reach up to 2+1=3
  Farthest: 4 (reaches the end!)

Total: 2 jumps

Why We Stop at n-2:

We iterate up to index n-2 because:

If we're at index n-1 (last index), we don't need another jump
The condition i == current_end at n-1 would incorrectly count an extra jump

Correctness Analysis

Let's rigorously prove why the greedy approach works for minimum jumps.

Greedy Choice Property

At each jump, choosing to extend as far as possible (implicitly, by tracking farthest) is always part of some optimal solution.

Proof Sketch:

Suppose the greedy algorithm makes k jumps, landing at indices j₁, j₂, ..., jₖ (with jₖ ≥ n-1).

Consider any optimal solution that makes k' jumps. We'll show k ≤ k'.

Key Observation: The greedy algorithm maximizes the "reach" at each level. If after jump i the greedy reach is gᵢ, and any optimal solution's reach after jump i is oᵢ, then gᵢ ≥ oᵢ.

Induction:

Base: After 0 jumps, both start at index 0. g₀ = o₀ = 0. ✓

Inductive Step: Assume gᵢ ≥ oᵢ. After jump i+1:

Greedy extends to gᵢ₊₁ = max{j + nums[j] : j ≤ gᵢ}
Optimal extends to oᵢ₊₁ = max{j + nums[j] : j ≤ oᵢ} (at best; it might choose a suboptimal jump)

Since gᵢ ≥ oᵢ, the greedy has access to all positions optimal has, plus potentially more. Therefore gᵢ₊₁ ≥ oᵢ₊₁. ✓

Conclusion: Greedy reaches at least as far as any solution with the same number of jumps. Thus, greedy uses the minimum number of jumps. ∎

The Implicit Choice

The greedy algorithm doesn't explicitly choose which index to jump to—it only tracks how far we can reach. This is a powerful pattern: optimize the reach, and the actual path will take care of itself.

Jump Game Variations

Several important variations test different aspects of the jump game concept:

Variation 1: Jump Game III — Can Reach Zero (LeetCode #1306)

You can jump forward OR backward. From index i, you can jump to i + nums[i] or i - nums[i]. Goal: determine if you can reach any index with value 0.

Approach: This is a graph traversal problem (BFS or DFS), not greedy, because you can move in both directions and need to track visited nodes.

jump_game_3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def can_reach_zero(nums: List[int], start: int) -> bool:
    """
    Jump Game III: Can reach an index with value 0?
    Can jump forward or backward by nums[i].
    
    BFS approach (not greedy).
    Time: O(n), Space: O(n)
    """
    from collections import deque
    
    n = len(nums)
    visited = [False] * n
    queue = deque([start])
    visited[start] = True
    
    while queue:
        i = queue.popleft()
        
        if nums[i] == 0:
            return True
        
        for next_i in [i + nums[i], i - nums[i]]:
            if 0 <= next_i < n and not visited[next_i]:
                visited[next_i] = True
                queue.append(next_i)
    
    return False

Variation 2: Jump Game IV — Minimum Jumps with Same Value Portals (LeetCode #1345)

In addition to jumping to adjacent indices (i-1 or i+1), you can teleport to any index j where nums[j] == nums[i].

Approach: BFS with a twist—precompute indices for each value. Remove indices from the "portal list" after visiting to avoid reprocessing.

Variation 3: Jump Game V — Decreasing Height Jumps (LeetCode #1340)

You can jump from index i to any index j if:

i - d ≤ j ≤ i + d (within d positions)
arr[i] > arr[j] (jumping to strictly smaller values)
All intermediate elements between i and j are also smaller than arr[i]

Approach: Dynamic programming with sorting by height, or recursive DP with memoization.

Variation 4: Jump Game VI — Maximum Score (LeetCode #1696)

Each index has a score (can be negative). From index i, you can jump to any index in [i+1, i+k]. Maximize total score to reach the end.

Approach: DP with monotonic deque for O(n) optimization. The greedy principle alone doesn't work because scores can be negative.

Jump Game Family Summary
Problem	Goal	Direction	Approach	Complexity
Jump Game I	Reach end?	Forward only	Greedy (max reach)	O(n)
Jump Game II	Min jumps	Forward only	Greedy (BFS-like)	O(n)
Jump Game III	Reach zero?	Both directions	BFS/DFS	O(n)
Jump Game IV	Min jumps with portals	Adjacent + portals	BFS + optimization	O(n)
Jump Game V	Max visitable indices	Both, constraints	DP	O(n × d)
Jump Game VI	Max score	Forward, k range	DP + mono deque	O(n)

Implementation Patterns and Tricks

Several implementation patterns recur across jump games:

Common Implementation Patterns

•Max Reach Tracking: Maintain max_reach = max(max_reach, i + nums[i]) as you iterate.
•Level Boundaries: Use current_end to mark where the current "level" ends. When i reaches current_end, increment jumps and extend current_end to max_reach.
•Early Termination: Check if max_reach >= n - 1 to exit early.
•Off-by-One Awareness: Iterate to n-2 (not n-1) in minimum jumps to avoid counting an unnecessary final jump.
•Visited Set (for bidirectional): When jumps can go backward, use a visited array to prevent infinite loops.

jump_game_patterns.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def jump_game_template(nums: List[int], 
                         goal: str = "reach") -> Union[bool, int]:
    """
    Unified template for forward-only jump games.
    
    goal: "reach" for reachability, "count" for minimum jumps
    """
    n = len(nums)
    if n <= 1:
        return True if goal == "reach" else 0
    
    max_reach = 0
    current_end = 0 if goal == "count" else n  # sentinel for reach
    jumps = 0
    
    for i in range(n - (1 if goal == "count" else 0)):
        # Check if stuck (reachability)
        if goal == "reach" and i > max_reach:
            return False
        
        # Extend max reach
        max_reach = max(max_reach, i + nums[i])
        
        # Process level boundary (count mode)
        if goal == "count" and i == current_end:
            jumps += 1
            current_end = max_reach
        
        # Early exit
        if max_reach >= n - 1:
            return True if goal == "reach" else jumps
    
    return True if goal == "reach" else jumps
 
 
# Specialized versions derived from template
def can_reach_end(nums: List[int]) -> bool:
    """Jump Game I: Can reach the end?"""
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)
    return True
 
 
def min_jumps(nums: List[int]) -> int:
    """Jump Game II: Minimum jumps to reach end."""
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    max_reach = 0
    
    for i in range(n - 1):
        max_reach = max(max_reach, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = max_reach
            if current_end >= n - 1:
                break
    
    return jumps

Common Mistakes and Pitfalls

Common Mistakes

•Off-by-one errors: Iterating to n instead of n-1 in min jumps
•Forgetting early exit: Not breaking when max_reach ≥ n-1
•Wrong loop bound: Using n-1 for reachability (should be n)
•Confusing problems: Applying min-jumps logic to reachability
•Not handling n=1: Special case where answer is 0 or True

Best Practices

•Clarify which problem: Reachability vs. min jumps
•Handle edge case n=1 first: Return early
•Use descriptive variable names: max_reach, current_end, jumps
•Trace through small examples: Verify logic manually
•Test the 0-heavy cases: [0], [1,0], [0,1]

The nums[i] = 0 Trap

A 0 in the array creates a "dead end"—you can't jump forward from that position. The algorithm handles this naturally: if you're forced to land on a 0 and can't reach beyond it, max_reach won't extend. Always test with arrays containing zeros.

Interview Perspective

Jump games are interview staples. Here's how to approach them systematically:

Interview Strategy

•Clarify the problem: Reachability? Min jumps? Bidirectional? Costs?
•Identify the type: Forward-only → likely greedy. Bidirectional or complex costs → BFS/DP.
•State the approach: "I'll track the farthest position I can reach as I iterate."
•Handle edge cases first: Empty array, single element, all zeros.
•Walk through an example: Trace your algorithm on the given example.
•Analyze complexity: O(n) time, O(1) space for basic variants.

Interview Script for Jump Game I

"I'll use a greedy approach: iterate through the array while tracking the farthest index I can reach. If I'm ever at an index beyond my reach, I'm stuck and return false. Otherwise, if my reach includes the last index, I return true. This is O(n) time and O(1) space."

Interview Script for Jump Game II

"For minimum jumps, I'll think of it like BFS levels. I track the end of the current level and the farthest I can reach within this level. When I hit the current level's end, I 'jump' to the next level and update the boundary. This gives the minimum number of jumps in O(n) time."

Jump Game Variations

The Array Traversal Challenge

Imagine standing at the beginning of an array. Each element tells you the maximum distance you can jump forward from that position. Your goal: reach the end. Can you make it?

What You Will Learn

Jump Game I: Can You Reach the End?

Problem Statement (LeetCode #55):

Input: An array nums of non-negative integers where nums[i] represents the maximum jump length from position i.

Output: Return true if you can reach the last index starting from index 0, otherwise false.

Constraints:

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁵

Examples:

nums = [2, 3, 1, 1, 4]

Positions:  0   1   2   3   4
Values:     2   3   1   1   4

From 0: can jump to 1 or 2
From 1: can jump to 2, 3, or 4 ✓

Answer: true (0 → 1 → 4)

nums = [3, 2, 1, 0, 4]

Positions:  0   1   2   3   4
Values:     3   2   1   0   4

From 0: can reach up to index 3
From 1: can reach up to index 3
From 2: can reach up to index 3
From 3: can only stay at 3 (value is 0)

Index 3 is a dead end - can never reach index 4.
Answer: false

The Greedy Insight

Track the farthest position we can reach. As we iterate through the array, if we're ever at a position beyond our reach, we're stuck. If our reach extends to or past the last index, we can make it.

jump_game_1.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from typing import List
 
def can_jump(nums: List[int]) -> bool:
    """
    Determine if you can reach the last index.
    
    Greedy approach: track the farthest reachable position.
    Time: O(n), Space: O(1)
    """
    n = len(nums)
    max_reach = 0  # Farthest position we can reach
    
    for i in range(n):
        # If current position is beyond our reach, we're stuck
        if i > max_reach:
            return False
        
        # Update farthest reachable position
        max_reach = max(max_reach, i + nums[i])
        
        # Early exit: if we can already reach the end
        if max_reach >= n - 1:
            return True
    
    return True  # Made it through the array
 
 
def can_jump_verbose(nums: List[int]) -> bool:
    """Same algorithm with detailed tracing."""
    n = len(nums)
    max_reach = 0
    
    print(f"\nJump Game I: {nums}")
    print("=" * 50)
    print(f"{'i':>3} | {'nums[i]':>7} | {'i+nums[i]':>9} | {'max_reach':>9} | Status")
    print("-" * 50)
    
    for i in range(n):
        if i > max_reach:
            print(f"{i:>3} | {nums[i]:>7} | {'-':>9} | {max_reach:>9} | STUCK!")
            return False
        
        old_reach = max_reach
        max_reach = max(max_reach, i + nums[i])
        update = "↑" if max_reach > old_reach else "-"
        
        print(f"{i:>3} | {nums[i]:>7} | {i+nums[i]:>9} | {max_reach:>9} | {update}")
        
        if max_reach >= n - 1:
            print("-" * 50)
            print(f"✓ Can reach end (index {n-1}) from position {i}")
            return True
    
    return True
 
 
# Test cases
can_jump_verbose([2, 3, 1, 1, 4])  # True
can_jump_verbose([3, 2, 1, 0, 4])  # False

Why This Works:

The greedy strategy maintains an invariant: max_reach is the farthest index reachable using positions 0 to i-1. When we visit position i:

If i > max_reach, position i is unreachable—we've hit a gap
Otherwise, we can extend max_reach to i + nums[i] (potentially)
If max_reach ever reaches the last index, we're done

Complexity:

Time: O(n) — single pass through the array
Space: O(1) — only one variable (max_reach)

Jump Game II: Minimum Jumps to Reach End

Problem Statement (LeetCode #45):

Input: An array nums of non-negative integers. You start at index 0 and the problem guarantees you can always reach the last index.

Output: Return the minimum number of jumps needed to reach the last index.

Key Difference from Jump Game I:

We're not just checking reachability—we're optimizing jump count
The problem guarantees a solution exists

Example:

nums = [2, 3, 1, 1, 4]

Positions:  0   1   2   3   4
Values:     2   3   1   1   4

Option 1: 0 → 1 → 4 (2 jumps)
Option 2: 0 → 2 → 3 → 4 (3 jumps)

Minimum: 2 jumps

The BFS Intuition

The Greedy Approach: Level-by-Level Expansion

Imagine the array as levels of a BFS tree:

Level 0: index 0 (starting position)
Level 1: all indices reachable in 1 jump from level 0
Level 2: all indices reachable in 1 jump from level 1 (but not already in level 0 or 1)
etc.

The key insight: we can compute each level's boundary without explicitly tracking all indices.

Algorithm:

MINIMUM-JUMPS(nums):
    n = length(nums)
    jumps = 0
    current_end = 0      // End of current level
    farthest = 0         // Farthest we can reach
    
    FOR i = 0 TO n-2:    // Don't need to jump from last index
        farthest = max(farthest, i + nums[i])
        
        IF i == current_end:
            // Must take a jump to continue
            jumps += 1
            current_end = farthest
            
            // Early exit if already reached
            IF current_end >= n-1:
                BREAK
    
    RETURN jumps

jump_game_2.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def jump(nums: List[int]) -> int:
    """
    Find minimum number of jumps to reach the last index.
    
    Greedy BFS-like approach: expand level by level.
    Time: O(n), Space: O(1)
    """
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0    # End boundary of current jump level
    farthest = 0       # Farthest reachable position seen so far
    
    for i in range(n - 1):  # Don't process last index
        # Update farthest reachable from any position in current level
        farthest = max(farthest, i + nums[i])
        
        # When we reach the end of current level, we must jump
        if i == current_end:
            jumps += 1
            current_end = farthest
            
            # Early termination
            if current_end >= n - 1:
                break
    
    return jumps
 
 
def jump_verbose(nums: List[int]) -> int:
    """Same algorithm with detailed level-by-level visualization."""
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    farthest = 0
    
    print(f"\nMinimum Jumps: {nums}")
    print("=" * 60)
    
    for i in range(n - 1):
        old_farthest = farthest
        farthest = max(farthest, i + nums[i])
        
        if i == current_end:
            jumps += 1
            print(f"\nLevel {jumps}:")
            print(f"  Positions in this level: indices up to {current_end}")
            print(f"  Farthest reachable after this level: {farthest}")
            current_end = farthest
            
            if current_end >= n - 1:
                print(f"  ✓ Reached last index!")
                break
    
    print(f"\nTotal jumps: {jumps}")
    return jumps
 
 
# Example
jump_verbose([2, 3, 1, 1, 4])

Visual Trace:

nums = [2, 3, 1, 1, 4]
       i=0  1  2  3  4

Level 0: [0]
  From index 0, can reach up to index 0+2=2
  
Level 1: [1, 2]  (indices reachable from level 0)
  From index 1, can reach up to 1+3=4
  From index 2, can reach up to 2+1=3
  Farthest: 4 (reaches the end!)

Total: 2 jumps

Why We Stop at n-2:

We iterate up to index n-2 because:

If we're at index n-1 (last index), we don't need another jump
The condition i == current_end at n-1 would incorrectly count an extra jump

Correctness Analysis

Let's rigorously prove why the greedy approach works for minimum jumps.

Greedy Choice Property

At each jump, choosing to extend as far as possible (implicitly, by tracking farthest) is always part of some optimal solution.

Proof Sketch:

Suppose the greedy algorithm makes k jumps, landing at indices j₁, j₂, ..., jₖ (with jₖ ≥ n-1).

Consider any optimal solution that makes k' jumps. We'll show k ≤ k'.

Key Observation: The greedy algorithm maximizes the "reach" at each level. If after jump i the greedy reach is gᵢ, and any optimal solution's reach after jump i is oᵢ, then gᵢ ≥ oᵢ.

Induction:

Base: After 0 jumps, both start at index 0. g₀ = o₀ = 0. ✓

Inductive Step: Assume gᵢ ≥ oᵢ. After jump i+1:

Greedy extends to gᵢ₊₁ = max{j + nums[j] : j ≤ gᵢ}
Optimal extends to oᵢ₊₁ = max{j + nums[j] : j ≤ oᵢ} (at best; it might choose a suboptimal jump)

Since gᵢ ≥ oᵢ, the greedy has access to all positions optimal has, plus potentially more. Therefore gᵢ₊₁ ≥ oᵢ₊₁. ✓

Conclusion: Greedy reaches at least as far as any solution with the same number of jumps. Thus, greedy uses the minimum number of jumps. ∎

The Implicit Choice

Jump Game Variations

Several important variations test different aspects of the jump game concept:

Variation 1: Jump Game III — Can Reach Zero (LeetCode #1306)

You can jump forward OR backward. From index i, you can jump to i + nums[i] or i - nums[i]. Goal: determine if you can reach any index with value 0.

Approach: This is a graph traversal problem (BFS or DFS), not greedy, because you can move in both directions and need to track visited nodes.

jump_game_3.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def can_reach_zero(nums: List[int], start: int) -> bool:
    """
    Jump Game III: Can reach an index with value 0?
    Can jump forward or backward by nums[i].
    
    BFS approach (not greedy).
    Time: O(n), Space: O(n)
    """
    from collections import deque
    
    n = len(nums)
    visited = [False] * n
    queue = deque([start])
    visited[start] = True
    
    while queue:
        i = queue.popleft()
        
        if nums[i] == 0:
            return True
        
        for next_i in [i + nums[i], i - nums[i]]:
            if 0 <= next_i < n and not visited[next_i]:
                visited[next_i] = True
                queue.append(next_i)
    
    return False

Variation 2: Jump Game IV — Minimum Jumps with Same Value Portals (LeetCode #1345)

In addition to jumping to adjacent indices (i-1 or i+1), you can teleport to any index j where nums[j] == nums[i].

Approach: BFS with a twist—precompute indices for each value. Remove indices from the "portal list" after visiting to avoid reprocessing.

Variation 3: Jump Game V — Decreasing Height Jumps (LeetCode #1340)

You can jump from index i to any index j if:

i - d ≤ j ≤ i + d (within d positions)
arr[i] > arr[j] (jumping to strictly smaller values)
All intermediate elements between i and j are also smaller than arr[i]

Approach: Dynamic programming with sorting by height, or recursive DP with memoization.

Variation 4: Jump Game VI — Maximum Score (LeetCode #1696)

Each index has a score (can be negative). From index i, you can jump to any index in [i+1, i+k]. Maximize total score to reach the end.

Approach: DP with monotonic deque for O(n) optimization. The greedy principle alone doesn't work because scores can be negative.

Jump Game Family Summary
Problem	Goal	Direction	Approach	Complexity
Jump Game I	Reach end?	Forward only	Greedy (max reach)	O(n)
Jump Game II	Min jumps	Forward only	Greedy (BFS-like)	O(n)
Jump Game III	Reach zero?	Both directions	BFS/DFS	O(n)
Jump Game IV	Min jumps with portals	Adjacent + portals	BFS + optimization	O(n)
Jump Game V	Max visitable indices	Both, constraints	DP	O(n × d)
Jump Game VI	Max score	Forward, k range	DP + mono deque	O(n)

Implementation Patterns and Tricks

Several implementation patterns recur across jump games:

Common Implementation Patterns

•Max Reach Tracking: Maintain max_reach = max(max_reach, i + nums[i]) as you iterate.
•Level Boundaries: Use current_end to mark where the current "level" ends. When i reaches current_end, increment jumps and extend current_end to max_reach.
•Early Termination: Check if max_reach >= n - 1 to exit early.
•Off-by-One Awareness: Iterate to n-2 (not n-1) in minimum jumps to avoid counting an unnecessary final jump.
•Visited Set (for bidirectional): When jumps can go backward, use a visited array to prevent infinite loops.

jump_game_patterns.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def jump_game_template(nums: List[int], 
                         goal: str = "reach") -> Union[bool, int]:
    """
    Unified template for forward-only jump games.
    
    goal: "reach" for reachability, "count" for minimum jumps
    """
    n = len(nums)
    if n <= 1:
        return True if goal == "reach" else 0
    
    max_reach = 0
    current_end = 0 if goal == "count" else n  # sentinel for reach
    jumps = 0
    
    for i in range(n - (1 if goal == "count" else 0)):
        # Check if stuck (reachability)
        if goal == "reach" and i > max_reach:
            return False
        
        # Extend max reach
        max_reach = max(max_reach, i + nums[i])
        
        # Process level boundary (count mode)
        if goal == "count" and i == current_end:
            jumps += 1
            current_end = max_reach
        
        # Early exit
        if max_reach >= n - 1:
            return True if goal == "reach" else jumps
    
    return True if goal == "reach" else jumps
 
 
# Specialized versions derived from template
def can_reach_end(nums: List[int]) -> bool:
    """Jump Game I: Can reach the end?"""
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)
    return True
 
 
def min_jumps(nums: List[int]) -> int:
    """Jump Game II: Minimum jumps to reach end."""
    n = len(nums)
    if n <= 1:
        return 0
    
    jumps = 0
    current_end = 0
    max_reach = 0
    
    for i in range(n - 1):
        max_reach = max(max_reach, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = max_reach
            if current_end >= n - 1:
                break
    
    return jumps

Common Mistakes and Pitfalls

Common Mistakes

•Off-by-one errors: Iterating to n instead of n-1 in min jumps
•Forgetting early exit: Not breaking when max_reach ≥ n-1
•Wrong loop bound: Using n-1 for reachability (should be n)
•Confusing problems: Applying min-jumps logic to reachability
•Not handling n=1: Special case where answer is 0 or True

Best Practices

•Clarify which problem: Reachability vs. min jumps
•Handle edge case n=1 first: Return early
•Use descriptive variable names: max_reach, current_end, jumps
•Trace through small examples: Verify logic manually
•Test the 0-heavy cases: [0], [1,0], [0,1]

The nums[i] = 0 Trap

Interview Perspective

Jump games are interview staples. Here's how to approach them systematically:

Interview Strategy

•Clarify the problem: Reachability? Min jumps? Bidirectional? Costs?
•Identify the type: Forward-only → likely greedy. Bidirectional or complex costs → BFS/DP.
•State the approach: "I'll track the farthest position I can reach as I iterate."
•Handle edge cases first: Empty array, single element, all zeros.
•Walk through an example: Trace your algorithm on the given example.
•Analyze complexity: O(n) time, O(1) space for basic variants.

Interview Script for Jump Game I

Interview Script for Jump Game II