5-line O(N) one pass solution with early termination (with explanation)


  • 0

    Key observation: all reachable indices must be consecutive, i.e., if we can jump to index i, we can jump to any index j which are fewer than i.

    The variable maxReach denotes the current maximum reachable index. Then we only need to update to check if maxReach >= n-1 eventually.

        bool canJump(vector<int>& nums) {
            int n = nums.size(), maxReach = 0;
            for (int i = 0; i < n; i++)
                if (i <= maxReach && maxReach < n-1) maxReach = max(maxReach, i+nums[i]);
                else return maxReach >= n-1;
            return true;
        }
    

Log in to reply
 

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