LeetCode 55 - Jump Game

Related: LeetCode 45 - Jump Game II
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.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
https://xuezhashuati.blogspot.com/2017/05/55-jump-game.html
We maintains the max distance that we can jump (a greedy algorithm).
If at any position, we find we can jump to here, we set the max distance to be the max of previous max distance and the distance we can jump from the current position.

If we find we can jump to the end, return true.

After trying all positions, we know we have not reach the end, so we return false;X. Greedy
The time complexity is O(n).
https://leetcode.com/articles/jump-game/

Once we have our code in the bottom-up state, we can make one final, important observation. From a given position, when we try to see if we can jump to a GOOD position, we only ever use one - the first one (see the break statement). In other words, the left-most one. If we keep track of this left-most GOODposition as a separate variable, we can avoid searching for it in the array. Not only that, but we can stop using the array altogether.

Iterating right-to-left, for each position we check if there is a potential jump that reaches a GOOD index (currPosition + nums[currPosition] >= leftmostGoodIndex). If we can reach a GOOD index, then our position is itself GOOD. Also, this new GOOD position will be the new leftmost GOOD index. Iteration continues until the beginning of the array. If first position is a GOOD index then we can reach the last index from the first position.

To illustrate this scenario, we will use the diagram below, for input array nums = [9, 4, 2, 1, 0, 2, 0]. We write G for GOOD, B for BAD and U for UNKNOWN. Let's assume we have iterated all the way to position 0 and we need to decide if index 0 is GOOD. Since index 1 was determined to be GOOD, it is enough to jump there and then be sure we can eventually reach index 6. It does not matter that nums[0] is big enough to jump all the way to the last index. All we need is one way.

Index	0	1	2	3	4	5	6
nums	9	4	2	1	0	2	0
memo	U	G	B	B	B	G	G

  public boolean 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;

  }

https://www.cnblogs.com/struggleli/p/6934287.html

    public boolean canJump(int[] A) {
        // think it as merging n intervals
        if (A == null || A.length == 0) {
            return false;
        }
        int farthest = A[0];
        for (int i = 1; i < A.length; i++) {
            if (i <= farthest && A[i] + i >= farthest) {
                farthest = A[i] + i;
            }
        }
        return farthest >= A.length - 1;
    }

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

X. http://bangbingsyb.blogspot.com/2014/11/leetcode-jump-game-i-ii.html

注意题目中A[i]表示的是在位置i，“最大”的跳跃距离，而并不是指在位置i只能跳A[i]的距离。所以当跳到位置i后，能达到的最大的距离至少是i+A[i]。用greedy来解，记录一个当前能达到的最远距离maxIndex：

1. 能跳到位置i的条件：i<=maxIndex。

2. 一旦跳到i，则maxIndex = max(maxIndex, i+A[i])。

3. 能跳到最后一个位置n-1的条件是：maxIndex >= n-1

    bool canJump(int A[], int n) {
        int maxIndex = 0;
        for(int i=0; i<n; i++) {
            if(i>maxIndex || maxIndex>=(n-1)) break;
            maxIndex = max(maxIndex, i+A[i]);
        } 
        return maxIndex>=(n-1) ? true : false;
    }

https://leetcode.com/discuss/22560/java-solution-easy-to-understand

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

From begin to top, the time complexity will be O(n), space will be in O(1)

    bool canJump(int A[], int n) {

        if (0 == n)

            return false;

        

        int cur_max = A[0];

        int i = 0;

        

        while (i <= cur_max) {

            cur_max = max(cur_max, i + A[i]);

            

            if(cur_max >= n - 1)

                return true;

                

            ++i;

        }

        

        return false;

    }

Using Greedy Algorithm

bool canJump(int A[], int n) {

if (0 == n)

            return false;

        int cur_max = A[0];

        int i = 0;

        while (i <= cur_max) {

            cur_max = max(cur_max, i + A[i]);

            

            if(cur_max >= n - 1)

                return true;

                

            ++i;

        }

        return false;

    }

bool canJump(int A[], int n) {       

        if (1 == n)

            return true;

        int i = 0;

        while (i < n)

        {

            int currMax = A[i] + i;

            

            if (0 == A[i])

                return false;

            if (currMax >= n - 1)

                return true;

                

            int tmpMax = 0;

            for (int j = i + 1; j <= currMax; ++j)

            {

                if (A[j] + j > tmpMax)

                {

                    tmpMax = A[j] + j;

                    i = j;

                }

            }

        }

        

        return (i >= n - 1);

    }

X. Approach 2: Dynamic Programming Top-down

enum Index {

  GOOD, BAD, UNKNOWN

}

public class Solution {

  public boolean canJump(int[] nums) {

    Index[] memo = new Index[nums.length];

    for (int i = 0; i < memo.length; i++) {

      memo[i] = Index.UNKNOWN;

    }

    memo[memo.length - 1] = Index.GOOD;

    for (int i = nums.length - 2; i >= 0; i--) {

      int furthestJump = Math.min(i + nums[i], nums.length - 1);

      for (int j = i + 1; j <= furthestJump; j++) {

        if (memo[j] == Index.GOOD) {

          memo[i] = Index.GOOD;

          break;

        }

      }

    }

    return memo[0] == Index.GOOD;

  }

}

bool canJump(int A[], int n) {
        bool ATag[n];
        for (int i = n - 1; i >= 0; --i)
        {
            ATag[i] = false;
            int maxReach = A[i] + i;
         
            if (maxReach >= n - 1)
            {
                ATag[i] = true;
                continue;
            }
         
            for (int j = maxReach; j > i; --j)
            {
                if (ATag[j])
                {
                    ATag[i] = true;
                    break;
                }
            }
        }
        return ATag[0];
    }
http://fisherlei.blogspot.com/2012/12/leetcode-jump-game.html
Just one round DP. No need an array to track the status. Refactor the code.

1:       bool canJump(int A[], int n) {  
2:            int maxCover = 0;  
3:            for(int start =0; start<= maxCover && start<n; start++)  
4:            {  
5:                 if(A[start]+start > maxCover)  
6:                      maxCover = A[start]+start;  
7:                 if(maxCover >= n-1) return true;  
8:            }  
9:            return false;  
10:       }  

http://yucoding.blogspot.com/2013/01/leetcode-question-28-jump-game.html
The simple but time-consuming way is O(n^2). Set every future step true according to the A[i]. 

    bool canJump(int A[], int n) {

        if (n==0) {return false;}

        if (n==1) {return true;}

         

        vector<bool>B(n-1,false);

        B[0]=true;

        for (int i=0;i<n;i++){

            if (B[i]==true){

                for (int j=1;j<=A[i];j++){

                    B[i+j]=true;

                }

            }

        }

        return B[n-1];

    }

http://n00tc0d3r.blogspot.com/2013/03/jump-game.html

 public boolean canJump(int[] A) {  
   if (A.length <= 1) return true;  
   boolean[] canReach = new boolean[A.length];  
   for (int i=A.length-2, dist=1; i>=0; --i, ++dist) {  
     if (A[i] >= dist) {  
       canReach[i] = true;  
     } else {  
       int j=1;  
       while (j<=A[i] && !canReach[i+j]) ++j;  
       if (j<=A[i]) canReach[i] = true;  
     }  
   }  
   return canReach[0];  
 }  

The downside of this algorithm is that it requires O(n^2) time since in worst case we need to check each element within the range. Also, it requires O(n) space.

Do we really need to check each of them? Actually, all we want to know whether the next can-reach-end element is within my range. So, during the iteration, we can store the position of the next can-reach-end element and then for each successor element, we only need to check whether that node is reachable.

 public boolean canJump(int[] A) {  
   int next = A.length - 1;  
   for (int i=A.length-2; i>=0; --i) {   
     if (A[i] >= (next - i)) {   
       next = i;   
     }  
   }   
   return (next == 0);  
 }  

This algorithm runs in time O(n) and uses O(1) space.
X. DFS + Cache

• Time complexity : $O(n^2)$. For every element in the array, say i, we are looking at the next nums[i]elements to its right aiming to find a GOOD index. nums[i] can be at most $n$, where $n$ is the length of array nums.
• Space complexity : $O(2n) = O(n)$. First n originates from recursion. Second n comes from the usage of the memo table. 

enum Index {

  GOOD, BAD, UNKNOWN

}

public class Solution {

  Index[] memo;

  public boolean canJumpFromPosition(int position, int[] nums) {

    if (memo[position] != Index.UNKNOWN) {

      return memo[position] == Index.GOOD ? true : false;

    }

    int furthestJump = Math.min(position + nums[position], nums.length - 1);

    for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {

      if (canJumpFromPosition(nextPosition, nums)) {

        memo[position] = Index.GOOD;

        return true;

      }

    }

    memo[position] = Index.BAD;

    return false;

  }

  public boolean canJump(int[] nums) {

    memo = new Index[nums.length];

    for (int i = 0; i < memo.length; i++) {

      memo[i] = Index.UNKNOWN;

    }

    memo[memo.length - 1] = Index.GOOD;

    return canJumpFromPosition(0, nums);

  }

}

X. Brute Force
Time complexity : $O(2^n)$. There are $2^n$ (upper bound) ways of jumping from the first position to the last, where $n$ is the length of array nums. For a complete proof, please refer to Appendix A.

One quick optimization we can do for the code above is to check the nextPosition from right to left. The theoretical worst case performance is the same, but in practice, for silly examples, the code might run faster. Intuitively, this means we always try to make the biggest jump such that we reach the end as soon as possible

The change required is:

For instance, in the example below, if we start from index 0, jump as far as possible and reach 1, jump as far as possible and reach 6. By doing so, we determine that 0 is a GOOD index in 3 steps.

  public boolean canJumpFromPosition(int position, int[] nums) {

    if (position == nums.length - 1) {

      return true;

    }

    int furthestJump = Math.min(position + nums[position], nums.length - 1);

    for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {

      if (canJumpFromPosition(nextPosition, nums)) {

        return true;

      }

    }

    return false;

  }

  public boolean canJump(int[] nums) {

    return canJumpFromPosition(0, nums);

  }

Read full article from Jump Game