Jump Game Problem in DSA C

Mental Model

You start at the first position and want to reach the last by jumping forward. Each number tells you the max steps you can jump from there.

Analogy: Imagine standing on stepping stones across a river. Each stone has a number showing how far you can jump forward. You want to see if you can reach the last stone without falling.

Index: 0   1   2   3   4
Array: [2] [3] [1] [1] [4]
Start ↑

Dry Run Walkthrough

Input: array: [2, 3, 1, 1, 4]

Goal: Determine if you can jump from start (index 0) to the last index (4)

Step 1: Start at index 0 with max jump 2, update furthest reachable to 2

furthest_reach = 2, current index = 0

Why: We can jump up to 2 steps from the first position

Step 2: Move to index 1, max jump 3, update furthest reachable to max(2,1+3)=4

furthest_reach = 4, current index = 1

Why: From index 1, we can jump further, so update the furthest reachable

Step 3: Move to index 2, max jump 1, furthest reachable stays 4

furthest_reach = 4, current index = 2

Why: No need to update since 2+1=3 < 4

Step 4: Move to index 3, max jump 1, furthest reachable stays 4

furthest_reach = 4, current index = 3

Why: No update needed, 3+1=4 equals current furthest

Step 5: Since furthest reachable (4) >= last index (4), return true

Reached last index

Why: We can reach or pass the last index

Result:

true -- can reach last index

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>

bool canJump(int* nums, int numsSize) {
    int furthest_reach = 0;
    for (int i = 0; i < numsSize; i++) {
        if (i > furthest_reach) {
            // Can't move forward anymore
            return false;
        }
        if (i + nums[i] > furthest_reach) {
            furthest_reach = i + nums[i];
        }
        if (furthest_reach >= numsSize - 1) {
            return true;
        }
    }
    return true;
}

int main() {
    int nums[] = {2, 3, 1, 1, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    bool result = canJump(nums, size);
    if (result) {
        printf("true\n");
    } else {
        printf("false\n");
    }
    return 0;
}

if (i > furthest_reach) { return false; }

stop if current index is beyond what we can reach

if (i + nums[i] > furthest_reach) { furthest_reach = i + nums[i]; }

update furthest reachable index if current jump extends it

if (furthest_reach >= numsSize - 1) { return true; }

return true early if we can reach or pass last index

Output

true

Complexity Analysis

Time: O(n) because we scan the array once updating the furthest reachable index

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Compared to recursive or backtracking approaches which can be exponential, this greedy method is much faster and uses less memory

Edge Cases

empty array

returns true because we are already at the last index

DSA C

for (int i = 0; i < numsSize; i++) { ... }

array with one element

returns true because start is last index

DSA C

if (furthest_reach >= numsSize - 1) { return true; }

array where first element is 0 and size > 1

returns false because can't move anywhere

DSA C

if (i > furthest_reach) { return false; }

When to Use This Pattern

When you see a problem asking if you can reach the end by jumping steps defined by array values, use the greedy furthest reachable index pattern to solve efficiently.

Common Mistakes

Mistake: Checking only if the current jump is possible without updating the furthest reachable index
Fix: Always update the furthest reachable index to track the maximum progress

Mistake: Not stopping early when the last index is reachable
Fix: Add a condition to return true as soon as furthest reachable index reaches or passes the last index

Summary

Determines if you can jump from start to end of array using max jump lengths at each position.

Use when you need to check reachability in a jump-based path problem.

Keep track of the furthest reachable index and stop early if you can reach the end.