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.