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

• Most of the solutions I've seen looks for the maximum reachable index and then checks for `n-1`.

• 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])``

• This post is deleted!

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

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