Jump Game Problem in DSA Rust - Execution Trace

Concept Flow - Jump Game Problem

Start at index 0

↓

Check if current index can reach end?

Yes→Return True

No↓

Find next reachable indices

↓

Move to next best index

↓

Repeat until end reachable or no moves

↓

Return False if stuck

Start from the first position, check if you can jump to the end. If not, try all reachable next steps until you reach the end or get stuck.

Execution Sample

DSA Rust

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 = std::cmp::max(max_reach, i + nums[i]);
    }
    true
}

This code checks if you can jump from start to end by tracking the farthest reachable index.

Execution Table

Step	Index i	nums[i]	max_reach before	Condition i <= max_reach	max_reach after	Action	Reachable Indices	Result
1	0	2	0	True	2	Update max_reach to max(0,0+2)=2	[1,2]	Continue
2	1	3	2	True	4	Update max_reach to max(2,1+3)=4	[2,3,4]	Continue
3	2	1	4	True	4	Update max_reach to max(4,2+1)=4	[3]	Continue
4	3	1	4	True	4	Update max_reach to max(4,3+1)=4	[4]	Continue
5	4	0	4	True	4	Update max_reach to max(4,4+0)=4	[]	Reached or passed end, return True
6	-	-	4	-	-	-	-	End reached, return True

💡 Loop ends because index i never exceeds max_reach and max_reach reaches or passes last index

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
i	0	1	2	3	4	-	-
nums[i]	-	2	3	1	1	0	-
max_reach	0	2	4	4	4	4	4

Key Moments - 3 Insights

Why do we return false if i > max_reach?

Because if current index i is beyond the farthest reachable index max_reach, it means we cannot jump to this position, so the end is unreachable. See execution_table step 3 condition.

Why do we update max_reach with max(i + nums[i], max_reach)?

Because from position i, we can jump up to i + nums[i]. We keep track of the farthest reachable index so far to know if we can reach the end. See execution_table max_reach updates.

What happens if nums[i] is 0?

If nums[i] is 0, we cannot jump forward from i, so max_reach does not increase. If max_reach is stuck and i exceeds it, we return false. See execution_table step 5.

Visual Quiz - 3 Questions

Look at the execution_table, what is max_reach after step 2?

A 2

B 4

C 3

D 1

💡 Hint

Check the 'max_reach after' column in row for step 2.

At which step does the condition i <= max_reach become false causing early return?

A Step 3

B Step 6

C Never in this example

D Step 5

💡 Hint

Look at the 'Condition i <= max_reach' column for all steps.

If nums[1] was 1 instead of 3, how would max_reach after step 2 change?

A max_reach would be 2

B max_reach would be 3

C max_reach would be 4

D max_reach would be 1

💡 Hint

Calculate max(i + nums[i], max_reach) for i=1 with nums[1]=1.

Concept Snapshot

Jump Game Problem:
- Start at index 0
- Track max_reach = farthest index reachable
- For each index i:
  - If i > max_reach, return false
  - Update max_reach = max(max_reach, i + nums[i])
- If loop ends, return true (end reachable)

Full Transcript

The Jump Game problem asks if you can reach the last index starting from the first index, given an array where each element represents the maximum jump length from that position. The code tracks the farthest reachable index (max_reach). It iterates through each index i, checking if i is reachable (i <= max_reach). If not, it returns false immediately. Otherwise, it updates max_reach to the maximum of current max_reach and i + nums[i]. If the loop completes without returning false, it means the last index is reachable, so it returns true. The execution table shows step-by-step how max_reach changes and how the condition is checked. Key moments clarify why we return false early and how max_reach updates. The visual quiz tests understanding of max_reach values and conditions during execution.

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