LeetCode/cpp/make-lexicographically-smallest-array-by-swapping-elements.cpp

#include <algorithm>
#include <list>
#include <unordered_map>
#include <vector>

class Solution {
  public:
    auto lexicographicallySmallestArray(std::vector<int> nums, int limit)
        -> std::vector<int> {
        // sort the numbers
        auto sorted_nums = nums;
        std::sort(sorted_nums.begin(), sorted_nums.end());

        // assign groups
        std::unordered_map<int, int> num_to_group;
        std::unordered_map<int, std::list<int>> groups;

        auto group = 0;
        for (auto i = 0u; i < sorted_nums.size(); ++i) {
            if (i > 0 && sorted_nums[i] - sorted_nums[i - 1] > limit) {
                ++group;
            }

            num_to_group[sorted_nums[i]] = group;
            groups[group].push_back(sorted_nums[i]);
        }

        // emplace into original ‹nums›
        for (auto &x : nums) {
            group = num_to_group[x];
            x = *groups[group].begin();
            groups[group].pop_front();
        }

        return nums;
    }
};