Skip to content
AI360Xpert
Back to Greedy
Medium

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.

Examples

Input:nums = [2,3,1,1,4]
Output:true
Jump 1 step from index 0 to 1, then 3 steps to the last index.
Input:nums = [3,2,1,0,4]
Output:false
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

Greedy Approach

Approach

We can work backwards from the last index to the first index. We maintain a `goal` index, which is initially the last index. We iterate from the second-to-last index down to the first index. At each step `i`, we check if we can reach the `goal` from `i` (i.e., `i + nums[i] >= goal`). If we can, we update the `goal` to be `i` because if we can reach `i`, we can reach the original `goal`. At the end, if the `goal` has reached index `0`, it means we can reach the end from the beginning.

Complexity Analysis

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

Time complexity is O(n) because we do a single backward pass through the array. Space complexity is O(1) as we only need one variable to store the goal.

Solution.java
class Solution {    public boolean canJump(int[] nums) {        int goal = nums.length - 1;                for (int i = nums.length - 2; i >= 0; i--) {            if (i + nums[i] >= goal) {                goal = i;            }        }                return goal == 0;    }}