Jump Game Problem in DSA C# - Time & Space Complexity

Time Complexity: Jump Game Problem

O(n)

Understanding Time Complexity

We want to understand how the time needed to check if we can jump to the end grows as the input array gets bigger.

How does the number of steps change when the array length increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public 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;
}
    

This code checks if you can jump from the start to the end of the array, where each number tells the max jump length from that position.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through each element once.
• How many times: Exactly once for each element in the array.

How Execution Grows With Input

As the array gets longer, the number of steps grows directly with its length.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The steps increase in a straight line as the input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to decide if you can reach the end grows in direct proportion to the array size.

Common Mistake

[X] Wrong: "Because we check jumps from each position, the time is much bigger than the array length, maybe quadratic."

[OK] Correct: The code only moves forward once through the array without nested loops, so it does not repeat work for each element multiple times.

Interview Connect

Understanding this helps you explain how to efficiently check reachability in arrays, a common skill in coding interviews.

Self-Check

"What if we changed the code to try all possible jumps from each position recursively? How would the time complexity change?"

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.