C++ O(n) solution with comments.

  • 6
    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

    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.