55 Jump Game

You are given an integer array nums. You are initially positioned at the first index, and each element in the array represents your maximum jump length from 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

Solution

We keep track of the farthest index we can reach (maxReach) as we iterate. If at any point the current index is greater than maxReach, it means we cannot move forward and should return false. If we finish the loop without this happening, we can reach the last index.

---

Step-by-Step Example: Input: nums = [2,3,1,1,4]

i=0: maxReach = max(0, 0+2) = 2
i=1: maxReach = max(2, 1+3) = 4
i=2: maxReach = max(4, 2+1) = 4
Since maxReach >= last index (4), return true.

---

Complexity Analysis:

• Time Complexity: O(n)
  We iterate through the array once.
• Space Complexity: O(1)
  Only one variable maxReach is used.

Java Solution:

class Solution {
    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;
    }
}

---

Kotlin Solution:

class Solution {
    fun canJump(nums: IntArray): Boolean {
        var maxReach = 0
        for (i in nums.indices) {
            if (i > maxReach) return false
            maxReach = maxOf(maxReach, i + nums[i])
        }
        return true
    }
}

---

Scala Solution:

import scala.util.boundary, boundary.break
object Solution {
    def canJump(nums: Array[Int]): Boolean = boundary {
        var maxReach = 0
        for (i <- nums.indices) {
            if (i > maxReach) boundary.break(false)
            maxReach = math.max(maxReach, i + nums(i))
        }
        true
    }
}

---

JavaScript Solution:

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

---

TypeScript Solution:

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

---