Jump Game Problem in DSA Rust - Build from Scratch

Jump Game Problem

📖 Scenario: Imagine you are playing a video game where you need to jump across platforms to reach the end. Each platform lets you jump a certain maximum number of steps forward. You want to check if you can reach the last platform starting from the first one.

🎯 Goal: Build a Rust program that checks if you can reach the last platform in a list of platforms, where each platform has a maximum jump length.

📋 What You'll Learn

Create a vector called platforms with exact values [2, 3, 1, 1, 4]

Create a variable called max_reach and set it to 0

Use a for loop with variable i to iterate over the indices of platforms

Inside the loop, update max_reach to the maximum of max_reach and i + platforms[i]

If i > max_reach at any point before the last index, break the loop

After the loop, print "Can reach end: true" if max_reach is greater than or equal to the last index, else print "Can reach end: false"

💡 Why This Matters

🌍 Real World

This problem models situations where you need to check if a path or sequence of steps is possible given constraints, like in games, network routing, or project planning.

💼 Career

Understanding this problem helps in software engineering roles that involve algorithmic thinking, problem solving, and optimization.

1

Create the platforms vector

Create a vector called platforms with these exact values: [2, 3, 1, 1, 4]

DSA Rust

# Create the platforms vector with values [2, 3, 1, 1, 4]
// Your code here

Hint

Use let platforms = vec![2, 3, 1, 1, 4]; to create the vector.

2

Create the max_reach variable

Create a variable called max_reach and set it to 0 inside the main function after the platforms vector

DSA Rust

fn main() {
    let platforms = vec![2, 3, 1, 1, 4];
    // Create max_reach variable and set to 0
    // Your code here
}

Hint

Use let mut max_reach = 0; to create a mutable variable.

3

Implement the jump logic loop

Use a for loop with variable i to iterate over the indices of platforms using 0..platforms.len(). Inside the loop, update max_reach to the maximum of max_reach and i + platforms[i]. If i > max_reach before the last index, break the loop.

DSA Rust

fn main() {
    let platforms = vec![2, 3, 1, 1, 4];
    let mut max_reach = 0;
    // Add for loop to update max_reach and break if stuck
    // Your code here
}

Hint

Use for i in 0..platforms.len() and inside check if i > max_reach then break. Update max_reach with max_reach.max(i + platforms[i] as usize).

4

Print if the end is reachable

After the loop, print "Can reach end: true" if max_reach is greater than or equal to platforms.len() - 1, else print "Can reach end: false"

DSA Rust

fn main() {
    let platforms = vec![2, 3, 1, 1, 4];
    let mut max_reach = 0;
    for i in 0..platforms.len() {
        if i > max_reach {
            break;
        }
        max_reach = max_reach.max(i + platforms[i] as usize);
    }
    // Print if the end is reachable
    // Your code here
}

Hint

Use if max_reach >= platforms.len() - 1 then print "Can reach end: true", else print "Can reach end: false".

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