# Leetcode 55 Solution

https://leetcode.com/problems/jump-game

## Thinking Process

The length of the array `N` is at the scale of `10^4`, so there is no way that we can pass the tests with `O(N^2)` time complexity. So let’s try `O(N)`.

The plan here is to walk the array, while keeping in mind how far we can reach at the current location.

• Everytime you jump to a new location, there is a possibility that you can jump farther, because that location might give you a larger number. So what we do here is to update our current farthest location, and then walk to the next location.
• If we are trying to walk over the currently memorized farthest location, then the game is over, i.e., you can’t jump to the end.

Let’s jump through this example, `[2,3,1,1,4]`. Here’s the jumping process:

Current LocationJumpCurrent Possible Farthest Location
022
134
214
314
448

Another example is, `[3,2,1,0,4]`:

Current LocationJumpCurrent Possible Farthest Location
033
123
213
303

when you jump to location 3, you can’t jump any more, because none of the previous location allow you to make such a jump. So in this example, you can’t jump to the end.

## Time & Space Complexity

Assuming N is the size of the array, the time & space compelxities are:

• Time complexity: `O(N)`
• Space complexity: `O(1)`

## Solution

``````class Solution {
public:
bool canJump(vector<int>& nums) {
int max_pos = 0;

for (int i = 0; i <= max_pos; i++)
{
int new_pos = nums[i] + i;
if (max_pos < new_pos)
{
max_pos = new_pos;
if (max_pos >= nums.size() - 1)
return true;
}
}

return max_pos >= nums.size() - 1;
}
};
``````