2948. Make Lexicographically Smallest Array by Swapping Elements

You are given a 0-indexed array of positive integers nums and a positive integer limit.

In one operation, you can choose any two indices i and j and swap nums[i] and nums[j] if |nums[i] - nums[j]| <= limit.

Return the lexicographically smallest array that can be obtained by performing the operation any number of times.

An array a is lexicographically smaller than an array b if in the first position where a and b differ, array a has an element that is less than the corresponding element in b. For example, the array [2,10,3] is lexicographically smaller than the array [10,2,3] because they differ at index 0 and 2 < 10.

Example 1:

Input: nums = [1,5,3,9,8], limit = 2
Output: [1,3,5,8,9]
Explanation: Apply the operation 2 times:
- Swap nums[1] with nums[2]. The array becomes [1,3,5,9,8]
- Swap nums[3] with nums[4]. The array becomes [1,3,5,8,9]
We cannot obtain a lexicographically smaller array by applying any more operations.
Note that it may be possible to get the same result by doing different operations.

Example 2:

Input: nums = [1,7,6,18,2,1], limit = 3
Output: [1,6,7,18,1,2]
Explanation: Apply the operation 3 times:
- Swap nums[1] with nums[2]. The array becomes [1,6,7,18,2,1]
- Swap nums[0] with nums[4]. The array becomes [2,6,7,18,1,1]
- Swap nums[0] with nums[5]. The array becomes [1,6,7,18,1,2]
We cannot obtain a lexicographically smaller array by applying any more operations.

Example 3:

Input: nums = [1,7,28,19,10], limit = 3
Output: [1,7,28,19,10]
Explanation: [1,7,28,19,10] is the lexicographically smallest array we can obtain because we cannot apply the operation on any two indices.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= limit <= 109

Approach 01:

#include <vector>
#include <algorithm>
#include <ranges>

class Solution {
public:
    vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
        vector<int> result(nums.size());
        // Group numbers based on the difference condition <= limit
        vector<vector<pair<int, int>>> groupedNumbers;

        // Sort numbers with their indices
        for (const pair<int, int>& numAndIndex : getNumAndIndexes(nums)) {
            // Start a new group if the difference between num and the last number exceeds the limit
            if (groupedNumbers.empty() ||
                numAndIndex.first - groupedNumbers.back().back().first > limit) {
                groupedNumbers.push_back({numAndIndex});
            } else {
                // Append to the existing group
                groupedNumbers.back().push_back(numAndIndex);
            }
        }

        // Process each group of numbers
        for (const vector<pair<int, int>>& numAndIndexesGroup : groupedNumbers) {
            vector<int> sortedNums;
            vector<int> sortedIndices;
            for (const auto& [num, index] : numAndIndexesGroup) {
                sortedNums.push_back(num);
                sortedIndices.push_back(index);
            }
            std::ranges::sort(sortedIndices); // Sort indices to maintain the lexicographical order
            for (int i = 0; i < sortedNums.size(); ++i)
                result[sortedIndices[i]] = sortedNums[i]; // Assign sorted values to result
        }

        return result;
    }

private:
    vector<pair<int, int>> getNumAndIndexes(const vector<int>& nums) {
        vector<pair<int, int>> numAndIndexes;
        for (int i = 0; i < nums.size(); ++i)
            numAndIndexes.emplace_back(nums[i], i);
        std::ranges::sort(numAndIndexes); // Sort pairs based on the numbers
        return numAndIndexes;
    }
};

class Solution:
    def lexicographicallySmallestArray(self, nums, limit):
        result = [0] * len(nums)
        # Group numbers based on the difference condition <= limit
        groupedNumbers = []

        # Sort numbers with their indices
        for num, index in self.getNumAndIndexes(nums):
            # Start a new group if the difference between num and the last number exceeds the limit
            if not groupedNumbers or num - groupedNumbers[-1][-1][0] > limit:
                groupedNumbers.append([(num, index)])
            else:
                # Append to the existing group
                groupedNumbers[-1].append((num, index))

        # Process each group of numbers
        for numAndIndexesGroup in groupedNumbers:
            sortedNums = []
            sortedIndices = []
            for num, index in numAndIndexesGroup:
                sortedNums.append(num)
                sortedIndices.append(index)
            sortedIndices.sort()  # Sort indices to maintain the lexicographical order
            for i in range(len(sortedNums)):
                result[sortedIndices[i]] = sortedNums[i]  # Assign sorted values to result

        return result

    def getNumAndIndexes(self, nums):
        numAndIndexes = [(num, index) for index, num in enumerate(nums)]
        numAndIndexes.sort()  # Sort pairs based on the numbers
        return numAndIndexes

Time Complexity:

• Sorting:

  Sorting the numbers based on their values and indices takes \( O(N \log N) \), where \( N \) is the size of the input array nums.

• Grouping:

  Grouping the numbers based on the difference condition takes \( O(N) \), since each element is processed once to check the grouping condition.

• Result Construction:

  Constructing the result array involves another \( O(N) \) operation, as each number is assigned its sorted value based on the grouped indices.

• Total Time Complexity:

  The overall time complexity is dominated by the sorting step, so the total time complexity is \( O(N \log N) \).

Space Complexity:

• Auxiliary Space:

  We need extra space for the groupedNumbers and numAndIndexes vectors. Each stores \( O(N) \) elements, so the auxiliary space complexity is \( O(N) \).

• Total Space Complexity:

  The total space complexity is \( O(N) \), which accounts for both the input and auxiliary space used during computation.