Jump Game

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.

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.

Solutions

Problem Statement: Imagine you’re playing a video game where you can jump from one platform to another. Each platform has a number on it that represents the maximum distance you can jump forward from that platform. You start at the first platform and your goal is to reach the last platform.

For example, if the platforms are represented by the array [2,3,1,1,4], you start on the platform with the number 2 (which means you can jump to either the next platform or the one after that), then if you jump to the platform with the number 3 (which means you can jump up to three platforms forward), and so on. The question is: can you reach the last platform?

Solution Explanation: The solution uses a “greedy” approach, which means it makes the locally optimal choice at each stage with the hope that these local choices will lead to a global optimum.

It starts from the last platform and moves backwards. For each platform, it checks if there’s a jump that could have come from a platform further back. If there is, it moves the “start” back to that platform. It continues this until it gets to the first platform.

In other words, it’s like you’re playing the game in reverse: starting from the last platform and jumping backwards. The question now is: can you get back to the first platform?

If you can, that means there’s a path from the first platform to the last one (because you can just reverse the jumps). If you can’t, that means there’s no way to reach the last platform from the first one.

public class Solution {
    public bool CanJump(int[] nums) {
        int lastPos = nums.Length - 1;
        for (int i = nums.Length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

Complexity

• Time complexity: O(n)

• Space complexity: O(1)