1098. Jump Game IV — BFS with Value Groups

Given an array arr, starting at index 0 you may jump to i+1, i-1, or any index j (j != i) with arr[j] == arr[i]. Return the minimum number of jumps to reach the last index. The input is JSON {arr}.

Input: JSON {arr}.

Output: Integer — the minimum number of jumps.

Examples

Input: {"arr":[100,-23,-23,404,100,23,23,23,3,404]}
Output: 3
Explanation: Jump via equal-value groups.

Input: {"arr":[7]}
Output: 0
Explanation: Already at the end.

Input: {"arr":[7,6,9,6,9,6,9,7]}
Output: 1
Explanation: Jump directly to an equal value.

Constraints

• 1<=n<=5*10^4

Asked by