Linear and simple solution in C++


  • 212
    A

    I just iterate and update the maximal index that I can reach

    bool canJump(int A[], int n) {
        int i = 0;
        for (int reach = 0; i < n && i <= reach; ++i)
            reach = max(i + A[i], reach);
        return i == n;
    }

  • 1
    L

    Cool!!!!, thanks for share, I run it in my head, and finally get the idea.
    I just wondering how do you get this solution.

    Greedy. the tag of the problem. great.


  • 4
    B
    class Solution:
    # @param A, a list of integers
    # @return a boolean
    def canJump(self, A):
        if not A:
            return False
        
        maxjump=0
        for i in range(len(A)):
            maxjump=max(maxjump-1,A[i])
            if maxjump==0:
                break
        
        return i==len(A)-1
    

    for python


  • 0
    H
    This post is deleted!

  • 24
    H

    Maybe for some special case ,no need to check all elements. A little change to you shearing code.Thx @alexander7

    class Solution {
    public:
      bool canJump(int A[], int n) {
        int i = 0, maxreach = 0;
        for (; i < n && i <= maxreach && maxreach < n - 1; ++i)
          maxreach = max(maxreach,i+A[i]);
        return maxreach>=n-1;
      }
    };

  • 0
    L

    what does maxjump-1 mean?


  • 0
    R

    This is soooooooooooooooo brilliant!


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

    No need to scan whole array when already know we can reach the end.


  • 4

    I think your code may be improved to stop early?

    See below mine:

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

  • 0

    check condition (i <= reach),it's already contain early stop condition..


  • 0
    C

    awesoooooooooooome


  • 0
    R

    brilliant solution


  • 0
    S

    @alexander7 you are great!


  • 2

    same idea different implementation.

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

  • 0
    B

    such a brilliant solution indeed


  • 2
    public class Solution {
        public boolean canJump(int[] nums) {
            return canJump(nums, nums.length);
        }
        
        private boolean canJump(int[] nums, int n) {
            int i = 0;
            // i <= reach, the furthest "start point" that I can reach
            // start point + nums[i] >= n, win!
            // start point + nums[i] < n, lose!
            // so greedy
            for (int reach = 0; i < n && i <= reach; ++i) 
                reach = Math.max(i + nums[i], reach);
            return i == n;
        }
    }
    

  • 0
    M
    This post is deleted!

  • 0
    M

    @alexander7 My mind constraint by the classical game monopoly, but walk one by one step and remember how far I can reach is the key of this problem,thanks for your brilliant solution.


  • 0
    M

    @alexander7
    bool canJump(vector<int>& nums) {
    int n = nums.size() - 1, reach = 0;
    for(int pos = 0; pos <= reach && reach < n; reach = max(nums[pos] + pos++, reach));
    return reach >= n;
    }
    Base on the problem and your solution,I optimized the code,this seems understandable and earlier stop,but I don't know why almost java's solutions are faster than cpp's.


  • 0
    K

    @alexander7 so elegant! Thanks for share!


Log in to reply
 

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