Jump Game Problem in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Jump Game Reachability Check

What is the output of the following C# code that checks if you can jump to the last index of the array?

DSA C#

using System;

class Program {
    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;
    }

    static void Main() {
        int[] nums = {2, 3, 1, 1, 4};
        Console.WriteLine(CanJump(nums));
    }
}

A Runtime exception

B False

C Compilation error

D True

💡 Hint

Think about whether the jumps allow reaching the last index.

The code tracks the farthest index reachable. Since the array allows jumps to reach the end, it returns True.

❓ Predict Output

intermediate

Output for Unreachable Last Index

What will the output be for this C# code when the last index is not reachable?

DSA C#

using System;

class Program {
    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;
    }

    static void Main() {
        int[] nums = {3, 2, 1, 0, 4};
        Console.WriteLine(CanJump(nums));
    }
}

A True

B False

C Compilation error

D Runtime exception

💡 Hint

Check if the zero blocks progress to the last index.

The zero at index 3 blocks any further jump, so the last index cannot be reached.

🔧 Debug

advanced

Identify the bug in Jump Game code

What error will this C# code produce when trying to check jump reachability?

DSA C#

using System;

class Program {
    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;
    }

    static void Main() {
        int[] nums = {2, 3, 1, 1, 4};
        Console.WriteLine(CanJump(nums));
    }
}

A True

B False

C IndexOutOfRangeException

D Compilation error

💡 Hint

Check the loop condition and array indexing carefully.

The loop runs until i <= nums.Length which causes an index out of range when accessing nums[i] at the last iteration.

🧠 Conceptual

advanced

Minimum Jumps to Reach Last Index

Given an array where each element represents the max jump length at that position, which approach correctly finds the minimum number of jumps to reach the last index?

A Use a greedy approach tracking the current jump's max reach and increment jumps when exceeding it

B Use a depth-first search to explore all jump paths and pick the shortest

C Sort the array and pick the largest jumps first

D Use a stack to store indices and pop when jumps are exhausted

💡 Hint

Think about how to track jumps efficiently without exploring all paths.

The greedy approach efficiently tracks the farthest reachable index within the current jump and increments jumps when moving beyond it.

❓ Predict Output

expert

Output of Minimum Jumps Calculation

What is the output of this C# code that calculates the minimum number of jumps to reach the last index?

DSA C#

using System;

class Program {
    static int MinJumps(int[] nums) {
        if (nums.Length <= 1) return 0;
        int jumps = 0, currentEnd = 0, farthest = 0;
        for (int i = 0; i < nums.Length - 1; i++) {
            farthest = Math.Max(farthest, i + nums[i]);
            if (i == currentEnd) {
                jumps++;
                currentEnd = farthest;
            }
        }
        return jumps;
    }

    static void Main() {
        int[] nums = {2, 3, 1, 1, 4};
        Console.WriteLine(MinJumps(nums));
    }
}

A 2

B 3

C 4

D 1

💡 Hint

Count how many jumps are needed to cover the array.

The minimum jumps to reach the last index in this array is 2: jump from index 0 to 1, then from 1 to 4.

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.