Leetcode: 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.

Understand the problem:
The problem gives an array of non-negative integers. Each element represents the maximum jump length you can reach. Determine if you can reach the last index. Besides the two normal examples shown above, we can take another several ones to illustrate the problem. 

For A= [0,1,1], return false, since the first element is false, you can never jump to the following elements. 

For A= [1, 1, 0, 2, 3], return false, because we stop at the 0. 

Solution:
Based on the analysis above, we can see that the basic idea is to iterate the array elements, note down the maximum steps we can reach for each index. Then determine if the maximum length is greater or equals to  the index of last element. 

Code (Java):

public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        if (A[0] == 0 && A.length > 1) {
            return false;
        }
        
        int max = 0;
        for (int i = 0; i < A.length; i++) {
            if (i <= max && i + A[i] > max) {
                max = i + A[i];
            } else if (i > max) {
                return false;
            }
        }
        
        return max >= A.length - 1;
    }
}

Discussion:
The key of the problem is the if condition in the for loop. Make sure the current element is within the maximum length you can reach; else we can never ever reach that point. 

Summary:
Understand the problem correctly is the key to this problem. In such kind of abstracted question, make sure you can think of every corner cases. A rule of thrumb is to take examples, in normal, negative, and extreme cases. 

Update on 10/11/14:

public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return true;
        }
        
        return canJumpHelper(0, A);
    }
    
    private boolean canJumpHelper(int index, int[] A) {
        if (index >= A.length) {
            return true;
        }
        
        for (int i = 1; i <= A[index]; i++) {
            if (canJumpHelper(index + i, A) == true) {
                return true;
            }
        }
        
        return false;
    }
}

A DP Solution:

public class Solution {
    public boolean canJump(int[] A) {
        if (A == null || A.length == 0) {
            return true;
        }
        
        if (A[0] == 0 && A.length > 1) {
            return false;
        }
        
        boolean[] dp = new boolean[A.length];
        dp[0] = true;
        
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] == true && j + A[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[A.length - 1];
        
    }
}

Update on 9/22/15:
A Greedy algorithm with O(n) time complexity:

public class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null || nums.length == 0) {
            return true;
        }
        
        int maxReach = 0;
        for (int i = 0; i <= maxReach && i < nums.length - 1; i++) {
            if (i + nums[i] > maxReach) {
                maxReach = i + nums[i];
            }
        }
        
        return maxReach >= nums.length - 1;
    }
}

Update on 2/12/16:

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