2948. Make Lexicographically Smallest Array by Swapping Elements
Approach
Sort with original indices; group by proximity (diff ≤ limit); assign sorted values to slots.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
// Approach: Sort with original indices; group by proximity (diff ≤ limit); assign sorted values to slots.
// Time: O(n log n) Space: O(n)
public class Solution
{
public int[] LexicographicallySmallestArray(int[] nums, int limit)
{
int[] ans = new int[nums.Length];
List<List<KeyValuePair<int, int>>> numAndIndexesGroups = new List<List<KeyValuePair<int, int>>>();
foreach (var numAndIndex in GetNumAndIndexes(nums))
{
if (numAndIndexesGroups.Count == 0 ||
numAndIndex.Key - numAndIndexesGroups.Last().Last().Key > limit)
// Start a new group.
numAndIndexesGroups.Add(new List<KeyValuePair<int, int>> { numAndIndex });
else
// Append to the existing group.
numAndIndexesGroups.Last().Add(numAndIndex);
}
foreach (var numAndIndexesGroup in numAndIndexesGroups)
{
List<int> sortedNums = new List<int>();
List<int> sortedIndices = new List<int>();
foreach (var pair in numAndIndexesGroup)
{
sortedNums.Add(pair.Key);
sortedIndices.Add(pair.Value);
}
sortedIndices.Sort();
for (int i = 0; i < sortedNums.Count; ++i)
ans[sortedIndices[i]] = sortedNums[i];
}
return ans;
}
private KeyValuePair<int, int>[] GetNumAndIndexes(int[] nums)
{
KeyValuePair<int, int>[] numAndIndexes = new KeyValuePair<int, int>[nums.Length];
for (int i = 0; i < nums.Length; ++i)
numAndIndexes[i] = new KeyValuePair<int, int>(nums[i], i);
Array.Sort(numAndIndexes, (a, b) => a.Key.CompareTo(b.Key));
return numAndIndexes;
}
}