Make Lexicographically Smallest Array by Swapping Elements

medium array connected components union-find sorting

Problem

You are given a 0-indexed array of positive integers nums and a positive integer limit. You may swap nums[i] and nums[j] any number of times whenever |nums[i] − nums[j]| ≤ limit. Return the lexicographically smallest array reachable.

Swappability is transitive, so the values split into connected components. Within one component the values can be placed in any order across that component's positions. To be smallest, give each component's earliest positions its smallest values.

Inputnums = [1,5,3,9,8], limit = 2

Output[1,3,5,8,9]

Components by value: {1}, {3,5} (positions 1,2), {8,9} (positions 3,4). Sort each component into its own positions.

nums (comma-separated)

limit

def lexicographicallySmallestArray(nums, limit):
    n = len(nums)
    # indices sorted by their value
    order = sorted(range(n), key=lambda i: nums[i])
    ans = [0] * n
    i = 0
    while i < n:
        # grow one connected component of consecutive sorted values
        j = i + 1
        while j < n and nums[order[j]] - nums[order[j - 1]] <= limit:
            j += 1
        group = order[i:j]                  # original indices in this component
        pos = sorted(group)                 # positions, left to right
        vals = sorted(nums[k] for k in group)
        for p, v in zip(pos, vals):         # smallest value to earliest position
            ans[p] = v
        i = j
    return ans

function lexicographicallySmallestArray(nums, limit) {
  const n = nums.length;
  // indices sorted by their value
  const order = [...nums.keys()].sort((a, b) => nums[a] - nums[b]);
  const ans = new Array(n).fill(0);
  let i = 0;
  while (i < n) {
    // grow one connected component of consecutive sorted values
    let j = i + 1;
    while (j < n && nums[order[j]] - nums[order[j - 1]] <= limit) j++;
    const group = order.slice(i, j);          // original indices
    const pos = [...group].sort((a, b) => a - b);
    const vals = group.map(k => nums[k]).sort((a, b) => a - b);
    for (let t = 0; t < pos.length; t++) ans[pos[t]] = vals[t];
    i = j;
  }
  return ans;
}

int[] lexicographicallySmallestArray(int[] nums, int limit) {
    int n = nums.length;
    Integer[] order = new Integer[n];
    for (int k = 0; k < n; k++) order[k] = k;
    Arrays.sort(order, (a, b) -> nums[a] - nums[b]);   // indices by value
    int[] ans = new int[n];
    int i = 0;
    while (i < n) {
        int j = i + 1;                                 // grow a component
        while (j < n && nums[order[j]] - nums[order[j - 1]] <= limit) j++;
        int len = j - i;
        int[] pos = new int[len], vals = new int[len];
        for (int t = 0; t < len; t++) { pos[t] = order[i + t]; vals[t] = nums[order[i + t]]; }
        Arrays.sort(pos);                              // positions ascending
        Arrays.sort(vals);                             // values ascending
        for (int t = 0; t < len; t++) ans[pos[t]] = vals[t];
        i = j;
    }
    return ans;
}

vector<int> lexicographicallySmallestArray(vector<int>& nums, int limit) {
    int n = nums.size();
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int a, int b){ return nums[a] < nums[b]; });
    vector<int> ans(n);
    int i = 0;
    while (i < n) {
        int j = i + 1;                                 // grow a component
        while (j < n && nums[order[j]] - nums[order[j - 1]] <= limit) j++;
        vector<int> pos(order.begin() + i, order.begin() + j);
        vector<int> vals;
        for (int k : pos) vals.push_back(nums[k]);
        sort(pos.begin(), pos.end());                  // positions ascending
        sort(vals.begin(), vals.end());                // values ascending
        for (int t = 0; t < (int)pos.size(); t++) ans[pos[t]] = vals[t];
        i = j;
    }
    return ans;
}

Explanation

Two values can be swapped when they differ by at most limit. Because swaps can be chained, "reachable from each other" is an equivalence relation, and the values fall into connected components — exactly the union-find / graph-component idea, but we never build the graph explicitly.

The key observation: sort the values. Two adjacent values in sorted order are connected iff their difference is ≤ limit. So a connected component is simply a maximal run of consecutive sorted values where each neighbour gap stays within limit. We sort indices by value so we keep track of where each value originally lived.

Within one component, every value can travel to every position the component occupies. The set of positions is fixed (the original indices of those values); only their ordering is free. To make the whole array lexicographically smallest, we place the component's smallest value at its earliest position, the next-smallest at the next position, and so on — i.e. sort positions ascending, sort values ascending, and pair them up.

Doing this independently for every component yields the global lexicographically smallest array, because earlier positions are always filled with the smallest available value reachable there.

Example nums = [1,5,3,9,8], limit = 2: sorted values are 1, 3, 5, 8, 9. Gaps 3−1=2, 5−3=2 are ≤2; 8−5=3 breaks the run; 9−8=1 is fine. Components are {1}, {3,5} at positions {1,2}, and {8,9} at positions {3,4}, giving [1,3,5,8,9].

Time: O(n log n) Space: O(n)