# 55. Jump Game

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.

Given the input of:

`[3, 2, 1, 0, 4]`

and `n`

is the last index of the listIndex (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`

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.

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).

Last modified 4mo ago