MinimumSwapsToSort.md (3759B)
1 # Minimum Swaps To Sort 2 3 ## Intuition 4 5 We have an unsorted array. We want to first create a sorted array copy of this array. We'll use this as the final destination, computing the number of swaps to make them equivalent. 6 7 To compute the swap number, we first want a way to index into our unsorted array by value. Thusly, we want a hashmap where the keys are the array's values, and the values are the indices. 8 9 Once we have our hashmap for lookups, we then iterate over each index of our array. If the value in our unsorted array doesn't match the sorted array, we know a swap must be done. Specifically, we want to swap the current element in the array element that matches the one in the sorted array at that index. To find this we simple check our hashmap for the index that contains sorted[i]. We then perform a swap of these two elements in both our array, and in our hashmap so they stay synchronized. We also increment the swap count by one as we have performed a swap. We do this for each element of arr. 10 11 Once done, arr will match sorted, and we will have the minimum swap count to sort as well. The time complexity of this algorithm is O(n log n), dominated by the initial sort. Each swap takes constant time, and we only perform at most n swaps. 12 13 ## Definition 14 15 Input: int[] arr 16 Output: int swapCount 17 18 1. Create sorted copy of arr 19 2. Create hashmap addressed by array value, storing index in arr 20 - For each element in arr, h[arr[i]] = i 21 3. swapCount = 0 22 4. For each index in arr 23 - if sorted[i] != arr[i] 24 - index = h[sorted[i]] 25 - swap(arr[i], arr[index]) 26 - h[arr[i]] = i 27 - h[arr[ind]] = ind 28 - swapCount++ 29 5. Return swapCount 30 31 ## Implementation in C++ 32 33 ### Leetcode Problem 34 35 Leetcode #3551, Minimum Swaps to Sort by Digit Sum 36 37 Given an array nums of distinct positive integers. Sort the array in increasing order based on the sum of the digits of each number. If two numbers have the same digit sum, the smaller number appears first in the sorted order. 38 39 Return the minimum number of swaps required to rearrange nums into this sorted order. 40 41 A swap is defined as exchanging the values at two distinct positions in the array. 42 43 ### Solution 44 45 NOTE: There are implementation improvements to aid in runtime, but asymptotically it's optimal. 46 47 ```c++ 48 int sumDigits(int input) { 49 int res = 0; 50 51 while(input > 0) { 52 res += (input % 10); 53 input /= 10; 54 } 55 return res; 56 } 57 58 std::string encodePair(std::pair<int,int> pr) { 59 return std::to_string(pr.first) + ":" + std::to_string(pr.second); 60 } 61 62 class Solution { 63 public: 64 int minSwaps(vector<int>& nums) { 65 66 std::vector<std::pair<int,int>> pairs {}; 67 std::vector<std::pair<int,int>> sortedPairs {}; 68 69 70 for(int i = 0; i < nums.size(); ++i) { 71 pairs.push_back({sumDigits(nums[i]), nums[i]}); 72 sortedPairs.push_back({sumDigits(nums[i]), nums[i]}); 73 } 74 75 std::sort(sortedPairs.begin(), sortedPairs.end()); 76 77 std::unordered_map<std::string,int> h {}; 78 79 for(int i = 0; i < pairs.size(); ++i) { 80 h[encodePair(pairs[i])] = i; 81 } 82 83 int swapCount = 0; 84 for(int i = 0; i < pairs.size(); ++i) { 85 86 if(pairs[i] != sortedPairs[i]) { 87 std::string encodedBase = encodePair(pairs[i]); 88 std::string encodedTarget = encodePair(sortedPairs[i]); 89 90 int swapIndex = h[encodedTarget]; 91 92 auto temp = pairs[i]; 93 pairs[i] = pairs[swapIndex]; 94 pairs[swapIndex] = temp; 95 96 h[encodedTarget] = i; 97 h[encodedBase] = swapIndex; 98 99 swapCount += 1; 100 } 101 } 102 103 104 return swapCount; 105 } 106 }; 107 ```