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

JAVA

• class Solution {
      public int[] lexicographicallySmallestArray(int[] nums, int limit) {
          int n = nums.length;
          Integer[] idx = new Integer[n];
          for (int i = 0; i < n; ++i) {
              idx[i] = i;
          }
          Arrays.sort(idx, (i, j) -> nums[i] - nums[j]);
          int[] ans = new int[n];
          for (int i = 0; i < n;) {
              int j = i + 1;
              while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {
                  ++j;
              }
              Integer[] t = Arrays.copyOfRange(idx, i, j);
              Arrays.sort(t, (x, y) -> x - y);
              for (int k = i; k < j; ++k) {
                  ans[t[k - i]] = nums[idx[k]];
              }
              i = j;
          }
          return ans;
      }
  }

C++

• class Solution {
  public:
      vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
          int n = nums.size();
          vector<int> idx(n);
          iota(idx.begin(), idx.end(), 0);
          sort(idx.begin(), idx.end(), [&](int i, int j) {
              return nums[i] < nums[j];
          });
          vector<int> ans(n);
          for (int i = 0; i < n;) {
              int j = i + 1;
              while (j < n && nums[idx[j]] - nums[idx[j - 1]] <= limit) {
                  ++j;
              }
              vector<int> t(idx.begin() + i, idx.begin() + j);
              sort(t.begin(), t.end());
              for (int k = i; k < j; ++k) {
                  ans[t[k - i]] = nums[idx[k]];
              }
              i = j;
          }
          return ans;
      }
  };

PYTHON

• class Solution:
      def lexicographicallySmallestArray(self, nums, limit):
          n = len(nums)
          idx = list(range(n))
          idx.sort(key=lambda i: nums[i])  # Sort indices by the values in `nums`
          ans = [0] * n
          i = 0
          
          while i < n:
              j = i + 1
              # Find a contiguous block where the difference is within the limit
              while j < n and nums[idx[j]] - nums[idx[j - 1]] <= limit:
                  j += 1
              
              t = sorted(idx[i:j])  # Sort the indices in the current block
              for k in range(i, j):
                  ans[t[k - i]] = nums[idx[k]]
              
              i = j  # Move to the next block
          
          return ans