Jump Game Problem in DSA C# - 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 forward a certain number of steps. You want to check if you can reach the last platform starting from the first one.

🎯 Goal: You will build a program that checks if it is possible to jump from the first platform to the last platform using the jump lengths given for each platform.

📋 What You'll Learn

Create an integer array called jumps with exact values representing jump lengths on each platform.

Create an integer variable called maxReach to track the farthest platform reachable.

Use a for loop with variable i to iterate over the jumps array and update maxReach.

Print "Can reach the end: True" or "Can reach the end: False" depending on whether the last platform is reachable.

💡 Why This Matters

🌍 Real World

This problem models situations where you need to check if a path or sequence of steps is possible, such as in games, navigation, or network routing.

💼 Career

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

1

Create the jumps array

Create an integer array called jumps with these exact values: 2, 3, 1, 1, 4.

DSA C#

// Create the jumps array with exact values
// Your code here

Hint

Use int[] jumps = {2, 3, 1, 1, 4}; to create the array.

2

Create maxReach variable

Create an integer variable called maxReach and set it to 0.

DSA C#

int[] jumps = {2, 3, 1, 1, 4};
// Create maxReach variable and set it to 0
// Your code here

Hint

Use int maxReach = 0; to create the variable.

3

Implement the jump logic

Use a for loop with variable i to iterate over the jumps array. Inside the loop, check if i is greater than maxReach. If yes, break the loop. Otherwise, update maxReach to the maximum of maxReach and i + jumps[i].

DSA C#

int[] jumps = {2, 3, 1, 1, 4};
int maxReach = 0;
// Add a for loop to update maxReach based on jumps
// Your code here

Hint

Use for (int i = 0; i < jumps.Length; i++) and inside check if (i > maxReach) to break. Update maxReach with Math.Max(maxReach, i + jumps[i]).

4

Print if the end is reachable

Print "Can reach the end: True" if maxReach is greater than or equal to jumps.Length - 1. Otherwise, print "Can reach the end: False".

DSA C#

int[] jumps = {2, 3, 1, 1, 4};
int maxReach = 0;
for (int i = 0; i  maxReach)
    {
        break;
    }
    maxReach = Math.Max(maxReach, i + jumps[i]);
}
// Print if the last platform is reachable
// Your code here

Hint

Use if (maxReach >= jumps.Length - 1) to decide what to print.

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.