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: