Leetcode 55 Solution

This article provides solution to leetcode question 55 (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

which means we can jump to the end.

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

Current LocationJumpCurrent Possible Farthest Location

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)


class Solution {
    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;