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:
- What is the most optimal solution when all the elements are distinct?
- 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.
