618. Jump Game IV
You start on index 0 of an integer array arr and want to stand on its last index. In one step, from your current index i you may hop to any of:
i + 1— one position to the right (if it exists),i - 1— one position to the left (if it exists),- any other index
jwitharr[j] == arr[i]— a "teleport" between equal values.
The function receives the array arr and returns the minimum number of steps needed to reach index arr.length - 1. You may never move outside the array, and an array of length 1 needs 0 steps.
Example 1:
Input: arr = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404]
Output: 3
Explanation: Teleport 0 → 4 (both hold 100), walk left 4 → 3, then teleport 3 → 9 (both hold 404). Three steps in total.
Example 2:
Input: arr = [7, 6, 9, 6, 9, 6, 9, 7]
Output: 1
Explanation: arr[0] and arr[7] are both 7, so one equal-value teleport lands directly on the last index.
Constraints:
- 1 ≤ arr.length ≤ 5 * 10⁴
- -10⁸ ≤ arr[i] ≤ 10⁸
Hints:
Model it as a graph: every index is a node, and i−1, i+1, plus all equal-value indices are its neighbors. Minimum steps on an unweighted graph is breadth-first search.
Precompute a hash map from value → list of indices so "every j with arr[j] == arr[i]" is a single lookup instead of a scan.
After you expand a value's index list once, delete it from the map. Every index in it is already discovered, so revisiting the list can only waste time — dropping it is what makes the BFS linear.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: arr = [100, -23, -23, 404, 100, 23, 23, 23, 3, 404]
Expected output: 3