Simple C++ solution with explanation


  • 1
    B

    I've tried several solutions for this problem:

    1. Recursion ( Time Limit Exceeded )

    From the start point, we need to determine if we can jump to the target (which is the last index). Given the current position, the size range that we can jump is [0, nums[i]], so now the problem can be changed to Given the position i+1, i+2, i+3 ... i+nums[i], is there a way to reach the target ? -- This problem can be coded naturally by recursion.

    bool canJump2(vector<int>& nums) {
            if (nums.empty())
                return false;
            return canJump_recur(nums, 0, nums.size()-1);
    }
    
    bool canJump_recur(vector<int>& nums, int start, int target) {
            if (start == target)
                return true;
    
            for (int i = 1; i <= nums[start]; ++i) {
                if (canJump_recur(nums, start+i, target))
                    return true;
            }
            return false;
    }
    

    Unfortunately, it gets Time Limit Exceeded error.

    1. Caching the result while doing recursion ( Time Limit Exceeded )

    This is actually an improvement to the recursive solution, we just maintain a data structure to save the result at each index, this will save us from doing a lot of unnecessary function calls, but still got Time Limit Exceeded error.

    1. Iterate from end to start

    For each index i (start at nums.size()-2), if it can reach the target, then we treat it as the new target;
    If not, just continue to check the previous index.
    We can determine the result by checking if the target equals to start point (which is 0 for this case).

    Attention that with either condition, we make the problem's size one index less, thus it'll eventually get solved.

    This idea is so simple which makes the codes really short, it does one pass without any extra space.
    Time complexity: O(n)
    Space complexity: O(1)

    bool canJump(vector<int>& nums) {
            int target = nums.size()-1;
    
            for (int i = target-1; i >= 0; --i) {
                if (nums[i]+i >= target)
                    target = i;
            }
            return target == 0;
    }
    

Log in to reply
 

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