# 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

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

Last updated