391. Make Lexicographically Smallest Array by Swapping Elements

If we sort the values, any run of adjacent values whose consecutive gaps are all <= limit are mutually swappable (swaps chain transitively). Within each such group the positions can be reordered freely, so place the smallest values at the smallest positions.

Key insight

Two elements are directly swappable when their absolute difference is at most limit. Swaps are transitive: if a can swap with b and b with c, then by a sequence of swaps a, b, c can be arranged in any order among their three positions. So the array splits into groups of freely-permutable values, and within a group we may put any of the group's values at any of the group's positions.

To find the groups without an O(n^2) pairwise check, sort the values. After sorting, a group is exactly a maximal run of consecutive sorted values where every adjacent gap is <= limit (if adjacent sorted values are within limit, they connect; connectivity chains along the sorted order).

For the lexicographically smallest result, each group owns a fixed multiset of positions (the original indices of its members) and a fixed multiset of values. Assign the smallest value to the smallest position, next smallest value to next smallest position, and so on.

Walk-through — nums = [1,5,3,9,8], limit = 2

1. Sort indices by value: order = [0, 2, 1, 4, 3] with values [1, 3, 5, 8, 9].
2. Scan the sorted values and cut a new group whenever the gap exceeds limit:
   • 1 -> 3 (gap 2 <= 2), 3 -> 5 (gap 2 <= 2): group A = values {1,3,5} at positions {0,2,1}.
   • 5 -> 8 (gap 3 > 2): cut. group B starts.
   • 8 -> 9 (gap 1 <= 2): group B = values {8,9} at positions {4,3}.
3. Group A: sort its positions -> [0,1,2], sort its values -> [1,3,5]. Assign result[0]=1, result[1]=3, result[2]=5.
4. Group B: sort its positions -> [3,4], values -> [8,9]. Assign result[3]=8, result[4]=9.
5. Result: [1,3,5,8,9].

Complexity

• Time: O(n log n) — dominated by sorting the indices; the grouping scan and per-group position sort are O(n log n) overall.
• Space: O(n) — the sorted-index order and the output array.

class Solution {
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        int n = nums.length;

        // Indices sorted by their value.
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, (a, b) -> Integer.compare(nums[a], nums[b]));

        int[] result = new int[n];
        int i = 0;
        while (i < n) {
            // Extend the group while consecutive sorted values stay within limit.
            int j = i + 1;
            while (j < n && nums[order[j]] - nums[order[j - 1]] <= limit) j++;

            // Positions owned by this group, sorted ascending. The values
            // nums[order[i..j-1]] are already ascending, so pairing assigns the
            // smallest value to the smallest position.
            int size = j - i;
            Integer[] positions = new Integer[size];
            for (int k = 0; k < size; k++) positions[k] = order[i + k];
            Arrays.sort(positions);
            for (int k = 0; k < size; k++) {
                result[positions[k]] = nums[order[i + k]];
            }

            i = j;
        }

        return result;
    }
}