#! python3

"""
#    leetcode 1345. Jump Game IV.
#
#    Given an array of integers arr, you are initially 
#    positioned at the first index of the array.
#    In one step you can jump from index i to index:
#        i + 1 where: i + 1 < arr.length.
#        i - 1 where: i - 1 >= 0.
#        j where: arr[i] == arr[j] and i != j.
#    Return the minimum number of steps to reach 
#    the last index of the array.
#
#    Notice that you can not jump outside of the array at any time.
#
#    Example 1:
#    Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
#    Output: 3
#    Explanation: You need three jumps: 0 --> 4 --> 3 --> 9. 
#                 Note that index 9 is the last index of the array.
#
#    Example 2:
#    Input: arr = [7]
#    Output: 0
#    Explanation: Start index is the last index. 
#                 You don't need to jump.
#
#    Example 3:
#    Input: arr = [7,6,9,6,9,6,9,7]
#    Output: 1
#    Explanation: You can jump directly from index 0 to 
#                 index 7 which is last index of the array.
#
#    Example 4:
#    Input: arr = [6,1,9]
#    Output: 2
#
#    Example 5:
#    Input: arr = [11,22,7,7,7,7,7,7,7,22,13]
#    Output: 3
#
#    Constraints:
#        1 <= arr.length <= 5 * 10^4
#        -10^8 <= arr[i] <= 10^8
"""

# --------------------------------------------------------------
# Idea of the solution: use BFS (Breadth First Search) 
# starting from 0 until the last position is found.
# Track all the values and positions we have explored. 
# Complexity : O(N) for time and space
# --------------------------------------------------------------

def minJumps(arr):
    # -------------------------
    # dictionary giving list of positions for each value
    mydict = {}
    for i in range(len(arr)):
        val = arr[i]
        if val not in mydict:
            mydict[val] = [i]
        else:
            mydict[val] += [i]
    # -------------------------
    N       = len(arr)
    visited = set([-1,N]) # set of visited indexes to avoid
    queue   = {0}         # set of indexes to visit
    Nsteps   = 0          # number of steps done
    while True:
        visited |= queue
        if N-1 in visited:
            return Nsteps
        Nsteps += 1
        nex_pos = set()
        for pos in queue:
            nex_pos |= set([pos-1,pos+1] + mydict.pop(arr[pos], []))
        queue = nex_pos - visited  


def minJumps2(arr):
    """  https://leetcode.com/problems/jump-game-iv/discuss/503171/9-lines-Python-BFS """
    import collections, itertools
    indices = collections.defaultdict(list)
    for i, a in enumerate(arr):
        indices[a].append(i)
    done, now = {-1}, {0}
    for Nsteps in itertools.count():
        done |= now
        if len(arr) - 1 in done:
            return Nsteps
        now = {j for i in now for j in [i-1, i+1] + indices.pop(arr[i], [])} - done

# --------------------------------------------------------------
if __name__ == "__main__":
    test_cases = [
        ([100,-23,-23,404,100,23,23,23,3,404],3),
        ([7], 0), 
        ([7,6,9,6,9,6,9,7], 1), 
        ([6,1,9], 2), 
        ([11,22,7,7,7,7,7,7,7,22,13], 3), 
    ]

for arr, nn in test_cases:
    res = minJumps2(arr)
    print(res,nn,arr)
