algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit ec8f601a9c5faf985c399e1898cf95650edb6287
parent 67e537bfb90287c4e9bc2451ab1d110aefb147f8
Author: Andrew Laack <andrew@laack.co>
Date:   Mon, 19 Oct 2026 11:24:35 -0500

Min swaps + easy problem

Diffstat:
Aleetcode/find-target-indices-after-sorting-array/find-target-indices-after-sorting-array.cpp | 12++++++++++++
Aleetcode/minimum-swaps-to-sort-by-digit-sum/minimum-swaps-to-sort-by-digit-sum.cpp | 59+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 71 insertions(+), 0 deletions(-)

diff --git a/leetcode/find-target-indices-after-sorting-array/find-target-indices-after-sorting-array.cpp b/leetcode/find-target-indices-after-sorting-array/find-target-indices-after-sorting-array.cpp @@ -0,0 +1,12 @@ +class Solution { +public: + vector<int> targetIndices(vector<int>& nums, int target) { + std::sort(nums.begin(), nums.end()); + std::vector<int> res {}; + for(int i = 0; i < nums.size(); ++i) { + if(target == nums[i]) + res.push_back(i); + } + return res; + } +}; diff --git a/leetcode/minimum-swaps-to-sort-by-digit-sum/minimum-swaps-to-sort-by-digit-sum.cpp b/leetcode/minimum-swaps-to-sort-by-digit-sum/minimum-swaps-to-sort-by-digit-sum.cpp @@ -0,0 +1,59 @@ +int sumDigits(int input) { + int res = 0; + + while(input > 0) { + res += (input % 10); + input /= 10; + } + return res; +} + +std::string encodePair(std::pair<int,int> pr) { + return std::to_string(pr.first) + ":" + std::to_string(pr.second); +} + +class Solution { +public: + int minSwaps(vector<int>& nums) { + + std::vector<std::pair<int,int>> pairs {}; + std::vector<std::pair<int,int>> sortedPairs {}; + + + for(int i = 0; i < nums.size(); ++i) { + pairs.push_back({sumDigits(nums[i]), nums[i]}); + sortedPairs.push_back({sumDigits(nums[i]), nums[i]}); + } + + std::sort(sortedPairs.begin(), sortedPairs.end()); + + std::unordered_map<std::string,int> h {}; + + for(int i = 0; i < pairs.size(); ++i) { + h[encodePair(pairs[i])] = i; + } + + int swapCount = 0; + for(int i = 0; i < pairs.size(); ++i) { + + if(pairs[i] != sortedPairs[i]) { + std::string encodedBase = encodePair(pairs[i]); + std::string encodedTarget = encodePair(sortedPairs[i]); + + int swapIndex = h[encodedTarget]; + + auto temp = pairs[i]; + pairs[i] = pairs[swapIndex]; + pairs[swapIndex] = temp; + + h[encodedTarget] = i; + h[encodedBase] = swapIndex; + + swapCount += 1; + } + } + + + return swapCount; + } +};