Leetcode 55 Solution

Leetcode Question Link

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:

which means we can jump to the end.

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

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;
    }
};