Simplest O(N) solution with constant space


  • 108
    L

    Idea is to work backwards from the last index. Keep track of the smallest index that can "jump" to the last index. Check whether the current index can jump to this smallest index.

    bool canJump(int A[], int n) {
        int last=n-1,i,j;
        for(i=n-2;i>=0;i--){
            if(i+A[i]>=last)last=i;
        }
        return last<=0;
    }

  • 0
    A

    In the last line, return last==0 should do, isn't it ?


  • 4
    L

    In case n is zero


  • 0
    D

    excellent code!


  • 7
    Z

    nit: j is not used in the code.


  • 8

    I solve most of the questions, but when i look into the solutions. I always end up thinking, "WHY DID I NOT THINK OF THIS BEFORE".


  • 25
    E

    Great solution. One possible improvement is that your loops runs for n times no matter what. This might not be necessary if we compute from start to end. The idea is: whenever we realize that we cannot reach a point i, return false.

    Code in Java:

    public boolean canJump(int[] nums) {
        int maxLocation = 0;
        for(int i=0; i<nums.length; i++) {
            if(maxLocation<i) return false; // if previous maxLocation smaller than i, meaning we cannot reach location i, thus return false.
            maxLocation = (i+nums[i]) > maxLocation ? i+nums[i] : maxLocation; // greedy:
        }
        return true;
    }

  • 4
    W

    I guess you can also add " if (maxLocation > nums.length) return true" to break the loop earlier.


  • 2
    O

    Just post my notes fyi, and the python implementation

    if you think from the front, it can't be a greedy solution
    however, if you think from the back, it IS greedy, why?

    when you are at index i, you can jump to index i + nums[i]
    so backwardly, the first goal is jumping to the index, target == len(nums) - 1
    if you find a index i, s.t. i + nums[i] >= len(nums) - 1, which means that as long as we can somehow greedily find a index j, s.t. j + nums[j] >= i, then we can sure we can jump from j to i.
    So we simply change target to i, and continuously doing backward!!
    And in the end, since we are in the index 0 at the begining, and we keep updating our goal to i,
    which means that if we (somehow) can jump to 0, which we already did, then we must be able to jump to len(nums) - 1!!

            target = len(nums) - 1
            for i in range(len(nums) - 2, -1, -1):
                if i + nums[i] >= target:
                    target = i
            return target == 0
    

  • 0

    farest is the farest index that the last index can reach.

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

  • 0
    C

    the description says that you are initially positioned at the first index so I wonder if your solution is legible


  • 0

    Similar Idea.

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

Log in to reply
 

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