Jump Game

Master greedy decision-making to determine reachability, the same adaptive strategy used in online learning and real-time speech systems.

TL;DR

Scan left to right, tracking the farthest reachable index. If the current position exceeds what is reachable, return false; if the farthest reach passes the last index, return true. This greedy approach runs in O(N) time with O(1) space, dramatically improving over the naive O(2^N) backtracking. The greedy reachability pattern connects to dynamic programming on grids and graph traversal problems.

Problem Statement

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

Examples

Example 1:

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

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump 
length is 0, which makes it impossible to reach the last index.

Example 3:

Input: nums = [0]
Output: true
Explanation: Already at the last index.

Constraints

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

Understanding the Problem

This is a reachability problem that teaches:

1. Greedy optimization - making locally optimal choices
2. Forward thinking - tracking maximum reachable position
3. Early termination - stopping as soon as we know the answer
4. Adaptive decision-making - updating strategy as we progress

Key Insight

At each position i, we can jump to any index in the range [i+1, i+nums[i]]. The question is: can we build a path from index 0 to index n-1?

Greedy observation: We don’t need to find the exact path, we just need to know if the last index is reachable.

We can track the maximum index we can reach so far and update it as we iterate through the array.

Why This Problem Matters

1. Greedy algorithms: Learn when greedy choices lead to optimal solutions
2. Reachability analysis: Common in graph problems, state machines
3. Optimization under constraints: Maximize reach with limited jumps
4. Real-world applications:
   • Network routing (can packet reach destination?)
   • Resource allocation (can we complete all tasks?)
   • Game AI (can player win from current state?)
   • Online learning (can model adapt to new patterns?)

The Adaptive Strategy Connection

Jump Game	Online Learning	Adaptive Speech
Greedily track max reach	Adapt model to new data	Adapt to speaker/noise
Update strategy at each position	Update weights incrementally	Update acoustic model online
Forward-looking optimization	Look-ahead predictions	Predictive adaptation
Early termination if stuck	Early stopping if degrading	Fallback if quality drops

All three use adaptive, greedy strategies to optimize in dynamic environments.

Approach 1: Brute Force - Try All Paths

Intuition

Use recursion/backtracking to try all possible paths from index 0 to index n-1.

Implementation

from typing import List

def canJump_bruteforce(nums: List[int]) -> bool:
    """
    Brute force: recursively try all paths.

    Time: O(2^N) - exponential, each position has multiple choices
    Space: O(N) - recursion depth

    Why this approach?
    - Shows the search space
    - Demonstrates need for optimization
    - Helps understand the problem structure

    Problem:
        - Extremely slow for large inputs
        - Explores redundant paths
        """
    def can_reach(position: int) -> bool:
        """Check if we can reach last index from position."""
        # Base case: reached the end
        if position >= len(nums) - 1:
            return True

            # Try all possible jumps from current position
            max_jump = nums[position]

            for jump in range(1, max_jump + 1):
                if can_reach(position + jump):
                    return True

                    return False

                    return can_reach(0)


                    # Test
                    print(canJump_bruteforce([2,3,1,1,4])) # True
                    print(canJump_bruteforce([3,2,1,0,4])) # False

Analysis

Time Complexity: O(2^N)

• At each position, we might have up to N choices
• Exponential branching factor

Space Complexity: O(N)

• Recursion depth

For N=10,000: Completely infeasible!

Approach 2: Dynamic Programming (Top-Down with Memoization)

Intuition

The brute force approach has overlapping subproblems - we might check if index i is reachable multiple times.

Use memoization to cache results.

Implementation

def canJump_dp_memo(nums: List[int]) -> bool:
    """
    DP with memoization.

    Time: O(N^2) - each position visited once, try up to N jumps
    Space: O(N) - memoization cache + recursion

    Optimization over brute force:
        - Cache results to avoid recomputation
        - Still explores many paths
        """
        memo = {}

    def can_reach(position: int) -> bool:
        # Check cache
        if position in memo:
            return memo[position]

            # Base case
            if position >= len(nums) - 1:
                return True

                # Try all jumps
                max_jump = nums[position]

                for jump in range(1, max_jump + 1):
                    if can_reach(position + jump):
                        memo[position] = True
                        return True

                        memo[position] = False
                        return False

                        return can_reach(0)

Analysis

Time Complexity: O(N^2)

• N positions
• Each position tries up to N jumps
• Better than exponential, but still slow

Space Complexity: O(N)

• Memoization cache
• Recursion stack

Approach 3: Dynamic Programming (Bottom-Up)

Intuition

Build up from the end: mark each position as GOOD (can reach end) or BAD (cannot reach end).

Implementation

def canJump_dp_bottomup(nums: List[int]) -> bool:
    """
    Bottom-up DP.

    Time: O(N^2)
    Space: O(N)

    dp[i] = True if we can reach last index from position i
    """
    n = len(nums)
    dp = [False] * n
    dp[n-1] = True # Last position can "reach" itself

    # Work backwards
    for i in range(n - 2, -1, -1):
        max_jump = nums[i]

        # Check if any position we can jump to is GOOD
        for jump in range(1, min(max_jump + 1, n - i)):
            if dp[i + jump]:
                dp[i] = True
                break

                return dp[0]

Approach 4: Greedy (Optimal)

The Key Insight

We don’t need to find the exact path, just whether the last index is reachable!

Greedy strategy: Track the maximum index we can reach so far as we iterate left to right.

• At each position i, update max_reach = max(max_reach, i + nums[i]).
• If max_reach >= n-1, we can reach the end.
• If at any point i > max_reach, we’re stuck (gap we can’t cross).

This is greedy because we make the locally optimal choice at each step: extend our reach as far as possible.

Implementation

def canJump(nums: List[int]) -> bool:
    """
    Greedy solution - optimal.

    Time: O(N) - single pass
    Space: O(1) - only tracking max_reach

    Strategy:
        - Track the farthest position we can reach
        - Update it as we iterate
        - If we reach or pass the last index, return True
        - If current position exceeds max reachable, return False

        Why this works:
            - We only care about maximum reach, not the exact path
            - Greedy choice: always extend reach as far as possible
            - Early termination: stop as soon as we know the answer
            """
            if len(nums) <= 1:
                return True

                max_reach = 0 # Farthest index we can reach

                for i in range(len(nums)):
                    # If current position is beyond our reach, we're stuck
                    if i > max_reach:
                        return False

                        # Update maximum reachable position
                        max_reach = max(max_reach, i + nums[i])

                        # Early termination: if we can reach the end, done
                        if max_reach >= len(nums) - 1:
                            return True

                            return max_reach >= len(nums) - 1

Step-by-Step Visualization

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

Initial: max_reach = 0

i=0, nums[0]=2:
 i (0) <= max_reach (0) ✓
 max_reach = max(0, 0+2) = 2
 Can reach indices: [0, 1, 2]

i=1, nums[1]=3:
 i (1) <= max_reach (2) ✓
 max_reach = max(2, 1+3) = 4
 Can reach indices: [0, 1, 2, 3, 4] ✓ (includes last index 4)
 Return True

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

Initial: max_reach = 0

i=0, nums[0]=3:
 i (0) <= max_reach (0) ✓
 max_reach = max(0, 0+3) = 3
 Can reach: [0, 1, 2, 3]

i=1, nums[1]=2:
 i (1) <= max_reach (3) ✓
 max_reach = max(3, 1+2) = 3
 Can reach: [0, 1, 2, 3]

i=2, nums[2]=1:
 i (2) <= max_reach (3) ✓
 max_reach = max(3, 2+1) = 3
 Can reach: [0, 1, 2, 3]

i=3, nums[3]=0:
 i (3) <= max_reach (3) ✓
 max_reach = max(3, 3+0) = 3
 Can reach: [0, 1, 2, 3] (stuck at index 3!)

i=4, nums[4]=4:
 i (4) > max_reach (3) ✗
 We can't reach index 4
 Return False

Why Greedy Works

Proof sketch:

1. If index j is reachable, then any index k where k <= j + nums[j] is also reachable.
2. Therefore, tracking the maximum reachable index is sufficient.
3. We never need to backtrack or try different paths.
4. The greedy choice (always extend reach maximally) guarantees we find the answer.

Implementation: Production-Grade Solution

from typing import List, Optional
import logging

class JumpGameSolver:
    """
    Production-ready Jump Game solver with multiple strategies.

    Features:
        - Input validation
        - Multiple algorithms
        - Performance metrics
        - Detailed logging
        """

    def __init__(self, strategy: str = "greedy"):
        """
        Initialize solver.

        Args:
            strategy: "greedy", "dp", or "bruteforce"
            """
            self.strategy = strategy
            self.logger = logging.getLogger(__name__)
            self.iterations = 0

    def can_jump(self, nums: List[int]) -> bool:
        """
        Determine if last index is reachable.

        Args:
            nums: Array of jump lengths

            Returns:
                True if last index reachable, False otherwise

                Raises:
                    ValueError: If input is invalid
                    """
                    # Validate input
                    if not nums:
                        raise ValueError("nums cannot be empty")

                        if not all(isinstance(x, int) and x >= 0 for x in nums):
                            raise ValueError("All elements must be non-negative integers")

                            # Reset metrics
                            self.iterations = 0

                            # Choose strategy
                            if self.strategy == "greedy":
                                result = self._greedy(nums)
                            elif self.strategy == "dp":
                                result = self._dp_bottomup(nums)
                            elif self.strategy == "bruteforce":
                                result = self._bruteforce(nums)
                            else:
                                raise ValueError(f"Unknown strategy: {self.strategy}")

                                self.logger.info(
                                f"Can jump: {result}, Strategy: {self.strategy}, "
                                f"Iterations: {self.iterations}"
                                )

                                return result

    def _greedy(self, nums: List[int]) -> bool:
        """Greedy approach - optimal."""
        if len(nums) <= 1:
            return True

            max_reach = 0

            for i in range(len(nums)):
                self.iterations += 1

                if i > max_reach:
                    return False

                    max_reach = max(max_reach, i + nums[i])

                    if max_reach >= len(nums) - 1:
                        return True

                        return max_reach >= len(nums) - 1

    def _dp_bottomup(self, nums: List[int]) -> bool:
        """DP approach."""
        n = len(nums)
        dp = [False] * n
        dp[n-1] = True

        for i in range(n - 2, -1, -1):
            self.iterations += 1
            max_jump = nums[i]

            for jump in range(1, min(max_jump + 1, n - i)):
                if dp[i + jump]:
                    dp[i] = True
                    break

                    return dp[0]

    def _bruteforce(self, nums: List[int]) -> bool:
        """Brute force recursive approach."""
    def can_reach(position: int) -> bool:
        self.iterations += 1

        if position >= len(nums) - 1:
            return True

            max_jump = nums[position]

            for jump in range(1, max_jump + 1):
                if can_reach(position + jump):
                    return True

                    return False

                    return can_reach(0)

    def find_path(self, nums: List[int]) -> Optional[List[int]]:
        """
        Find an actual path to the last index (if exists).

        Returns:
            List of indices representing the path, or None if impossible
            """
            if not self.can_jump(nums):
                return None

                n = len(nums)
                if n == 1:
                    return [0]

                    # Use greedy to find a path
                    path = [0]
                    current = 0

                    while current < n - 1:
                        max_jump = nums[current]

                        # Greedy choice: jump to position that maximizes next reach
                        best_next = current + 1
                        best_reach = best_next + nums[best_next]

                        for jump in range(1, max_jump + 1):
                            next_pos = current + jump
                            if next_pos >= n - 1:
                                path.append(n - 1)
                                return path

                                next_reach = next_pos + nums[next_pos]
                                if next_reach > best_reach:
                                    best_reach = next_reach
                                    best_next = next_pos

                                    path.append(best_next)
                                    current = best_next

                                    return path

    def get_stats(self) -> dict:
        """Get performance statistics."""
        return {
        "strategy": self.strategy,
        "iterations": self.iterations
        }


        # Example usage
        if __name__ == "__main__":
            logging.basicConfig(level=logging.INFO)

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

            solver = JumpGameSolver(strategy="greedy")

            for nums in test_cases:
                print(f"\nInput: {nums}")
                result = solver.can_jump(nums)
                print(f"Can jump: {result}")

                if result:
                    path = solver.find_path(nums)
                    print(f"Path: {path}")

                    print(f"Stats: {solver.get_stats()}")

Testing

Comprehensive Test Suite

import pytest

class TestJumpGame:
    """Comprehensive test suite for Jump Game."""

    @pytest.fixture
    def solver(self):
        return JumpGameSolver(strategy="greedy")

    def test_basic_examples(self, solver):
        """Test basic examples from problem."""
        assert solver.can_jump([2,3,1,1,4]) == True
        assert solver.can_jump([3,2,1,0,4]) == False
        assert solver.can_jump([0]) == True

    def test_edge_cases(self, solver):
        """Test edge cases."""
        # Single element
        assert solver.can_jump([5]) == True

        # Two elements
        assert solver.can_jump([1,0]) == True
        assert solver.can_jump([0,1]) == False

        # All zeros except first
        assert solver.can_jump([2,0,0]) == True
        assert solver.can_jump([1,0,0]) == False

    def test_always_reachable(self, solver):
        """Test cases where all jumps are >= 1."""
        assert solver.can_jump([1,1,1,1,1]) == True
        assert solver.can_jump([2,2,2,2,2]) == True

    def test_large_jumps(self, solver):
        """Test with very large jumps."""
        assert solver.can_jump([10000]) == True
        assert solver.can_jump([10000, 0, 0, 0, 0]) == True

    def test_barrier(self, solver):
        """Test with zero barrier."""
        assert solver.can_jump([1,0,1]) == False
        assert solver.can_jump([2,0,1]) == True
        assert solver.can_jump([1,1,0,1]) == True

    def test_strategy_equivalence(self):
        """Test that all strategies give same results."""
        test_cases = [
        [2,3,1,1,4],
        [3,2,1,0,4],
        [0],
        [1,2,3],
        ]

        for nums in test_cases:
            greedy_result = JumpGameSolver("greedy").can_jump(nums)
            dp_result = JumpGameSolver("dp").can_jump(nums)

            assert greedy_result == dp_result

    def test_find_path(self, solver):
        """Test path finding."""
        nums = [2,3,1,1,4]
        path = solver.find_path(nums)

        assert path is not None
        assert path[0] == 0
        assert path[-1] == len(nums) - 1

        # Verify path is valid
        for i in range(len(path) - 1):
            current = path[i]
            next_pos = path[i + 1]
            max_jump = nums[current]
            assert next_pos <= current + max_jump

    def test_no_path(self, solver):
        """Test when no path exists."""
        nums = [3,2,1,0,4]
        path = solver.find_path(nums)
        assert path is None


        # Run tests
        if __name__ == "__main__":
            pytest.main([__file__, "-v"])

Complexity Analysis

Greedy Approach (Optimal)

Time Complexity: O(N)

• Single pass through the array
• Each position visited once
• O(1) work per position

Space Complexity: O(1)

• Only a few variables: max_reach, loop index
• No additional data structures

Comparison

Approach	Time	Space	Notes
Brute Force	O(2^N)	O(N)	Too slow
DP (Memo)	O(N^2)	O(N)	Correct but slow
DP (Bottom-up)	O(N^2)	O(N)	Correct but slow
Greedy	O(N)	O(1)	Optimal

Production Considerations

1. Handling Very Large Arrays

For arrays that don’t fit in memory:

def canJump_streaming(nums_iterator):
    """
    Check if jump is possible with streaming input.

    Useful when nums is too large to load at once.
    """
    max_reach = 0
    position = 0

    for num in nums_iterator:
        if position > max_reach:
            return False

            max_reach = max(max_reach, position + num)
            position += 1

            return max_reach >= position - 1

2. Minimum Jumps (Extension)

If reachable, what’s the minimum number of jumps?

def minJumps(nums: List[int]) -> int:
    """
    Find minimum number of jumps to reach last index.

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

    Greedy approach:
        - Track current jump range
        - Count jumps when forced to jump again
        """
        if len(nums) <= 1:
            return 0

            jumps = 0
            current_end = 0
            farthest = 0

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

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

                    # Early termination
                    if current_end >= len(nums) - 1:
                        break

                        return jumps if current_end >= len(nums) - 1 else -1

3. Validation and Error Handling

class JumpValidator:
    """Validate jump game inputs and scenarios."""

    @staticmethod
    def validate_input(nums: List[int]) -> tuple[bool, Optional[str]]:
        """
        Validate input array.

        Returns:
            (is_valid, error_message)
            """
            if not nums:
                return False, "Array cannot be empty"

                if len(nums) > 10**4:
                    return False, f"Array too large: {len(nums)} (max 10^4)"

                    for i, num in enumerate(nums):
                        if not isinstance(num, int):
                            return False, f"Invalid type at index {i}: {type(num)}"

                            if num < 0:
                                return False, f"Negative value at index {i}: {num}"

                                if num > 10**5:
                                    return False, f"Value too large at index {i}: {num}"

                                    return True, None

4. Performance Monitoring

import time
from dataclasses import dataclass

@dataclass
class PerformanceMetrics:
    """Track performance metrics."""
    execution_time_ms: float
    iterations: int
    input_size: int
    result: bool

    @property
    def iterations_per_element(self) -> float:
        return self.iterations / self.input_size if self.input_size > 0 else 0

    def __str__(self) -> str:
        return (
        f"Performance Metrics:\n"
        f" Execution time: {self.execution_time_ms:.3f}ms\n"
        f" Iterations: {self.iterations}\n"
        f" Input size: {self.input_size}\n"
        f" Iterations/element: {self.iterations_per_element:.2f}\n"
        f" Result: {self.result}"
        )


    def canJump_with_metrics(nums: List[int]) -> tuple[bool, PerformanceMetrics]:
        """Solve problem and return metrics."""
        start = time.perf_counter()
        iterations = 0

        max_reach = 0

        for i in range(len(nums)):
            iterations += 1

            if i > max_reach:
                result = False
                break

                max_reach = max(max_reach, i + nums[i])

                if max_reach >= len(nums) - 1:
                    result = True
                    break
                else:
                    result = max_reach >= len(nums) - 1

                    execution_time = (time.perf_counter() - start) * 1000

                    metrics = PerformanceMetrics(
                    execution_time_ms=execution_time,
                    iterations=iterations,
                    input_size=len(nums),
                    result=result
                    )

                    return result, metrics

Connections to ML Systems

The greedy decision-making and adaptive strategy from this problem applies directly to online learning and adaptive systems:

1. Online Learning Systems

Similarity to Jump Game:

• Jump Game: Greedily extend reach at each position
• Online Learning: Greedily update model with each new data point

class OnlineLearner:
    """
    Online learning with greedy updates.

    Similar to Jump Game:
        - Process data sequentially (like iterating through array)
        - Make greedy decisions at each step (like updating max_reach)
        - Adapt to new information (like extending reach)
        """

    def __init__(self, learning_rate: float = 0.01):
        self.weights = None
        self.learning_rate = learning_rate
        self.performance_history = []

    def update(self, features, label):
        """
        Greedy update with new sample.

        Like Jump Game's greedy reach extension:
            - Each new sample updates our 'reach' (model capability)
            - Greedy choice: always move towards better performance
            """
            if self.weights is None:
                self.weights = np.zeros(len(features))

                # Predict
                prediction = np.dot(self.weights, features)

                # Compute error
                error = label - prediction

                # Greedy update: move weights to reduce error
                self.weights += self.learning_rate * error * features

                # Track 'reach' (model performance)
                self.performance_history.append(abs(error))

    def can_converge(self, threshold: float = 0.01) -> bool:
        """
        Check if model is converging.

        Like checking if we can 'reach' the goal (low error).
        """
        if len(self.performance_history) < 10:
            return False

            recent_errors = self.performance_history[-10:]
            avg_error = np.mean(recent_errors)

            return avg_error < threshold

2. Adaptive Thresholding

In real-time systems, we often need to decide: can we meet SLA with current resources?

class AdaptiveThresholdManager:
    """
    Manage adaptive thresholds based on performance.

    Similar to Jump Game's reachability check.
    """

    def __init__(self, target_latency_ms: float = 100.0):
        self.target_latency = target_latency_ms
        self.current_load = 0
        self.max_capacity = 100

    def can_handle_request(self, request_cost: int) -> bool:
        """
        Greedy check: can we handle this request?

        Like Jump Game: can we 'reach' a state where this request completes?
        """
        # Current position = current_load
        # Jump = request_cost
        # Goal = stay under max_capacity

        potential_load = self.current_load + request_cost

        if potential_load > self.max_capacity:
            return False # Can't reach goal

            # Greedy decision: accept request
            self.current_load = potential_load
            return True

    def release_resources(self, amount: int):
        """Release resources (like moving forward in jump game)."""
        self.current_load = max(0, self.current_load - amount)

3. Checkpoint Reachability

In distributed training, we need to determine: can we reach next checkpoint before timeout/failure?

def can_reach_checkpoint(
current_step: int,
checkpoint_step: int,
steps_per_second: float,
time_remaining_sec: float
) -> bool:
    """
    Check if we can reach checkpoint in time.

    Similar to Jump Game:
        - Current position = current_step
        - Goal = checkpoint_step
        - Constraint = time_remaining
        - 'Jump length' = steps we can complete in time
        """
        steps_needed = checkpoint_step - current_step
        steps_possible = int(steps_per_second * time_remaining_sec)

        return steps_possible >= steps_needed

Key Parallels

Jump Game	Online Learning	Adaptive Systems
Track max reach	Track model performance	Track system capacity
Greedy extension	Greedy weight updates	Greedy resource allocation
Early termination	Early stopping	Circuit breaking
Forward-looking	Look-ahead prediction	Predictive scaling

Interview Strategy

How to Approach This in an Interview

1. Clarify (1 min)

- Can nums contain zeros? (Yes)
- Can nums be empty? (No, constraint says length >= 1)
- Jump length is maximum, not fixed? (Yes, can jump 1 to nums[i])

2. Explain Intuition (2 min)

"I'll track the farthest position I can reach as I iterate through
the array. At each position, I update the maximum reach based on
current position + jump length. If I ever encounter a position
beyond my reach, I'm stuck. Otherwise, if max reach includes the
last index, return true."

3. Discuss Approaches (2 min)

1. Brute force: Try all paths - O(2^N), too slow
2. DP: Track reachability for each position - O(N^2)
3. Greedy: Track max reach - O(N), optimal

I'll implement the greedy approach.

4. Code (8-10 min)

• Clear variable names
• Handle edge cases
• Add comments

5. Test (3 min)

• Walk through Example 1 and 2
• Test edge case: single element

6. Optimize (2 min)

• Already optimal!
• Discuss early termination

Common Mistakes

1. Checking every reachable position instead of just max: ``python # Inefficient for i in range(len(nums)): for j in range(i+1, min(i+nums[i]+1, len(nums))): # Check each position

# Efficient max_reach = max(max_reach, i + nums[i]) ``

1. Not checking if current position is reachable: ``python # Wrong: might process unreachable positions for i in range(len(nums)): max_reach = max(max_reach, i + nums[i])

# Correct: check if i is reachable for i in range(len(nums)): if i > max_reach: return False max_reach = max(max_reach, i + nums[i]) ``

1. Forgetting early termination:
   • Can return True as soon as max_reach >= len(nums) - 1
2. Off-by-one errors:
   • Last index is len(nums) - 1, not len(nums)

Follow-up Questions

Q1: Find minimum number of jumps?

See minJumps implementation above.

Q2: Can you jump backwards?

Different problem, need to explore all paths (DP or BFS).

Q3: What if each element is a cost, and you want minimum cost path?

Dijkstra’s algorithm or DP with cost accumulation.

Q4: What if there are multiple goals (reachable indices)?

Modify to track all reachable positions, use a set or boolean array.

Additional Practice & Variants

1. Jump Game II (LeetCode 45)

Problem: Find the minimum number of jumps to reach the last index (guaranteed reachable).

def jump(nums: List[int]) -> int:
    """
    Minimum jumps to reach end.

    Greedy approach:
        - Track current jump's max reach
        - When we must jump again, increment counter

        Time: O(N), Space: O(1)
        """
        if len(nums) <= 1:
            return 0

            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

2. Jump Game III (LeetCode 1306)

Problem: Given array arr and start index, you can jump to i + arr[i] or i - arr[i]. Can you reach any index with value 0?

def canReach(arr: List[int], start: int) -> bool:
    """
    Can reach index with value 0 (bidirectional jumps).

    Use BFS or DFS since we can jump both directions.
    """
    visited = set()
    queue = [start]

    while queue:
        pos = queue.pop(0)

        if arr[pos] == 0:
            return True

            if pos in visited:
                continue

                visited.add(pos)

                # Try both jumps
                for next_pos in [pos + arr[pos], pos - arr[pos]]:
                    if 0 <= next_pos < len(arr) and next_pos not in visited:
                        queue.append(next_pos)

                        return False

3. Jump Game IV (LeetCode 1345)

Problem: Can jump to i-1, i+1, or any index j where arr[j] == arr[i]. Find minimum jumps.

Uses BFS with value-based teleportation.

Key Takeaways

✅ Greedy approach is optimal - track maximum reachable position

✅ Single pass, O(1) space - no need for DP or recursion

✅ Early termination - return as soon as we know the answer

✅ Forward-looking strategy - always extend reach maximally

✅ Reachability problems often have elegant greedy solutions

✅ Same pattern in online learning - greedy updates, adaptive strategies

✅ Same pattern in adaptive systems - greedy resource allocation, capacity checks

✅ Testing critical - edge cases (zeros, barriers, large jumps)

✅ Extensions interesting - minimum jumps, bidirectional, value-based teleportation

✅ Production applications - checkpoint reachability, SLA compliance, resource planning

Mental Model

Think of this problem as:

• Jump Game: Greedy reach extension with early termination
• Online Learning: Greedy model updates with convergence checks
• Adaptive Speech: Greedy model adaptation with quality monitoring

All use the pattern: make greedy decisions, adapt based on new information, terminate when goal is reached or unreachable.

Connection to Thematic Link: Greedy Decisions and Adaptive Strategies

All three topics share greedy, adaptive optimization:

DSA (Jump Game):

• Greedy decision: extend max reach at each step
• Adaptive: update strategy based on current position
• Forward-looking: anticipate future reachability

ML System Design (Online Learning Systems):

• Greedy decision: update model with each new sample
• Adaptive: adjust to distribution shifts
• Forward-looking: predict future patterns

Speech Tech (Adaptive Speech Models):

• Greedy decision: update model based on recent audio
• Adaptive: adjust to speaker/noise/accent changes
• Forward-looking: anticipate user corrections

The unifying principle: make locally optimal, greedy decisions while adapting to new information, crucial for systems that must respond to changing conditions in real-time.

FAQ

How does the greedy approach solve the Jump Game problem?

Maintain a variable tracking the farthest index reachable so far. At each position i, if i is within reach, update the farthest reach to max(farthest, i + nums[i]). If farthest reaches or exceeds the last index at any point, return true. If you encounter a position i that exceeds the current farthest reach, it means you are stuck and should return false.

Why is greedy optimal for Jump Game?

At each position, extending the maximum reach is always at least as good as any other strategy. The key insight is that reachability is monotonic: if index i is reachable, every index before i is also reachable. This means a single forward pass tracking the maximum reach is sufficient, and no backtracking or dynamic programming table is needed.

What is the difference between Jump Game and Jump Game II?

Jump Game is a boolean reachability problem: can you reach the last index? Jump Game II asks for the minimum number of jumps to reach the end. Both use greedy approaches, but Jump Game II additionally tracks the current jump boundary and increments a jump counter each time that boundary is crossed during the forward scan.

How does Jump Game relate to dynamic programming?

Jump Game can be solved with DP where dp[i] indicates whether index i is reachable, checking all previous positions. This runs in O(N squared) time. The greedy optimization recognizes that reachability forms a contiguous prefix: once you know the farthest reachable index, all positions up to that index are reachable, collapsing the DP table into a single variable.

---

Originally published at: arunbaby.com/dsa/0020-jump-game