DDSA Solutions

2948. Make Lexicographically Smallest Array by Swapping Elements

MediumView on LeetCode
ArrayGreedySortingOrdered Set

Problem Overview

You may swap two values only when their absolute difference is at most limit.

Intuition

You may swap two values only when their absolute difference is at most limit. That relation is transitive along a chain of nearby values, so after sorting the numbers, consecutive gaps of size at most limit glue them into connected components. Inside one component every value can move to any index that belongs to that same component. The lexicographically smallest layout puts the sorted values of the component into the sorted indices of the component.

Algorithm

  1. 1Build an index array 0..n-1 and sort it by nums[i] ascending.
  2. 2Scan the sorted indices. Split into groups wherever nums[idx[i]] - nums[idx[i-1]] > limit.
  3. 3For each group, copy its indices, sort those indices, and write the already-sorted group values into those positions.
  4. 4Return the filled answer array.

Example Walkthrough

Input: nums = [1, 5, 3, 9, 8], limit = 2

  1. 1.Sorted values: 1, 3, 5, 8, 9. Gaps: 2, 2, 3, 1.
  2. 2.Groups: {1}, {3,5}, {8,9} because 5 to 8 differs by 3 > 2.
  3. 3.Place sorted values into sorted indices of each group: [1,3,5,8,9].

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

Common Pitfalls

  • •Compare consecutive values after sorting by value, not by original index order.
  • •A gap larger than limit starts a new group even if both ends could swap with some middle value that is not present.
  • •Values inside a group are already sorted from the global sort; only the destination indices need a second sort.
  • •Do not try pairwise swaps in place. The component view is what guarantees the global lex minimum.
2948.cs
C#
// Approach: Sort indices by value. Consecutive values with gap <= limit form a
// component that can be freely rearranged. For each component, sort its indices
// and write the already-sorted values into those positions (lex-smallest).
// Complexity: O(n log n) time and O(n) extra space.
public class Solution
{
    public int[] LexicographicallySmallestArray(int[] nums, int limit)
    {
        int n = nums.Length;
        int[] idx = new int[n];
        for (int i = 0; i < n; i++)
            idx[i] = i;

        Array.Sort(idx, (a, b) => nums[a].CompareTo(nums[b]));

        int[] ans = new int[n];
        int start = 0;

        for (int i = 1; i <= n; i++)
        {
            if (i < n && nums[idx[i]] - nums[idx[i - 1]] <= limit)
                continue;

            int len = i - start;
            int[] slots = new int[len];
            for (int j = 0; j < len; j++)
                slots[j] = idx[start + j];

            Array.Sort(slots);
            for (int j = 0; j < len; j++)
                ans[slots[j]] = nums[idx[start + j]];

            start = i;
        }

        return ans;
    }
}
Was this solution helpful?

Related Problems