693. Teleport Hops
A warehouse has n teleport pads in a line, numbered from 0, and pad i carries the label arr[i]. In one hop you can walk to the adjacent pad i - 1 or i + 1 (if it exists), or teleport from pad i to any other pad j that carries the same label, arr[j] == arr[i].
You start on pad 0 and want to reach pad n - 1. Return the minimum number of hops needed. If n == 1 the answer is 0. Labels may repeat a huge number of times, so make sure your search never re-scans the same group of equal labels again and again; aim for O(n) time on average.
Example 1
- Input:
- arr = [7,5,5,9,7,3,9]
- Output:
- 3
- Explanation:
Pad 0 teleports to pad 4 (both labelled 7), pad 4 walks to pad 3, and pad 3 teleports to pad 6 (both labelled 9): 3 hops.
Example 2
- Input:
- arr = [4,4,4,4]
- Output:
- 1
- Explanation:
All pads share a label, so pad 0 teleports straight to pad 3 in one hop.
Example 3
- Input:
- arr = [9]
- Output:
- 0
- Explanation:
You already stand on the last pad, so no hops are needed.
Constraints
1 ≤ arr.length ≤ 100000
-108 ≤ arr[i] ≤ 108
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)