Thinking in reverse: an O(n) time O(1) space solution


  • 1
    T

    Most of the solutions I've seen looks for the maximum reachable index and then checks for n-1.
    What if we instead look for the answer more directly:

    • Can we jump to last from any i?
    • If so, can we jump to i from any i' before that?
    • ... repeating until we're asking whether can we jump to 0?
    • or failing to find any i to jump from.

    Below is an O(n^2) time implementation and it's also an O(n) space deep recursion in the worst case ([1,1,...,1,1,x]):

    public boolean canJumpSlow(int[] nums) {
        return canJumpSlow(nums, nums.length - 1);
    }
    boolean canJumpSlow(int[] nums, int last) {
        if (last == 0) return true;
        for (int i = 0; i < last; ++i) {
            int needToJump = last - i, canJump = nums[i];
            if (needToJump <= canJump) {
                return canJumpSlow(nums, i);
            }
        }
        return false;
    }
    

    By reversing the iteration we can do it in O(n) time, but the O(n) space recursion is still there:

    public boolean canJumpFast(int[] nums) {
        return canJumpFast(nums, nums.length - 1);
    }
    boolean canJumpFast(int[] nums, int last) {
        if (last == 0) return true;
        for (int i = last - 1; i >= 0; --i) {
            int needToJump = last - i, canJump = nums[i];
            if (needToJump <= canJump) {
                return canJumpFast(nums, i);
            }
        }
        return false;
    }
    

    Here's an O(n) time, O(1) space iterative version, which is a simple linear walk (backwards):

    public boolean canJump(int[] nums) {
        int last = nums.length - 1;
        for (int i = last - 1; i >= 0; --i) {
            int needToJump = last - i, canJump = nums[i];
            if (needToJump <= canJump) {
                last = i;
            }
        }
        return last == 0;
    }
    

    I'm curious about insights into how this is equivalent to the DP solutions which look for

    max = max(max, i+nums[i])

  • -1
    C
    This post is deleted!

  • 0
    T

    You missed the point... I asked for how, there are already other 10s of solutions like yours, I know how they look like.

    BTW, there's an std::max you could use that.


Log in to reply
 

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