Jump Game

Problem Statement

In this challenge, an integer array nums is provided where each element represents the maximum jump length from that index in the array. You start from the first index of this array. The task is to determine whether it's possible to jump from the beginning to the last index based solely on the jump lengths defined by the elements of the array. The function should return true if reaching the last index is possible, and false if it's not.

Examples

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 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints

• 1 <= nums.length <= 104
• 0 <= nums[i] <= 105

Approach and Intuition

Understanding the problem involves grasping the way jumps can be made based on the value at each array index and the constraints imposed on those values:

1. Initial Setup: You start at the first index of the array. Your goal is to make jumps to other indices using the numbers at current index which tells how far you can jump maximum from that index.

2. Progressing through the array:

   • At any index, the number represents the maximum length of the jump you can make.
   • If the number at the current index is 0, and it's not the last index, you cannot progress further.
   • You aim to jump in such a way that you either reach or surpass the last index.
   • You should also aim to make the maximum progress with each jump without missing the potential earlier exits.

3. Greedy Solution Strategy:

   • Keeping the current furthest reachable index updated will help plan the next jump.
   • If at any point, the current index exceeds the furthest reachable index computed so far and it still hasn’t reached the end of the array, then the last index is unreachable.
   • Each position in the array updates the furthest reachable index to its maximum possible value based on the maximum jump length permissible from that position.

Constructing the Intuition

• The approach can be thought of as a greedy strategy — you always jump to the position where you can go farthest next, updating your reach in the process.
• For example, in nums = [2,3,1,1,4]: starting from index 0, the value is 2, allowing potential reach to index 2. From index 1 or 2, seeing the values and calculating the maximal reach incrementally ensures whether you can surpass the last index.

In summary, your ability to reach or surpass the last index relies heavily on making optimal jumps based on the current maximum reach and recalculating the possibilities as you move through the array.

Solutions

class Solution {
public:
    bool canReachEnd(vector<int>& jumps) {
        int goal = jumps.size() - 1;
        for (int idx = jumps.size() - 1; idx >= 0; idx--) {
            if (idx + jumps[idx] >= goal) {
                goal = idx;
            }
        }
        return goal == 0;
    }
};