H-Index - LeetCode Solution in C++, Java, Python

1. Introduction

The "Jump Game" problem tests the ability to determine if it's possible to reach the end of an array given that each element represents the maximum jump length from that position. This problem is a typical example of a greedy algorithm.

2. Problem

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true if you can reach the last index, or false otherwise.

3. Solution in C++

bool canJump(vector<int>& nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (i > maxReach) return false; // Can't reach this point
        maxReach = max(maxReach, i + nums[i]);
    }
    return true;
}

Explanation:

1. Initialize maxReach to 0, indicating the furthest point that can be reached.

2. Iterate through the array.

3. If the current index is greater than maxReach, return false as it's impossible to reach this point.

4. Update maxReach with the maximum value between the current maxReach and the furthest point that can be reached from the current index (i + nums[i]).

5. If the loop completes without returning false, it's possible to reach the end, so return true.

4. Solution in Java

public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

Explanation:

1. Initialize maxReach to track the furthest index that can be reached.

2. Iterate through nums.

3. If the current position is beyond maxReach, return false.

4. Update maxReach to the maximum of its current value and the furthest point reachable from the current index.

5. If the loop finishes, true is returned, indicating the end is reachable.

5. Solution in Python

def canJump(nums):
    maxReach = 0
    for i, num in enumerate(nums):
        if i > maxReach:
            return False
        maxReach = max(maxReach, i + num)
    return True

Explanation:

1. maxReach keeps track of the furthest index that can be reached.

2. Loop through nums using enumerate to get both index and value.

3. If the current index is beyond maxReach, it's not possible to reach this index, return False.

4. Update maxReach to be the maximum of itself and the furthest index that can be reached from the current position.

5. Return True if the loop completes, indicating the last index is reachable.