[LeetCode][python3]Day25. Jump Game (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.25

1. My solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        l=len(nums)
        index=0
        maxpath=nums[0]
        while index<l and index<=maxpath:
            maxpath=max(maxpath,index+nums[index])
            index+=1
        if index!=l:
            return False
        return True

Explanation:

The Solution records the furthest index maxpath it could reach, then check every item between it to modify the maxpath.

2. A Faster Solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        N = len(nums)
        
        target = N-1
        for i in range(N-1, -1, -1):
            if i + nums[i] >= target:
                target = i
                
        return target == 0

Explanation:

This is faster because we check two conditions for the while loop in the first solution, but this use a for loop instead.

3. A Cool Solution

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # problem becomes, will we eventually get stuck on nums[i] == 0
        # if nums[i] = 0, need to check nums[i-k] > k
        # if satisfied, move on to find next zero
        # if not satisfied until nums[0], return false
        
        # if array length 1, already at last index
        if len(nums) == 1: return True
        # if array length not 1, and nums[0] is zero, we're already stuck
        if nums[0] == 0: return False
        
        # if last element is zero, we don't need to check it, we're guaranteed
        # to reach it if nums[-2] is not zero, if nums[-2] is zero, we'll be 
        # checking later in this code whether we're stuck at it or not,
        # if we'll be stuck at it, program will return False anyways.
        if not nums[-1]:
            nums.pop()
        
        # if there's no 0 in nums, automatically True
        if 0 not in nums: return True
        
        # start from tail
        i = len(nums)-1
        while i > 0:
            # look for zero, we only check if elements to the left of zero
            # will get stuck at it
            if nums[i]:
                i -= 1
                continue
            zero = i # i index is zero
            # while elements to the left of zero can only reach this zero or shorter
            # we keep going left to look for a number that can jump past this zero
            # if we find it, we go to top of while loop to look for another zero
            while i >= 0 and nums[i] <= zero - i:
                i -= 1
            # if we are not able to find this number that can jump past zero at nums[0]
            # i will change into -1, this is the only condition we fail the jump game.
            if i == -1: return False
        # if no failure is found, it means all zero can be jumped past, so we can win.
        return True

Explanation:

The main idea is to check every 0 in the array. If any one of them can’t be overcome, then return false. You can see the details in the script.