Skip to content

Jump Game

Approach

I: Track the farthest reachable index. If current index exceeds farthest, return False. II: BFS-style greedy. Track current window end and farthest reachable. Increment jumps when reaching the window end.

When to Use

Reachability analysis — "can you reach the end?", "minimum hops to reach target". Track farthest reachable index greedily. Also: network hop-count analysis, coverage verification.

Complexity
Time O(n)
Space O(1)

Implementation

jump_game

Jump Game — can you reach the last index? / minimum jumps.

Problem (I): Given an array where each element is the max jump length from that position, determine if you can reach the last index.

Problem (II): Return the minimum number of jumps to reach the last index. Assume the answer always exists.

Approach

I: Track the farthest reachable index. If current index exceeds farthest, return False. II: BFS-style greedy. Track current window end and farthest reachable. Increment jumps when reaching the window end.

When to use

Reachability analysis — "can you reach the end?", "minimum hops to reach target". Track farthest reachable index greedily. Also: network hop-count analysis, coverage verification.

Complexity

Time: O(n) Space: O(1)

can_jump 

can_jump(nums: Sequence[int]) -> bool

Return True if the last index is reachable.

can_jump([2, 3, 1, 1, 4]) True can_jump([3, 2, 1, 0, 4]) False

Source code in src/algo/greedy/jump_game.py 
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def can_jump(nums: Sequence[int]) -> bool:
    """Return True if the last index is reachable.

    >>> can_jump([2, 3, 1, 1, 4])
    True
    >>> can_jump([3, 2, 1, 0, 4])
    False
    """
    farthest = 0
    for i, n in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + n)
    return True

jump_game_ii 

jump_game_ii(nums: Sequence[int]) -> int

Return the minimum number of jumps to reach the last index.

jump_game_ii([2, 3, 1, 1, 4]) 2 jump_game_ii([1]) 0

Source code in src/algo/greedy/jump_game.py 
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def jump_game_ii(nums: Sequence[int]) -> int:
    """Return the minimum number of jumps to reach the last index.

    >>> jump_game_ii([2, 3, 1, 1, 4])
    2
    >>> jump_game_ii([1])
    0
    """
    if len(nums) <= 1:
        return 0

    jumps = 0
    cur_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = farthest
            if cur_end >= len(nums) - 1:
                break

    return jumps
tests/greedy/test_jump_game.py
"""Tests for jump game I and II."""

from algo.greedy.jump_game import can_jump, jump_game_ii


class TestCanJump:
    def test_reachable(self) -> None:
        assert can_jump([2, 3, 1, 1, 4]) is True

    def test_unreachable(self) -> None:
        assert can_jump([3, 2, 1, 0, 4]) is False

    def test_single_element(self) -> None:
        assert can_jump([0]) is True

    def test_all_zeros_except_first(self) -> None:
        assert can_jump([4, 0, 0, 0, 0]) is True

    def test_zero_at_start(self) -> None:
        assert can_jump([0, 1]) is False


class TestJumpGameII:
    def test_basic(self) -> None:
        assert jump_game_ii([2, 3, 1, 1, 4]) == 2

    def test_single_element(self) -> None:
        assert jump_game_ii([1]) == 0

    def test_two_elements(self) -> None:
        assert jump_game_ii([1, 1]) == 1

    def test_large_first_jump(self) -> None:
        assert jump_game_ii([5, 1, 1, 1, 1]) == 1

    def test_all_ones(self) -> None:
        assert jump_game_ii([1, 1, 1, 1]) == 3

Implement it yourself

Run: just challenge greedy jump_game

Then implement the functions to make all tests pass. Use just study greedy for watch mode.

Reveal Solution

jump_game

Jump Game — can you reach the last index? / minimum jumps.

Problem (I): Given an array where each element is the max jump length from that position, determine if you can reach the last index.

Problem (II): Return the minimum number of jumps to reach the last index. Assume the answer always exists.

Approach

I: Track the farthest reachable index. If current index exceeds farthest, return False. II: BFS-style greedy. Track current window end and farthest reachable. Increment jumps when reaching the window end.

When to use

Reachability analysis — "can you reach the end?", "minimum hops to reach target". Track farthest reachable index greedily. Also: network hop-count analysis, coverage verification.

Complexity

Time: O(n) Space: O(1)

can_jump 

can_jump(nums: Sequence[int]) -> bool

Return True if the last index is reachable.

can_jump([2, 3, 1, 1, 4]) True can_jump([3, 2, 1, 0, 4]) False

Source code in src/algo/greedy/jump_game.py 
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def can_jump(nums: Sequence[int]) -> bool:
    """Return True if the last index is reachable.

    >>> can_jump([2, 3, 1, 1, 4])
    True
    >>> can_jump([3, 2, 1, 0, 4])
    False
    """
    farthest = 0
    for i, n in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + n)
    return True

jump_game_ii 

jump_game_ii(nums: Sequence[int]) -> int

Return the minimum number of jumps to reach the last index.

jump_game_ii([2, 3, 1, 1, 4]) 2 jump_game_ii([1]) 0

Source code in src/algo/greedy/jump_game.py 
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def jump_game_ii(nums: Sequence[int]) -> int:
    """Return the minimum number of jumps to reach the last index.

    >>> jump_game_ii([2, 3, 1, 1, 4])
    2
    >>> jump_game_ii([1])
    0
    """
    if len(nums) <= 1:
        return 0

    jumps = 0
    cur_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = farthest
            if cur_end >= len(nums) - 1:
                break

    return jumps