# 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:

Code: