Jump Game IV
Hard · Stack & Strings · Array · Hash Table · Breadth-First Search
Problem
You start at the first index of an integer array arr. In one step you may move from index i to:
- i + 1, if it is inside the array;
- i - 1, if it is inside the array;
- any index j != i with arr[j] == arr[i].
Return the fewest steps needed to reach the last index.
Examples
Input: arr = [5,2,8,5,9,3] Output: 3
0 → 3 by the equal value 5, then 3 → 4 → 5.
Input: arr = [4,1,1,1,4] Output: 1
Index 0 and the last index both hold 4.
Input: arr = [6] Output: 0
You already stand on the last index.
Constraints
- 1 <= len(arr) <= 5 · 10^4
- -10^8 <= arr[i] <= 10^8
Approaches
- BFS that rescans equal values — time O(n²), space O(n)
Follow-up
What if you also wanted the fewest steps to every index, not just the last one? Run the same search to completion and return the whole distance array; see the first use case.
Related problems
Start free on Cariara · Coding problems · System design studio
