Jump Game Problem in DSA C# - Execution Trace

Concept Flow - Jump Game Problem

Start at index 0

↓

Check max jump from current index

↓

Update furthest reachable index

↓

Move to next index

↓

Is current index <= furthest reachable?

No→Return False

Yes↓

Reached last index?

Yes→Return True

No↓

Check max jump from current index

Start from the first position, keep track of the furthest index reachable, move forward checking if the current position is reachable, and stop when the last index is reachable or not.

Execution Sample

DSA C#

int[] nums = {2,3,1,1,4};
int furthest = 0;
for (int i = 0; i < nums.Length; i++) {
  if (i > furthest) return false;
  furthest = Math.Max(furthest, i + nums[i]);
}
return true;

This code checks if you can jump from the start to the end of the array by updating the furthest reachable index at each step.

Execution Table

Step	Operation	Current Index (i)	Current Jump Length (nums[i])	Furthest Reachable Index	Condition i <= Furthest?	Action	Visual State (Indices reachable)
1	Start	0	2	0	0 <= 0 (True)	Update furthest = max(0, 0+2)=2	[0,1,2] reachable
2	Next index	1	3	2	1 <= 2 (True)	Update furthest = max(2, 1+3)=4	[0,1,2,3,4] reachable
3	Next index	2	1	4	2 <= 4 (True)	Update furthest = max(4, 2+1)=4	[0,1,2,3,4] reachable
4	Next index	3	1	4	3 <= 4 (True)	Update furthest = max(4, 3+1)=4	[0,1,2,3,4] reachable
5	Next index	4	4	4	4 <= 4 (True)	Update furthest = max(4, 4+4)=8	[0,1,2,3,4,5,6,7,8] reachable (beyond end)
6	End	-	-	8	-	Reached end, return True	[0,1,2,3,4,5,6,7,8] reachable

💡 Loop ends because all indices up to last are reachable (i <= furthest) and last index is reached.

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	4	-	-
furthest	0	2	4	4	4	8	8

Key Moments - 3 Insights

Why do we check if current index i is greater than furthest reachable index?

Because if i > furthest, it means we cannot reach index i from any previous jumps, so the game cannot be completed. This is shown in execution_table row 2 where the condition i <= furthest must be true to continue.

Why do we update furthest reachable index with max(furthest, i + nums[i])?

Because from index i, we can jump up to nums[i] steps ahead, so we update furthest to the maximum reachable index so far. This ensures we track the best possible reach, as seen in execution_table rows 1 to 5.

What happens if furthest reaches beyond the last index?

If furthest is beyond or equal to the last index, it means we can reach the end. The loop can stop and return true, as shown in execution_table row 5 where furthest becomes 8, beyond the last index 4.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the furthest reachable index?

A 2

B 3

C 4

D 5

💡 Hint

Check the 'Furthest Reachable Index' column at Step 3 in the execution_table.

At which step does the condition i <= furthest become false, causing the loop to stop?

A It never becomes false

B Step 5

C Step 2

D Step 6

💡 Hint

Look at the 'Condition i <= Furthest?' column in the execution_table for all steps.

If nums[1] was 0 instead of 3, how would the furthest reachable index change at Step 2?

A It would become 1

B It would remain 2

C It would become 3

D It would become 4

💡 Hint

Check how furthest is updated using max(furthest, i + nums[i]) at Step 2 in the execution_table.

Concept Snapshot

Jump Game Problem:
- Start at index 0
- Track furthest reachable index
- For each index i, if i > furthest, return false
- Update furthest = max(furthest, i + nums[i])
- If furthest >= last index, return true
- Time: O(n), Space: O(1)

Full Transcript

The Jump Game problem asks if you can reach the last index of an array starting from the first index, where each element represents the maximum jump length from that position. The approach is to keep track of the furthest index reachable so far. Starting at index 0, we update the furthest reachable index by comparing the current furthest with the current index plus the jump length at that index. If at any point the current index is beyond the furthest reachable index, it means we cannot proceed further and return false. If we reach or pass the last index, we return true. The execution table shows step-by-step how the furthest index updates and how the condition is checked at each step. This method runs in linear time and uses constant space.

Practice

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

easy

A. If you can reach the last index starting from the first index by jumping according to the values.

B. The maximum jump length you can make from any position.

C. The minimum number of jumps needed to reach the last 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 you can start at the first index and reach the last index by jumping forward using the values at each index as maximum jump lengths.

2. Step 2: Identify the goal

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

3. Final Answer:

   If you can reach the last index starting from the first index by jumping according to the values. -> Option A

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 needed.
• Thinking about maximum jump length only.
• Assuming sum of jumps matters.

2. Which of the following C# code snippets correctly declares an array for the Jump Game input?

easy

A. int jumps[] = new int[5] {2, 3, 1, 1, 4};

B. int jumps = {2, 3, 1, 1, 4};

C. int[] jumps = new int[] {2, 3, 1, 1, 4};

D. int[] jumps = (2, 3, 1, 1, 4);

Solution

1. Step 1: Check array declaration syntax in C#

   In C#, arrays are declared with type[], then initialized with new type[] and values inside braces.

2. Step 2: Validate each option

   int[] jumps = new int[] {2, 3, 1, 1, 4}; uses correct syntax: int[] jumps = new int[] {2, 3, 1, 1, 4}; Options A, B, and D have syntax errors or invalid declarations.

3. Final Answer:

   int[] jumps = new int[] {2, 3, 1, 1, 4}; -> Option C

4. Quick Check:

   C# array syntax = int[] jumps = new int[] {2, 3, 1, 1, 4}; [OK]

Hint: Use 'int[] name = new int[] {values};' for arrays in C#. [OK]

Common Mistakes:

• Omitting 'new int[]' when initializing arrays.
• Using parentheses instead of braces for array values.
• Declaring arrays like in other languages (e.g., C/C++).

3. What will be the output of the following C# code for the Jump Game problem?

public static bool CanJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.Length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.Max(maxReach, i + nums[i]);
    }
    return true;
}

Console.WriteLine(CanJump(new int[] {3, 2, 1, 0, 4}));

medium

A. Runtime exception

B. True

C. Compile-time error

D. False

Solution

1. Step 1: Trace the loop and maxReach updates

   Start with maxReach=0. At i=0, maxReach = max(0, 0+3)=3. i=1 (<=3), maxReach=max(3,1+2)=3. i=2 (<=3), maxReach=max(3,2+1)=3. i=3 (<=3), maxReach=max(3,3+0)=3. i=4 (4 > maxReach=3), return false.

2. Step 2: Understand the return value

   Since index 4 is not reachable, the function returns false.

3. Final Answer:

   False -> Option D

4. Quick Check:

   Index 4 unreachable = False [OK]

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

Common Mistakes:

• Assuming all arrays are reachable.
• Not updating maxReach correctly.
• Confusing true/false return values.

4. Identify the bug in this C# Jump Game code snippet:

public static bool CanJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i <= nums.Length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.Max(maxReach, i + nums[i]);
    }
    return true;
}

medium

A. The loop condition should be i < nums.Length, not i <= nums.Length.

B. maxReach should be initialized to -1 instead of 0.

C. The return type should be int, not bool.

D. The Math.Max function is used incorrectly.

Solution

1. Step 1: Analyze the for loop condition

   The loop runs from i=0 to i <= nums.Length, which means it tries to access nums[nums.Length], causing an index out of range error.

2. Step 2: Correct the loop boundary

   The loop should run while i < nums.Length to avoid accessing beyond the array bounds.

3. Final Answer:

   The loop condition should be i < nums.Length, not i <= nums.Length. -> Option A

4. Quick Check:

   Array index out of range fixed by loop condition [OK]

Hint: Use i < length for array loops to avoid out-of-bounds. [OK]

Common Mistakes:

• Using <= instead of < in loop conditions.
• Ignoring array index limits.
• Misunderstanding return types.

5. Given the array int[] nums = {2, 0, 2, 0, 1}, which modification to the Jump Game algorithm below will correctly determine if the last index is reachable?

public static bool CanJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.Length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.Max(maxReach, i + nums[i]);
    }
    return true;
}

hard

A. Add a check to skip indices where nums[i] == 0.

B. No modification needed; the current algorithm works correctly.

C. Change the loop to iterate backwards from the end to the start.

D. Return false immediately if maxReach does not increase in an iteration.

Solution

1. Step 1: Trace the algorithm with the given array

   Start maxReach=0. i=0: maxReach=max(0,0+2)=2. i=1 (1 <= 2): maxReach=max(2,1+0)=2. i=2 (2 <= 2): maxReach=max(2,2+2)=4. i=3 (3 <= 4): maxReach=max(4,3+0)=4. i=4 (4 <= 4): maxReach=max(4,4+1)=5. Loop ends, return true.

2. Step 2: Confirm algorithm correctness

   The algorithm correctly identifies the last index is reachable without modification.

3. Final Answer:

   No modification needed; the current algorithm works correctly. -> Option B

4. Quick Check:

   Algorithm handles zeros and reachability correctly [OK]

Hint: Test with zeros; algorithm handles them if maxReach updates properly. [OK]

Common Mistakes:

• Thinking zeros always block progress.
• Adding unnecessary checks for zero values.
• Changing loop direction without reason.