Jump Game

---

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.

---

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

---

Try this Problem on your own or check similar problems:

1. Jump Game II
2. Jump Game III
3. Jump Game VII

Solution:

Java

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

JavaScript

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canJump = function (nums) {
  let maxSoFar = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxSoFar) return false;
    maxSoFar = Math.max(maxSoFar, i + nums[i]);
  }
  return true;
};

Python

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        maxSoFar = 0
        for i in range(len(nums)):
            if i > maxSoFar:
                return False
            maxSoFar = max(maxSoFar, i + nums[i])
        return True

C++

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxSoFar = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > maxSoFar) return false;
            maxSoFar = std::max(maxSoFar, i + nums[i]);
        }
        return true;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

---

Explanation:

The difference between greedy and dynamic programming solutions is that in dynamic programming we optimize for each subproblem, so we can reach the end in the best way, but in greedy we choose local optimum and assume convergence to the global (which is the solution of the problem). In this solution we iterate over the input array elements checking if can reach the current index (if index is larger than our max reachable point, we know that we cannot reach so we return false), we update our local optimum everytime we see we can reach further in the array (starting from the current index, and going nums[i] steps.)