Jump Game - C Solution

1. Introduction

In this blog post, we delve into a dynamic programming challenge known as the "Jump Game". This problem, often encountered in coding interviews and algorithmic challenges, involves determining whether it's possible to reach the end of an array given each element's maximum jump length. It's a classic problem that tests one's ability to apply dynamic programming techniques and understand array traversal.

Problem

Given an integer array nums, where each element represents the maximum jump length at that position, the task is to determine whether you can reach the last index starting from the first index. The function should return true if it is possible to reach the last index, and false otherwise.

2. Solution Steps

1. Initialize a variable maxReach to keep track of the farthest index that can be reached.

2. Iterate through the array.

3. Update maxReach if the current index plus its jump length can reach farther.

4. If maxReach becomes less than the current index at any point, return false.

5. If maxReach reaches or surpasses the last index, return true.

3. Code Program

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

// Function to check if it's possible to reach the end of the array
bool canJump(int* nums, int numsSize) {
    int maxReach = 0; // Initialize the maximum reachable index

    // Loop through each element in the array
    for (int i = 0; i < numsSize; i++) {
        // If the maximum reachable index is less than the current index, return false
        if (maxReach < i) {
            return false;
        }
        // Update maxReach if the current index can reach farther
        if (i + nums[i] > maxReach) {
            maxReach = i + nums[i];
        }
    }
    return maxReach >= numsSize - 1; // Check if we can reach or surpass the last index
}

// Main function to test the canJump function
int main() {
    int nums1[] = {2, 3, 1, 1, 4};
    int numsSize1 = sizeof(nums1) / sizeof(nums1[0]);
    printf("Can jump (Example 1): %s\n", canJump(nums1, numsSize1) ? "true" : "false");

    int nums2[] = {3, 2, 1, 0, 4};
    int numsSize2 = sizeof(nums2) / sizeof(nums2[0]);
    printf("Can jump (Example 2): %s\n", canJump(nums2, numsSize2) ? "true" : "false");

    return 0;
}

Output:

Can jump (Example 1): true
Can jump (Example 2): false

Explanation:

1. int maxReach = 0; - Initialize the farthest reachable index.

2. for (int i = 0; i < numsSize; i++) - Iterate through each element of the array.

3. if (maxReach < i) - Check if the current position is reachable.

4. if (i + nums[i] > maxReach) - Update maxReach if the current index can reach farther.

5. return maxReach >= numsSize - 1; - Check if the last index is reachable.

6. The main function tests the canJump function with two examples and prints whether it's possible to jump to the end.