My 5 lines DP solution in O(n) time with constant space, 19ms.


  • 5

    This a DP solution, and the idea is to save the maximum jump length every time, if the maximum length be zero, than return false.

    class Solution {
    public:
        bool canJump(std::vector<int> &nums) {
    		int maxJumpNow = 0, len = static_cast<int>(nums.size());
            for (int i = 0; i < len - 1 && maxJumpNow < len - i; ++i)
                if (!(maxJumpNow = std::max(maxJumpNow - 1, nums[i])))
                    return false;
            return true;
        }
    };

  • 0
    S

    Brilliant solution! I did a recursive function and even after all the optimizations, could not clear the benchmark test. This is simple and elegant.


  • 8
    J

    Same idea, but doesn't change the original array.

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

  • 0

    Cleverer, there is no need to change the original array.


  • 1
    R

    this is exactly what i came up with too.. but I also put a check on updated A[i] (variable d in my case) if greater than n-1-i , then done..no need to process it further. Here is my code

    class Solution {
    public:
        bool canJump(int A[], int n) {
            int i=0;
            if(n==1)
                return true;
            if(A[0] == 0)
                return false;
            //start observing from pos 1 (0 is handled in base case)
            i = 1;
            int d = A[0]; //d is max jump at previous position
            while(i < n) {
                d = max(d-1,A[i]); //everytime decrease jump by 1 and check for max
                if(d >= (n-1-i)) //if you can jump till end - done!
                    return true;
                if(d == 0) //if you can't jump anymore - done!
                    return false;
                i++;            
            }           
        }
    };

  • 0

    Solid consideration!


  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.