Minimum Number of Swaps to Sort an Array of consecutive integers

Well, the title speaks for itself!

Try it yourself on HackerRank

Apparently this is quite a common interview question (asked at Google Phone Screen). Sadly, I couldn’t find some good visualizations to understand the underlying logic behind the solving this problem. So, I couldn’t help but write one for myself.

In this post we explore the minimum swaps required to sort, and array/list of consecutive integers, note that the case of non-consecutive integers will be slightly different.

The Constraints

We are given a list (since I use Python, sticking to “list” 😐) a N integers such that

• 1 ≤ N ≤ 10⁵
• 1 ≤ arr[i] ≤ N

The Data Structure

The intuitive idea is to think of the elements in the list as nodes and their corresponding position as edges of a graph. Let’s consider a very simple example:

arr = [4, 2, 3, 1]

Now the correct order looks like this: [1,2,3,4]

It is obvious here that 1 and 4 will swap. Now, let’s consider it as a graph:

• We have the nodes: (1), (2), (3), (4)
• Consider the positions of each of them in arr as a hashMap: