notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

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 ```