Jump Game IV
Real-world version: Fewest Hops Along the Locker RowThe statement here is our own: the same inputs, outputs and technique.
A row of lockers is numbered from 0 to label.length - 1, and label[i] is the code stencilled on locker i. Two lockers may carry the same code.
A porter starts at locker 0 and wants to reach the last locker. Standing at locker i, one move takes the porter to any single one of these:
- locker
i + 1, if that locker exists; - locker
i - 1, if that locker exists; - any locker
jwithj != iandlabel[j] == label[i], however far away it is.
Return the fewest moves needed to reach the last locker. If the porter already starts there, the answer is 0.
Examples
Example 1
- Input
- label = [4, 9, 9, 9, 4, 8]
- Output
- 2
One route is locker 0 to locker 4, allowed because both are stencilled 4, and then locker 4 to locker 5. That is two moves.
Example 2
- Input
- label = [11, 12, 13, 14, 15]
- Output
- 4
No two lockers share a code, so the porter walks 0 to 1 to 2 to 3 to 4, which is four moves.
Example 3
- Input
- label = [5]
- Output
- 0
Locker 0 is already the last locker, so no move is needed.
Constraints
- 1 <= label.length <= 5 * 10^4
- -10^8 <= label[i] <= 10^8
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def fewest_hops(label: list[int]) -> int:public int fewestHops(int[] label)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's