Jump Game Problem in DSA C#

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 stepping stones across a river. Each stone tells you how far you can jump next. 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 stone.

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, so max reachable index is 0 + 3 = 3

maxReach = 3, current index = 0

Why: We begin with the first stone and see how far we can jump.

Step 2: Move to index 1, max jump is 2, update maxReach to max(3, 1+2) = 3

maxReach = 3, current index = 1

Why: Check if we can jump farther from index 1.

Step 3: Move to index 2, max jump is 1, update maxReach to max(3, 2+1) = 3

maxReach = 3, current index = 2

Why: Check if we can jump farther from index 2.

Step 4: Move to index 3, max jump is 0, update maxReach to max(3, 3+0) = 3

maxReach = 3, current index = 3

Why: Check if we can jump farther from index 3.

Step 5: Try to move to index 4, but maxReach is 3 which is less than 4, so cannot reach index 4

maxReach = 3, current index = 4 (not reachable)

Why: We cannot jump beyond index 3, so last index is unreachable.

Result:

Cannot reach last index because maxReach = 3 < last index 4

Annotated Code

DSA C#

using System;

class JumpGame {
    public static bool CanJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (i > maxReach) return false; // cannot reach this position
            maxReach = Math.Max(maxReach, i + nums[i]); // update max reachable index
        }
        return true; // reached or passed last index
    }

    static void Main() {
        int[] nums = {3, 2, 1, 0, 4};
        bool result = CanJump(nums);
        Console.WriteLine(result ? "Can reach last index" : "Cannot reach last index");
    }
}

if (i > maxReach) return false; // cannot reach this position

stop if current index is beyond max reachable index

maxReach = Math.Max(maxReach, i + nums[i]); // update max reachable index

update max reachable index using current position and jump length

Output

Cannot reach last index

Complexity Analysis

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

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Compared to recursive or backtracking approaches that try all paths (exponential), this greedy approach is efficient and linear.

Edge Cases

Empty array

Returns true because we are already at the last index

DSA C#

for (int i = 0; i < nums.Length; i++) {

Single element array [0]

Returns true because start is last index

DSA C#

for (int i = 0; i < nums.Length; i++) {

Array with zero at start [0, 1]

Returns false because cannot move anywhere

DSA C#

if (i > maxReach) 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 maxReach pattern to track the farthest reachable index.

Common Mistakes

Mistake: Not checking if current index is beyond max reachable index before updating maxReach
Fix: Add a condition to return false immediately if current index is unreachable

Mistake: Trying to simulate all jump paths instead of tracking max reachable index
Fix: Use a single variable to track max reachable index greedily

Summary

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

Use when you need to check reachability in jump or step problems efficiently.

Keep track of the farthest index you can reach and stop if you get stuck before the end.

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.