Question

Formatted question description: https://leetcode.ca/all/55.html

55	Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [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: [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.


@tag-array
@tag-greedy

Algorithm

Greedy Algorithm, because here is not very concerned about the number of remaining steps at each position, but only want to know whether we can reach the end, that is to say we are only interested in the farthest reachable position.

So we maintain a variable reach, represents the farthest reachable position, initialized to 0. Traverse each number in the array,

  • if the current coordinate is greater than reach or reach has reached the last position, then jump out of the loop,
  • otherwise update the value of reach to the larger value of i + nums[i], where i + nums[i] indicates the maximum position that the current position can reach.

Code

Java

public class Jump_Game {


    class Solution {
        public boolean canJump(int[] nums) {

            if (nums == null || nums.length == 0) {
                return false;
            }

            int reach = 0;
            for (int i = 0; i < nums.length; i++) {
                // first judge, whether the last reach can reach the new i
                if (reach >= nums.length - 1 || reach < i) { // i > reach, meaning cannot reach
                    break;
                }

                reach = Math.max(reach, i + nums[i]);
            }

            return reach >= nums.length - 1;

        }
    }


    class Solution_dp {
        public boolean canJump(int[] nums) {

            if (nums == null || nums.length == 0) {
                return false;
            }

            // 其中 dp[i] 表示达到i位置时剩余的跳力,若到达某个位置时跳力为负了,说明无法到达该位置
            int[] dp = new int[nums.length];

            for (int i = 1; i < nums.length; i++) { // @note: start from 1, because already at index=0
                dp[i] = Math.max(dp[i - 1], nums[i - 1]) - 1;

                if (dp[i] < 0) {
                    return false;
                }
            }

            return true;

        }
    }

}

All Problems

All Solutions