HackerRank 'Minimum Swaps 2' Solution

Martin Kysel · July 26, 2020

Short Problem Definition:

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.

Minimum Swaps 2

Complexity:

time complexity is O(N)

space complexity is O(1)

Execution:

This solution runs in O(N) since it will visit every element at most 2 times. No need for complex cycle algorithms, stacks, etc.

The trick is to put every element in the place it belongs to and swap it with the element at that position. It is possible that the swapped element wont be the correct once, hence the while loop.

Solution:
def minimumSwaps(arr):
    swaps = 0
    n = len(arr)

    for idx in xrange(n):
        while arr[idx]-1 != idx:
            ele = arr[idx]
            arr[ele-1], arr[idx] = arr[idx], arr[ele-1]
            swaps += 1
    return swaps

Twitter, Facebook

To learn more about solving Coding Challenges in Python, I recommend these courses: Educative.io Python Algorithms, Educative.io Python Coding Interview.