Make Lexicographically Smallest Array by Swapping Elements

Leetcode Problem:

• Make Lexicographically Smallest Array by Swapping Elements

Summary

• Given a 0-indexed array of positive integers and a positive integer limit, return the lexicographically smallest array that can be obtained by swapping any two indices if the absolute difference between the two elements is less than or equal to the limit.

Approach

• The solution uses a greedy approach to group the elements into subarrays based on their values
• It first sorts the array and then iterates through the sorted array to create subarrays
• Each subarray contains elements that are within the limit of each other
• Finally, it replaces each element in the original array with the smallest element in its corresponding subarray.

Complexity

• O(n log n) due to the sorting operation, where n is the number of elements in the array.

Solution Code:

class Solution {
public:
    vector lexicographicallySmallestArray(vector& nums, int limit) {
        vector> groups;
        unordered_map valToGrp;
        int numIdx = 0;
        vector nums2;
        for(int i = 0 ; i < nums.size(); i++){
            nums2.push_back(nums[i]);
        }
        sort(nums2.begin(), nums2.end());
        while(numIdx < nums2.size()){
            groups.push_back(vector ());
            long long minv = nums2[numIdx];
            long long maxv = nums2[numIdx];
            while(minv - limit <= nums2[numIdx] && nums2[numIdx] <= maxv + limit){
                groups.back().push_back(nums2[numIdx]);
                valToGrp[nums2[numIdx]] = groups.size() - 1;
                numIdx++;
                if(numIdx >= nums2.size()) break;
                if(minv > nums2[numIdx] && nums2[numIdx] >= minv - limit){
                    minv = nums2[numIdx];
                }
                if(maxv < nums2[numIdx] && nums2[numIdx] <= maxv + limit){
                    maxv = nums2[numIdx];
                }
            }
        }
        unordered_map groupIdx;
        for(int i = 0 ; i < nums.size(); i++){
            int idx = valToGrp[nums[i]];
            nums[i] = groups[idx][groupIdx[idx]];
            groupIdx[idx]++;
        }
        return nums;
    }
};