2191. Sort the Jumbled Numbers
Approach
Map each number through digit mapping; stable sort by mapped value.
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.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
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: Map each number through digit mapping; stable sort by mapped value.
// Time: O(n log n) Space: O(n)
public class Solution
{
public int[] SortJumbled(int[] mapping, int[] nums)
{
int n = nums.Length;
int[] ans = new int[n];
List<int[]> pair = new List<int[]>();
for (int i = 0; i < n; i++)
pair.Add(new int[] { GetMapped(nums[i], mapping), i, nums[i] });
pair.Sort((a, b) => a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
return pair.Select(x => x[2]).ToArray();
}
private int GetMapped(int val, int[] mapping)
{
var sb = new StringBuilder();
foreach (char c in val.ToString())
sb.Append(mapping[c - '0']);
return int.Parse(sb.ToString());
}
}