hardGraphsPure DSA~30 min
Fewest Jumps with Value Teleports
You hop along an array of node labels. From an index you can step left, step right, or teleport to any other index sharing the same label. Reach the last index in the fewest hops.
Problem
Given an integer array arr, starting at index 0 you may move from index i to i+1, i-1 (within bounds), or to any index j != i with arr[j] == arr[i]. Return the minimum number of steps to reach the last index.
Input
An integer array arr.
Output
An integer: the minimum number of steps to reach index n-1.
Constraints
- 1 <= arr.length <= 50000
- -10^8 <= arr[i] <= 10^8
Examples
Example 1
Input
arr = [100,-23,-23,404,100,23,23,23,3,404]
Output
3
0 -> 4 (same value 100) -> 3 -> 9 (same value 404), three steps.
Example 2
Input
arr = [7]
Output
0
Already at the last index.