Jump Game Problem in DSA C - Execution Trace

Concept Flow - Jump Game Problem

Start at index 0

↓

Check if current index can reach end?

Yes→Return True

No↓

From current index, check all reachable next indices

↓

For each next index, repeat check

↓

If no next index leads to end

→Return False

Start from the first position, check if you can jump to the end or to positions that can reach the end, repeat until success or no moves left.

Execution Sample

DSA C

bool canJump(int* nums, int numsSize) {
    int lastPos = numsSize - 1;
    for (int i = numsSize - 2; i >= 0; i--) {
        if (i + nums[i] >= lastPos) lastPos = i;
    }
    return lastPos == 0;
}

Checks from the end if each position can reach the last known reachable position, updating it backward.

Execution Table

Step	Operation	Index i	nums[i]	Last Reachable Position	Action	Visual State
1	Initialize lastPos	-	-	4	Set lastPos to last index	[0,3,1,1,4]
2	Check index	3	1	4	3 + 1 >= 4 → Update lastPos to 3	[0,3,1,1,4]
3	Check index	2	1	3	2 + 1 >= 3 → Update lastPos to 2	[0,3,1,1,4]
4	Check index	1	3	2	1 + 3 >= 2 → Update lastPos to 1	[0,3,1,1,4]
5	Check index	0	0	1	0 + 0 >= 1 → No, lastPos stays 1	[0,3,1,1,4]
6	Result	-	-	1	lastPos == 0? No → Return False	[0,3,1,1,4]

💡 Reached start index; lastPos is 1, not 0, so cannot jump to end from start.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
lastPos	4	3	2	1	1	1
i	-	3	2	1	0	-

Key Moments - 3 Insights

Why do we update lastPos only when i + nums[i] >= lastPos?

Because lastPos tracks the earliest position that can reach the end. If from i we can jump to lastPos or beyond, then i itself can reach the end, so we update lastPos to i (see steps 2-5 in execution_table).

Why do we start checking from the end of the array?

Starting from the end lets us know which positions can reach the end. We move backward to find if the start can eventually reach the end (see step 1 initialization and backward loop in code).

What does it mean if lastPos is not zero at the end?

It means the start index cannot reach the end because lastPos marks the earliest reachable position to the end, and if it's not zero, the start can't jump to it (see step 6 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of lastPos?

A 2

B 1

C 3

D 4

💡 Hint

Check the 'Last Reachable Position' column at step 4 in execution_table.

At which step does the lastPos first update to 3?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look at the 'Action' column and see when lastPos changes from 4 to 3.

If nums[0] was 1 instead of 0, what would be the final lastPos value?

A 0

B 1

C 2

D 4

💡 Hint

If nums[0] = 1, then at step 5 condition i + nums[i] >= lastPos would be true, updating lastPos to 0.

Concept Snapshot

Jump Game Problem:
- Given array nums, each element is max jump length.
- Goal: Can start index reach last index?
- Approach: Track last reachable position from end backward.
- Update lastPos if current index can jump to lastPos.
- Return true if lastPos reaches 0, else false.

Full Transcript

The Jump Game problem asks if you can jump from the start of an array to the end, given each element's max jump length. We solve it by starting from the end and moving backward, tracking the earliest position that can reach the end. We update this position if the current index can jump to it or beyond. If by the time we reach the start index, this position is zero, it means we can jump to the end. Otherwise, we cannot. The code initializes lastPos to the last index, then loops backward checking if each index can reach lastPos. If yes, lastPos updates to that index. Finally, it returns true if lastPos is zero. The execution table shows step-by-step how lastPos changes and why the function returns false for the example input.

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