Min swaps for sorting list of consecutive integers

The problem:

You are given an unordered array consisting of consecutive integers [1, 2, 3, ..., n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.

My solution/issue:

My code does what it is supposed to; however, for large arrays it takes longer to run than allowed.

def minimumSwaps(arr):
    swaps = 0
    for num in range(1, len(arr)):
        if num != arr.index(num)+1: 
            arr[arr.index(num)] = arr[num-1]
            arr[num-1] = num
            swaps+=1
    return swaps

Any ideas/advice on how could I optimize this?

Answer

Since the list.index method costs O(n) in time complexity, calling it in a loop over the length of the list would result in O(n ^ 2) time complexity.

You can instead map the numbers in the list to their respective indices as a dict, so that the lookup of a number’s index would cost O(1) on average, resulting in an overall time complexity of O(n) instead. Update the indices accordingly whenever a swap is performed:

def minimumSwaps(arr):
    index = {v: i for i, v in enumerate(arr)}
    swaps = 0
    for num in range(1, len(arr)):
        if num != index[num] + 1:
            arr[index[num]] = arr[num - 1]
            index[arr[num - 1]] = index[num]
            arr[num - 1] = num
            index[num] = arr[num - 1]
            swaps += 1
    return swaps