[Leetcode] 55. Jump Game

Medium

 

Intuition:

The problem might seem like a search problem at first because you are looking for a possible leap paths to the final index. But really, you just have to return the boolean value, so by thinking about maximum possible jumps, one can do this in linear time easily. Feels like some kind of greedy algorithm will work here.

 

My solution:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cur_max = 0
        for i, num in enumerate(nums):
            if i <= cur_max:
                cur_max = max(cur_max, i + num)
            else:
                return False
        return True

 

At the start, we can jump to 1 at most, so we set cur_max to 0. Then we enumerate each element in the row checking if the current index can be reached by the current max jump range. If it cannot be reached, we just return False since the current index is not reachable and thus other farther down indexes surely cannot be reached as well. If it is reachable, then we update the current max jumpable index. We compare the current max value to the i + num, which is current index + jumpable distance. If we have ended the loop, this function should return True as the loop completed without returning False, meaning every index was reachable. The concept of greedy algorithm is important here as we are just marking maximum reachable distance/position.

 

Time complexity: O(n)

Space complexity: O(1)

 

Crowdsourced solution:

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        gas = 0
        for n in nums:
            if gas < 0:
                return False
            elif n > gas:
                gas = n
            gas -= 1
            
        return True

This is the most upvoted solution on Leetcode. Instead of setting the max reachable index, it adds a concept of gas, or amount of pace you can have. I think it conceptually is same as mine in that it greedily replaces the amount of gas at each index, and has the same time / space complexity. But this does finish marginally faster than my solution (~350ms vs ~370ms). Might be related to the use of max function, so once I changed it to this

                if cur_max < i + num:
                    cur_max = i + num
                # cur_max = max(cur_max, i + num)

the runtime basically became the same.