Jump Game IV

Problem

Given arr, return the minimum number of jumps to reach the last index, where from index i you may move to i - 1, i + 1, or any index j with arr[j] equal to arr[i].

Run BFS layer by layer, using a map from value to indices and deleting each value's list after it is expanded so no group is processed twice. The first layer that reaches the last index is the answer.

Hint

After expanding a value group, deleting it keeps the total work linear.

Test cases

case 1

in: [[100,-23,-23,404,100,23,23,23,3,404]]

expected: 3

case 2

in: [[7]]

expected: 0

case 3

in: [[7,6,9,6,9,6,9,7]]

expected: 1

case 4

in: [[6,1,9]]

expected: 2

case 5

in: [[11,22,7,7,7,7,7,7,7,22,13]]

expected: 3

Starter codePython

def min_jumps_jump_game_iv(arr):
    # Your code here
    pass

5 test cases · run your code against them in the editor