- Shortest path, apparently we need BFS.
- It’s easier to write a classic BFS template, but it cannot pass cases like,
- We did so many extra work with unnecessary 7.
- We need to skip
- For sequences with the same value, we only need the
- 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.
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
queuewith a tmp array at the end.
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.
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]