55. Jump Game

Description

Refer to: https://leetcode.com/problems/jump-game/description/

Solution

The solution to this problem is to start at the end and work backwards. As you move backward you want to determine if the current index can be reached by a previous (lower index) item. If it can, then you want to determine if that position can also be reached by a previous (lower index) item. This process is repeated until the start of the list is reached (or not).

The reason to work backword is it eliminates possibilites. By working forward you would potentially check multiple paths to determine if there is a solution. By working backwards only one path needs to be followed. This leads to an O(n) solution.

Examples

Example 1 - No solution

Given the input of: [3, 2, 1, 0, 4] and n is the last index of the list

Index (Element)	Result
n - 1 (0)	Cannot jump to n
n - 2 (1)	Cannot jump to n (jump to n-1)
n - 3 (2)	Cannot jump to n (jump to n-1 or n-2)
n - 4 (3)	Cannot jump to n (jump to n-1 or n-2 or n-3)

No solution found. No element could jump to n

Exampe 2 - Has solution

Given the input: [3,2,2,0,4]

Index (Element)	Result
n - 1 (0)	Cannot jump to n
n - 2 (2)	Can jump to n (jump to n-1 or n). Can anything jump to this position (n - 2)?
n - 3 (2)	Can jump to n - 2. Can anything jump to this position (n - 3)?
n -4 (3)	Can jump to n - 3

Solution found.

Code

from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        dest_index = len(nums) - 1
        prev_index = dest_index - 1
        for i in range(1, len(nums)):
            # Need to substract previous index from destination 
            # index to get the jump distance. 
            if nums[prev_index] >= dest_index - prev_index:
                # if the element can 'jump' to or beyond the destination index then a 
                # potential path has been found. Reset the destination index to this 
                # location. On the next loop it will check if this new destination
                # index is reachable
                dest_index = prev_index
                prev_index = dest_index - 1
            else:
                # the element cannot jump to this location. Try again with a previous
                # element
                prev_index = prev_index - 1

        # If destination index is set to 0 then a path was found to the start of the list. 
        # Hence there is a path to the end of the list    
        return dest_index == 0

Solution is O(n), O(1).