### GRAYRHINO's blog

By GRAYRHINO, history, 16 months ago,

Given an array of integers (duplicates are possible), find the minimum number of swaps to sort the array. For [3,9,2,4,2] it should be 2 : [3, 9, 2, 4, 2] -> [2, 9, 3, 4, 2] -> [2, 2, 3, 4, 9]

If the elements are distinct then there's a time complexity O(nlog(n)) and space complexity O(n) solution here. However, I couldn't find any satisfactory proof for solutions where array contains duplicates. So, I have two questions:

1. What is the most optimal solution when all the elements are distinct?
2. Any algorithm when the array contains duplicates?

This seems to be very common questions in top tech interviews. Your ideas and suggestions (possibly code) would be much appreciated.

• +91

 » 16 months ago, # |   -16 It's with the same basic principle, let's take the i-th element in the array, we have to swap it (at some point) with the j-th element if, j < i and the i-th element is smaller, or j > i and the j-th element is smaller. this many swaps is necessary as there are at least this many inversions, and we can also see that it is sufficient, so we need to calculate this amount. doing so can be easily done using segment trees, in O(n.log(n)) time and O(n) memory.
•  » » 16 months ago, # ^ |   +31 You are counting no of inversions and claiming that answer is no of inversions. It is wrong.He never said you can swap only adjacent elements. In fact answer of this problem is always less than n. While no of inversions can be O(n^2).
•  » » » 16 months ago, # ^ |   0 Thanks for highlighting that. Before posting the question here, I have seen various solutions but almost all of them make some assumptions such as elements are distinct, only adjacent swaps are allowed, etc. While all those assumptions are valid and there's something to learn from them, the reason I posted here is to get feedback for the worst case that is when duplicates are allowed and you can swap any two elements. Hope we can get some satisfactory explanation.
•  » » » » 16 months ago, # ^ |   +13 The problem seems interesting but IDK how to solve it. Lebossle wrote about this problem -"you can model it as a graph where nodes are groups of equal elements and edges say where they want to go, which ends up being a circulation (degree in = degree out). The problem is thus decomposition into maximum amount of cycles. Dual is minimum amount of edges to cut to make it a DAG. Not sure how to move from here, I'll think if simplex translates into something fast, like a flow, or maybe it's matroid intersection which I still need to learn"
•  » » » » » 16 months ago, # ^ |   +10 Minimum number of edges to cut to make a Graph a DAG is known as the Feedback Arc Set Problem. This is known to be NP-Complete.
 » 16 months ago, # | ← Rev. 2 →   +16 Cycle Sort — Read the second point please. UPD: It is wrong
•  » » 16 months ago, # ^ | ← Rev. 5 →   0 It's wrong. It goes the correct answer only for a stable sort. Basically, it assumes if i
•  » » 16 months ago, # ^ |   0 Your suggested solution gives 4 for [3,9,2,4,2] and 3 for [5, 1, 3, 2] while for both of them the answer is 2. Am I missing something?
 » 16 months ago, # |   +19 Hello, can you give a link to the task?
•  » » 16 months ago, # ^ |   0 Unfortunately, I do not have any links. I read about it from someone's interview experience at Google. The question is intentionally vague and obviously you can make assumptions and solve it for special cases as discussed above. To test your limits the interviewer will make it difficult after each correct solution.
 » 16 months ago, # |   0 Pls, provide a link to the problem.
 » 16 months ago, # |   -16 If you really need ANY solution for duplicates: just make an array of indexes (basically it is 0, 1, .. n-1). Then you can swap adjacent indexes of this array in original one and check if the original array is sorted after it or not. After that you take next permutation of your array of indexes. This solution works for N!. If you have any doubts you can ask me.