Jump Game In C,CPP,JAVA,PYTHON,C#,JS

Problem Statement: Jump Game

You are given an integer array nums. Each element in the array represents your maximum jump length from that position. You start at the first index of the array.

• Return true if you can reach the last index, otherwise return false.

Example 1:

Input:

nums = [2, 3, 1, 1, 4]

Output:

true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

---

Example 2:

Input:

nums = [3, 2, 1, 0, 4]

Output:

false

Explanation: You will always arrive at index 3. It’s maximum jump length is 0, which means you can’t move further.

Approach:

This problem can be solved using a greedy approach. The idea is to keep track of the farthest index that you can reach at each step. If at any point, you are able to reach or surpass the last index, return true. If you can’t reach the last index by the time you process the entire array, return false.

Key Ideas:

1. Initialize a variable max_reach to keep track of the farthest index you can jump to.
2. Traverse the array, for each index i:
   • If i is greater than max_reach, it means you can’t reach index i, so return false.
   • Update max_reach as the maximum of max_reach and i + nums[i].
3. If at any point max_reach reaches or exceeds the last index, return true.

Time Complexity:

• Time Complexity: O(n), where n is the number of elements in the array. We only traverse the array once.
• Space Complexity: O(1), since we use only a few variables to track the farthest position.

Algorithm:

1. Initialize max_reach as 0.
2. Iterate through the array:
   • If i > max_reach, return false (you can’t move beyond this point).
   • Update max_reach as max(max_reach, i + nums[i]).
   • If at any point max_reach >= len(nums) - 1, return true (you can reach or surpass the last index).
3. If you finish iterating without reaching the last index, return false.

---

Code Implementations in Different Languages:

1. C Language:

#include <stdio.h>

int canJump(int* nums, int numsSize) {
    int max_reach = 0;
    
    for (int i = 0; i < numsSize; i++) {
        if (i > max_reach) {
            return 0; // Can't reach index i
        }
        max_reach = (max_reach > i + nums[i]) ? max_reach : i + nums[i];
        if (max_reach >= numsSize - 1) {
            return 1; // Can reach or surpass the last index
        }
    }
    
    return 0; // Can't reach the last index
}

int main() {
    int nums[] = {2, 3, 1, 1, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("Can Jump: %d\n", canJump(nums, size));  // Output: 1 (true)
    return 0;
}

2. C++ Language:

#include <iostream>
#include <vector>
using namespace std;

bool canJump(vector<int>& nums) {
    int max_reach = 0;
    
    for (int i = 0; i < nums.size(); i++) {
        if (i > max_reach) {
            return false; // Can't reach index i
        }
        max_reach = max(max_reach, i + nums[i]);
        if (max_reach >= nums.size() - 1) {
            return true; // Can reach or surpass the last index
        }
    }
    
    return false; // Can't reach the last index
}

int main() {
    vector<int> nums = {2, 3, 1, 1, 4};
    cout << "Can Jump: " << canJump(nums) << endl;  // Output: 1 (true)
    return 0;
}

3. Java:

public class JumpGame {
    public static boolean canJump(int[] nums) {
        int maxReach = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (i > maxReach) {
                return false; // Can't reach index i
            }
            maxReach = Math.max(maxReach, i + nums[i]);
            if (maxReach >= nums.length - 1) {
                return true; // Can reach or surpass the last index
            }
        }
        
        return false; // Can't reach the last index
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        System.out.println("Can Jump: " + canJump(nums));  // Output: true
    }
}

4. Python:

def canJump(nums):
    max_reach = 0
    
    for i in range(len(nums)):
        if i > max_reach:
            return False  # Can't reach index i
        max_reach = max(max_reach, i + nums[i])
        if max_reach >= len(nums) - 1:
            return True  # Can reach or surpass the last index
    
    return False  # Can't reach the last index

# Test case
nums = [2, 3, 1, 1, 4]
print("Can Jump:", canJump(nums))  # Output: True

5. C#:

using System;

public class JumpGame {
    public static bool CanJump(int[] nums) {
        int maxReach = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            if (i > maxReach) {
                return false; // Can't reach index i
            }
            maxReach = Math.Max(maxReach, i + nums[i]);
            if (maxReach >= nums.Length - 1) {
                return true; // Can reach or surpass the last index
            }
        }
        
        return false; // Can't reach the last index
    }

    public static void Main() {
        int[] nums = {2, 3, 1, 1, 4};
        Console.WriteLine("Can Jump: " + CanJump(nums));  // Output: True
    }
}

6. JavaScript:

function canJump(nums) {
    let maxReach = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            return false; // Can't reach index i
        }
        maxReach = Math.max(maxReach, i + nums[i]);
        if (maxReach >= nums.length - 1) {
            return true; // Can reach or surpass the last index
        }
    }
    
    return false; // Can't reach the last index
}

// Test case
const nums = [2, 3, 1, 1, 4];
console.log("Can Jump:", canJump(nums));  // Output: true

Complexity Analysis:

• Time Complexity: O(n), where n is the number of elements in the array. We traverse the array only once.
• Space Complexity: O(1), since we only use a few variables (max_reach).

Conclusion:

This greedy algorithm efficiently solves the Jump Game problem by maintaining the maximum reachable index at each step, ensuring that we can determine if it’s possible to reach the last index with a linear time complexity.