C++ O(n) solution with comments.


  • 6
    C
    bool canJump(vector<int>& nums) {
        unsigned int maxReach = 0;
        for (unsigned int i = 0; i < nums.size(); i++) {
            if (maxReach < i)  // cannot reach i 
                return false;
            if (maxReach >= nums.size()-1)
                return true;  //early return 
            maxReach = max(maxReach, i+nums[i]);
        }
        return true;
    }

  • 0
    T

    You should indicate in title that this solution uses shortcuts to behave better on in case there's a huge jump ahead ([1000000, 0 x 999999]) or when it's not reachable at all [1, 0 x 1000000] unlike other O(n) solution I've checked.


Log in to reply
 

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