# Leetcode 1345 - Jump Game IV

`Note:`

- Shortest path, apparently we need BFS.
- It’s easier to write a classic BFS template, but it cannot pass cases like,
`[7,7,7,7,7,7....,7,7]`

. - We did so many extra work with unnecessary 7.
- We need to skip
`inbetween 7s`

! - For sequences with the same value, we only need the
`start`

and`end`

! - Skip over the middle ones because there is no way shorter from those inbetween ones to our end!
- We def would spend extra steps to get to the middle ones first.
- Also,
`delete arr[i]`

key from map after we have added all indexes with the same val to our queue. - Note that to save speed, avoid using
`shift()`

on queue, instead reassign`queue`

with a tmp array at the end.

`Question:`

Given an array of integers `arr`

, you are initially positioned at the first index of the array.

In one step you can jump from index i to index:

- i + 1 where: i + 1 < arr.length.
- i - 1 where: i - 1 >= 0.
- j where: arr[i] == arr[j] and i != j.

Return the minimum number of steps to reach the `last index`

of the array.

Notice that you can not jump outside of the array at any time.

`Example:`

1 | Input: arr = [100,-23,-23,404,100,23,23,23,3,404] |

`Code:`

1 | /** |