Jump Game Problem in DSA Rust

Mental Model

You want to jump through an array from start to end using the numbers as max jump lengths. The question is if you can reach the last position.

Analogy: Imagine standing on stepping stones across a river. Each stone has a number telling you the farthest you can jump forward from it. You want to know if you can reach the last stone without falling in the water.

Start -> [3] -> 2 -> 1 -> 0 -> 4 -> End
Each number shows max jump length from that position.

Dry Run Walkthrough

Input: array: [3, 2, 1, 0, 4]

Goal: Determine if you can jump from index 0 to the last index using max jump lengths

Step 1: Start at index 0 with max jump 3, update furthest reachable to 3

Index: 0 -> 1 -> 2 -> 3 -> 4
Reachable max: 3 ↑

Why: We can jump up to 3 steps from start, so we can reach indices 1, 2, or 3

Step 2: Move to index 1 with max jump 2, update furthest reachable to max(3, 1+2=3)

Index: 0 -> 1 -> 2 -> 3 -> 4
Reachable max: 3 ↑

Why: From index 1, max jump is 2, but furthest reachable stays 3

Step 3: Move to index 2 with max jump 1, update furthest reachable to max(3, 2+1=3)

Index: 0 -> 1 -> 2 -> 3 -> 4
Reachable max: 3 ↑

Why: From index 2, max jump is 1, furthest reachable still 3

Step 4: Move to index 3 with max jump 0, update furthest reachable to max(3, 3+0=3)

Index: 0 -> 1 -> 2 -> 3 -> 4
Reachable max: 3 ↑

Why: From index 3, no jump possible, furthest reachable remains 3

Step 5: Try to move to index 4 but furthest reachable is 3, cannot reach index 4

Index: 0 -> 1 -> 2 -> 3 -> 4
Reachable max: 3 ↑ (cannot reach index 4)

Why: We cannot jump beyond index 3, so cannot reach the last index

Result:

Index: 0 -> 1 -> 2 -> 3 -> 4
Reachable max: 3 ↑ (cannot reach last index)
Answer: false

Annotated Code

DSA Rust

fn can_jump(nums: Vec<usize>) -> bool {
    let mut furthest = 0;
    for i in 0..nums.len() {
        if i > furthest {
            return false; // can't reach this position
        }
        furthest = furthest.max(i + nums[i]);
    }
    true
}

fn main() {
    let nums = vec![3, 2, 1, 0, 4];
    let result = can_jump(nums);
    println!("{}", result);
}

if i > furthest { return false; }

stop if current index is beyond furthest reachable index

furthest = furthest.max(i + nums[i]);

update furthest reachable index using max jump from current position

Output

false

Complexity Analysis

Time: O(n) because we scan the array once updating the furthest reachable index

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to backtracking which tries all paths (exponential), this greedy approach is much faster and simpler

Edge Cases

empty array

returns true because we are already at the last index

DSA Rust

for i in 0..nums.len() {

single element array [0]

returns true because start is last index

DSA Rust

for i in 0..nums.len() {

array with zero at start [0, 1]

returns false because cannot move anywhere

DSA Rust

if i > furthest { return false; }

When to Use This Pattern

When you see a problem asking if you can reach the end of an array by jumping variable steps, use the greedy furthest reachable index pattern to solve efficiently.

Common Mistakes

Mistake: Trying to explore all jump paths recursively causing timeouts
Fix: Use a greedy approach tracking the furthest reachable index instead of recursion

Mistake: Not checking if current index is reachable before updating furthest
Fix: Add a check to return false if current index is beyond furthest reachable

Summary

Determines if you can jump from start to end of an array using max jump lengths at each position.

Use when you need to check reachability in a jump game or similar stepwise movement problem.

Keep track of the furthest reachable index and stop early if you find a gap you cannot cross.

Practice

1. What does the Jump Game problem ask you to determine given an array of non-negative integers?

easy

A. The minimum number of jumps to reach the last index

B. The maximum jump length from the first index

C. If you can reach the last index starting from the first index

D. The sum of all jump lengths in the array

Solution

1. Step 1: Understand the problem statement

   The Jump Game problem asks if it is possible to move from the first index to the last index by jumping according to the values in the array.

2. Step 2: Identify the goal

   The goal is to check if the last index is reachable, not the number of jumps or sums.

3. Final Answer:

   If you can reach the last index starting from the first index -> Option C

4. Quick Check:

   Jump Game = Reach last index [OK]

Hint: Focus on reachability, not jump counts or sums [OK]

Common Mistakes:

• Confusing reachability with minimum jumps
• Thinking about total jump sums
• Assuming jumps can be backward

2. Which of the following Rust code snippets correctly declares a vector representing jump lengths for the Jump Game problem?

easy

A. let jumps = vec![2, 3, 1, 1, 4];

B. let jumps = [2, 3, 1, 1, 4];

C. let jumps = (2, 3, 1, 1, 4);

D. let jumps = {2, 3, 1, 1, 4};

Solution

1. Step 1: Identify Rust vector syntax

   In Rust, vectors are declared using vec![elements], which creates a growable array.

2. Step 2: Check each option

   let jumps = vec![2, 3, 1, 1, 4]; uses vec![], which is correct. let jumps = [2, 3, 1, 1, 4]; is an array, not a vector. let jumps = (2, 3, 1, 1, 4); is a tuple. let jumps = {2, 3, 1, 1, 4}; uses braces which is invalid syntax.

3. Final Answer:

   let jumps = vec![2, 3, 1, 1, 4]; -> Option A

4. Quick Check:

   vec! macro creates vectors [OK]

Hint: Use vec![] for vectors, not [] or () [OK]

Common Mistakes:

• Using array syntax instead of vec! macro
• Confusing tuples with vectors
• Using braces {} which is invalid

3. What is the output of the following Rust code snippet for the Jump Game problem?

fn can_jump(nums: Vec<usize>) -> bool {
    let mut max_reach = 0;
    for i in 0..nums.len() {
        if i > max_reach {
            return false;
        }
        max_reach = max_reach.max(i + nums[i]);
    }
    true
}

fn main() {
    let jumps = vec![2, 3, 1, 1, 4];
    println!("{}", can_jump(jumps));
}

medium

A. Runtime panic

B. false

C. Compilation error

D. true

Solution

1. Step 1: Trace the loop and max_reach updates

   Start with max_reach = 0. For i=0, max_reach = max(0, 0+2) = 2. For i=1, max_reach = max(2, 1+3) = 4. For i=2, max_reach = max(4, 2+1) = 4. For i=3, max_reach = max(4, 3+1) = 4. For i=4, max_reach = max(4, 4+4) = 8.

2. Step 2: Check if any index is unreachable

   At each i, i <= max_reach, so no false return. Loop completes and returns true.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Max reach covers all indices [OK]

Hint: Check if current index exceeds max reachable index [OK]

Common Mistakes:

• Not updating max_reach correctly
• Returning false too early
• Confusing max_reach with jump count

4. Identify the bug in the following Rust function for the Jump Game problem and select the fix.

fn can_jump(nums: Vec<usize>) -> bool {
    let mut max_reach = 0;
    for i in 0..nums.len() {
        if i >= max_reach {
            return false;
        }
        max_reach = max_reach.max(i + nums[i]);
    }
    true
}

medium

A. Change 'max_reach.max(i + nums[i])' to 'max_reach.min(i + nums[i])'

B. Change 'if i >= max_reach' to 'if i > max_reach'

C. Change 'for i in 0..nums.len()' to 'for i in 1..nums.len()'

D. Add 'max_reach += nums[i]' inside the loop

Solution

1. Step 1: Analyze the condition for unreachable index

   The condition 'if i >= max_reach' returns false even when i equals max_reach, which is incorrect because reaching exactly max_reach is allowed.

2. Step 2: Correct the condition

   Changing it to 'if i > max_reach' allows reaching max_reach index and only returns false if i is beyond max_reach.

3. Final Answer:

   Change 'if i >= max_reach' to 'if i > max_reach' -> Option B

4. Quick Check:

   Allow index equal to max_reach [OK]

Hint: Use strict greater than to check unreachable index [OK]

Common Mistakes:

• Using >= instead of > causes early false
• Using min instead of max for max_reach
• Skipping index 0 in loop

5. Given the array vec![3, 2, 1, 0, 4], what is the correct output of the Jump Game problem using the standard greedy approach in Rust?

hard

A. false

B. true

C. Compilation error

D. Runtime panic

Solution

1. Step 1: Trace max_reach for each index

   Start max_reach=0. i=0: max_reach=max(0,0+3)=3. i=1: max_reach=max(3,1+2)=3. i=2: max_reach=max(3,2+1)=3. i=3: max_reach=max(3,3+0)=3. i=4: i=4 > max_reach=3, so return false.

2. Step 2: Understand why last index is unreachable

   Index 4 cannot be reached because max_reach never extends beyond 3 due to zero jump at index 3.

3. Final Answer:

   false -> Option A

4. Quick Check:

   Zero jump blocks progress [OK]

Hint: Zero jump can block reaching the end [OK]

Common Mistakes:

• Assuming always true if first jump > 0
• Ignoring zero jump blocking path
• Confusing max_reach with jump count