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 reach the last index of the array?

DSA C

int canJump(int* nums, int numsSize) {
    int maxReach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > maxReach) return 0;
        if (i + nums[i] > maxReach) maxReach = i + nums[i];
    }
    return 1;
}

int main() {
    int arr[] = {2,3,1,1,4};
    int size = sizeof(arr)/sizeof(arr[0]);
    int result = canJump(arr, size);
    printf("%d\n", result);
    return 0;
}

A 0

B 1

C Compilation error

D Runtime error

💡 Hint

Think about whether the maximum reachable index covers the last index.

The function tracks the furthest index reachable. Since the array allows jumps to reach the end, the function returns 1.

❓ Predict Output

intermediate

Output when jump is not possible

What will be printed by this C program that uses the jump game logic?

DSA C

int canJump(int* nums, int numsSize) {
    int maxReach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > maxReach) return 0;
        if (i + nums[i] > maxReach) maxReach = i + nums[i];
    }
    return 1;
}

int main() {
    int arr[] = {3,2,1,0,4};
    int size = sizeof(arr)/sizeof(arr[0]);
    int result = canJump(arr, size);
    printf("%d\n", result);
    return 0;
}

A 1

B Compilation error

C 0

D Segmentation fault

💡 Hint

Check if the zero in the array blocks progress.

The zero at index 3 blocks further jumps, so the last index is unreachable, returning 0.

🧠 Conceptual

advanced

Understanding the Greedy Approach in Jump Game

Why does the greedy approach work for the Jump Game problem instead of trying all possible jumps?

A Because it uses dynamic programming to store all reachable indices.

B Because it tries every possible jump recursively to find the path.

C Because it sorts the array to find the best jumps first.

D Because the maximum reachable index always increases or stays the same, ensuring no need to backtrack.

💡 Hint

Think about how the maximum reachable index changes as you move forward.

The greedy approach works because it keeps track of the furthest reachable index and never needs to revisit previous positions.

❓ Predict Output

advanced

Output of Jump Game with Zero at Start

What will the following C program print when the first element is zero?

DSA C

int canJump(int* nums, int numsSize) {
    int maxReach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > maxReach) return 0;
        if (i + nums[i] > maxReach) maxReach = i + nums[i];
    }
    return 1;
}

int main() {
    int arr[] = {0,2,3};
    int size = sizeof(arr)/sizeof(arr[0]);
    int result = canJump(arr, size);
    printf("%d\n", result);
    return 0;
}

A 0

B 1

C Runtime error

D Compilation error

💡 Hint

If the first jump length is zero, can you move forward?

Since the first element is zero, you cannot move anywhere, so the last index is unreachable.

🧠 Conceptual

expert

Time Complexity of Jump Game Greedy Solution

What is the time complexity of the greedy solution for the Jump Game problem and why?

A O(n), because it scans the array once updating the maximum reachable index.

B O(n^2), because it checks all jumps from each index.

C O(log n), because it uses binary search to find jumps.

D O(1), because it uses constant time operations.

💡 Hint

Consider how many times the loop runs and what operations it performs inside.

The greedy solution runs in linear time because it iterates through the array once, updating the maximum reachable index without nested loops.

Practice

1. What is the main goal of the Jump Game problem?

easy

A. Calculate the minimum jump length required to reach the last index

B. Determine if you can reach the last index from the first index by jumping

C. Count the total number of jumps needed to reach the end

D. Find the maximum jump length from the first index

Solution

1. Step 1: Understand the problem statement

   The Jump Game problem asks if it is possible to move from the first index to 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 to count jumps or find maximum jump length.

3. Final Answer:

   Determine if you can reach the last index from the first index by jumping -> Option B

4. Quick Check:

   Goal = Reach last index [OK]

Hint: Focus on reachability, not jump counts or lengths [OK]

Common Mistakes:

• Confusing maximum jump length with reachability
• Trying to count jumps instead of checking possibility
• Assuming jumps can go backward

2. Which of the following is the correct syntax to declare an integer array nums of size 5 in C for the Jump Game problem?

easy

A. int[] nums = new int[5];

B. int nums = [5];

C. int nums(5);

D. int nums[5];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared by specifying the type, name, and size in square brackets, like int nums[5];.

2. Step 2: Check each option

   int nums[5]; matches correct C syntax. int nums = [5]; uses invalid assignment. int nums(5); uses parentheses which is incorrect. int[] nums = new int[5]; is Java syntax.

3. Final Answer:

   int nums[5]; -> Option D

4. Quick Check:

   C array syntax = int nums[5]; [OK]

Hint: Use type name[size] for arrays in C [OK]

Common Mistakes:

• Using Java or C++ style array declarations
• Using parentheses instead of square brackets
• Assigning array size with equals sign

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

int nums[] = {2, 3, 1, 1, 4};
int n = 5;
int maxReach = 0;
for (int i = 0; i < n; i++) {
    if (i > maxReach) {
        printf("false\n");
        return 0;
    }
    if (i + nums[i] > maxReach) {
        maxReach = i + nums[i];
    }
}
printf("true\n");

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Trace the loop and maxReach updates

   Start with maxReach=0. At i=0, maxReach = max(0, 0+2)=2. i=1 ≤ 2, maxReach = max(2,1+3)=4. i=2 ≤ 4, maxReach = max(4,2+1)=4. i=3 ≤ 4, maxReach = max(4,3+1)=4. i=4 ≤ 4, maxReach = max(4,4+4)=8.

2. Step 2: Check if loop completes without returning false

   Since i never exceeds maxReach, loop completes and prints "true".

3. Final Answer:

   true -> Option A

4. Quick Check:

   maxReach covers all indices = true [OK]

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

Common Mistakes:

• Stopping early without updating maxReach
• Confusing index with jump length
• Assuming false if maxReach equals index

4. Identify the bug in the following C code snippet for the Jump Game problem:

int canJump(int* nums, int n) {
    int maxReach = 0;
    for (int i = 0; i <= n; i++) {
        if (i > maxReach) return 0;
        if (i + nums[i] > maxReach) maxReach = i + nums[i];
    }
    return 1;
}

medium

A. Return values should be swapped (1 for false, 0 for true)

B. maxReach should be initialized to -1

C. Loop condition should be i < n, not i <= n

D. nums array should be declared inside the function

Solution

1. Step 1: Analyze the loop condition

   The loop runs from i=0 to i<=n, which means it accesses nums[n], an out-of-bounds index causing undefined behavior.

2. Step 2: Correct the loop condition

   The loop should run while i < n to avoid accessing beyond the array.

3. Final Answer:

   Loop condition should be i < n, not i <= n -> Option C

4. Quick Check:

   Array index in bounds = i < n [OK]

Hint: Loop up to n-1 to avoid out-of-bounds access [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring array boundary checks
• Incorrect return values for boolean

5. Given the array nums = {3, 2, 1, 0, 4}, why does the standard greedy Jump Game algorithm return false for reachability?

hard

A. Because index 3 has a jump length of 0, blocking further progress

B. Because the array length is less than 5

C. Because the first element is too large

D. Because the last element is unreachable due to negative jumps

Solution

1. Step 1: Trace jumps from start

   Start at index 0 with jump length 3, maxReach = 3. Indices 1, 2, 3 are reachable. At index 3, jump length is 0, so maxReach stays 3.

2. Step 2: Check if last index is reachable

   Last index is 4, which is beyond maxReach 3, so it is unreachable, causing the algorithm to return false.

3. Final Answer:

   Because index 3 has a jump length of 0, blocking further progress -> Option A

4. Quick Check:

   Zero jump blocks path = false [OK]

Hint: Zero jump at reachable index blocks reaching the end [OK]

Common Mistakes:

• Ignoring zero jump blocking
• Assuming array length affects reachability
• Thinking negative jumps exist in problem