2948: Make-Lexicographically-Smallest-Array-by-Swapping-Elements
Medium

table of contents

My solution is based around a trick that I found while playing with their example test cases; given x_1, x_2, ..., x_n where x_1 < x_2 < ... < x_n and |x_i - x_j| <= limit for all i, j in {0, ..., n} (basically, given n elements ordered from smallest to largest, where the difference between each element is smaller than or equal to limit), we can rearrange all n elements amongst themselves.

You can easily prove this using induction. I will just provide a simple example:

Knowing this, we can sort nums from smallest to largest and keep track of their original indices. Then, we will find all the groups of integers, such that for each group, all the integers can be rearranged amongst themselves to form the lexicographically smallest array, by iterating through nums and checking if nums[i] + limit >= nums[i+1]:

Then, using the original indices of the elements inside the group, we can rearrange the elements to lexicographically form the smallest array for the group. Since each group can only be rearranged amongst themselves, it implies that the resulting array will lexicographically be the smallest array possible.

code

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        vector<pair<int, int>> pnums;
        for (int i = 0; i < nums.size(); ++i) {
            pnums.push_back({nums[i], i});
        }
        sort(pnums.begin(), pnums.end());

        vector<int> ans (nums.size());
        vector<pair<int, int>> temp_pnums;
        for (int i = 0; i < pnums.size(); ++i) {
            if (temp_pnums.size() > 0) {
                int n = temp_pnums.size();
                if (pnums[i].first-temp_pnums[n-1].first > limit) {
                    vector<pair<int, int>> temp_index = temp_pnums;
                    sort(temp_index.begin(), temp_index.end(), [&](auto &a, auto&b){return a.second < b.second;});

                    for (int j = 0; j < n; ++j) {
                        ans[temp_index[j].second] = temp_pnums[j].first;
                    }
                    temp_pnums.clear();
                }
            }
            temp_pnums.push_back(pnums[i]);
        }
        if (temp_pnums.size() > 0) {
            int n = temp_pnums.size();
            vector<pair<int, int>> temp_index = temp_pnums;
            sort(temp_index.begin(), temp_index.end(), [&](auto &a, auto&b){return a.second < b.second;});

            for (int j = 0; j < n; ++j) {
                ans[temp_index[j].second] = temp_pnums[j].first;
            }
        }
        return ans;
    }
};

complexity