I'm prepping for a Google Technical Phone Screen. Saw the following question on Leetcode. Can't quite solve it. Anyone ever solved this one. https://leetcode.com/discuss/interview-question/346621/Google-or-Phone-screen-or-Least-amount-of-changes-to-order-an-array-in-ascending-order Cheers
The minimum number of swaps needed is the number of inversions in the array. Look up counting array inversions. Can be done in O(n log n) by either modifying merge sort routine or by using a Fenwick (binary indexed) tree.
@blendo counting inversion for all cases won't give you the minimum number of swaps though! e.g. an array like so {15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1} has so many inversions but you only need to swap like half the length of the array to sort it. So I'm guessing minimum swap here is like arr.length / 2
If all numbers are unique, then the answer is n - length of the Longest Increasing Subsequence (LIS). LIS can be solved in O(nlogn) time.
Wow. I got asked something super similar to that question for one of my google onsites a few months ago!
Reposting question contents in case LC deletes the topic : https://pastebin.com/prfrefiZ
Sort the array and map each value to its index in the sorted array. Traverse the unsorted array. If you hit a value that is not in its correct place, swap it for the value in the place where it should go. Repeat this until the current position you are at has the correct value as well. Continue. I believe this greedy approach should give you the optimal number of swaps, but I may be wrong. Time complexity is O(n lg n) due to the initial sort. Please correct me if Iām wrong about anything.
No need to swap while traversing, just check if they mismatch. The answer will be number of mismatches - 1?
prestige is right. SdeF66, wrong. You need to swap. Eg(2,1,4,3). Ans is 2, not 3.