Hashing, Sorting and PriorityQueue in C#

This part is about the containers, and about the parts of the C# standard library that contest write-ups tend to get wrong because they predate them.

Every program below is complete, was run on .NET 10, and its output is pasted from the run.

Pattern 26 — Counting things

Four ways, in increasing order of how much they cost.

using System.Runtime.InteropServices;

int[] a = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5];

// The version everyone writes. Two hash lookups per item.
Dictionary<int, int> plain = [];
foreach (int x in a) plain[x] = plain.GetValueOrDefault(x) + 1;

// One lookup. The ref points into the dictionary's own storage.
Dictionary<int, int> fast = [];
foreach (int x in a)
{
    ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(fast, x, out _);
    slot++;
}

// .NET 9 and later. Shortest to write, allocates an enumerable.
var counted = a.CountBy(x => x).OrderBy(kv => kv.Key);

Console.WriteLine($"plain   : {string.Join(" ", plain.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"ref     : {string.Join(" ", fast.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"CountBy : {string.Join(" ", counted.Select(kv => $"{kv.Key}x{kv.Value}"))}");
Console.WriteLine($"all agree: {plain.OrderBy(k => k.Key).SequenceEqual(fast.OrderBy(k => k.Key))}");

// When the keys are small and dense, skip hashing altogether.
int[] tally = new int[10];
foreach (int x in a) tally[x]++;
Console.WriteLine($"array   : [{string.Join(", ", tally)}]   <- no hashing at all");

It prints:

plain   : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
ref     : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
CountBy : 1x2 2x1 3x2 4x1 5x3 6x1 9x1
all agree: True
array   : [0, 2, 1, 2, 1, 3, 1, 0, 0, 1]   <- no hashing at all

dict[x] = dict.GetValueOrDefault(x) + 1 hashes the key twice — once to read, once to write. CollectionsMarshal.GetValueRefOrAddDefault hands back a ref straight into the dictionary’s storage, so the increment happens in place after a single lookup. On a tight loop over a million items that is a real difference, and it is three lines.

CountBy arrived in .NET 9. It is the shortest thing to write and allocates an enumerable, which is the right trade outside a hot loop.

And when the keys are small non-negative integers, a plain int[] beats all of them. No hashing, no collisions, contiguous memory. If the problem says values are between 1 and 10⁶, that array is 4MB and it is almost certainly the right answer.

Reach for it when — always, but pick the right one. Small dense keys mean an array. A hot loop means the ref. Anything else, write the readable one.

Pattern 27 — Grouping by a signature

Group words that are anagrams of each other.

The whole pattern is choosing a signature: something identical for everything in a group and different for everything outside it.

string[] words = ["eat", "tea", "tan", "ate", "nat", "bat"];

// The signature has to be identical for anagrams and different for anything
// else. Sorted letters is the obvious one.
static string SortedKey(string w)
{
    char[] c = w.ToCharArray();
    Array.Sort(c);
    return new string(c);
}

// For a fixed alphabet, a count vector is O(n) instead of O(n log n).
static string CountKey(string w)
{
    int[] n = new int[26];
    foreach (char c in w) n[c - 'a']++;
    return string.Join(",", n);
}

foreach (var g in words.GroupBy(SortedKey))
    Console.WriteLine($"key \"{g.Key}\"  ->  [{string.Join(", ", g)}]");

Console.WriteLine();
Console.WriteLine($"both keys agree on the grouping: " +
    $"{words.GroupBy(SortedKey).Count() == words.GroupBy(CountKey).Count()}");
Console.WriteLine($"SortedKey(\"eat\") = \"{SortedKey("eat")}\"");
Console.WriteLine($"CountKey(\"eat\")  = \"{CountKey("eat")}\"");

It prints:

key "aet"  ->  [eat, tea, ate]
key "ant"  ->  [tan, nat]
key "abt"  ->  [bat]

both keys agree on the grouping: True
SortedKey("eat") = "aet"
CountKey("eat")  = "1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0"

Sorted letters is the obvious signature and costs O(m log m) per word. For a fixed alphabet, a count of each letter is O(m) and works just as well — the output confirms both produce the same grouping.

The interesting cases are the ones where the obvious signature is subtly wrong. For “are these two trees the same shape”, the signature has to encode the nulls too, or different trees collide. Getting the signature exactly as strong as the equivalence you want is the whole job.

Reach for it when the problem says group, find duplicates, or how many distinct.

Pattern 28 — Comparers, and the sort that reorders equal items

Sort by score descending, then by name ascending.

(string Name, int Score)[] people =
[
    ("ada", 90), ("grace", 85), ("alan", 90), ("edsger", 85), ("barbara", 90)
];

// Score descending, then name ascending. One comparer, two keys.
var byScoreThenName = Comparer<(string Name, int Score)>.Create((x, y) =>
{
    int c = y.Score.CompareTo(x.Score);       // reversed operands = descending
    return c != 0 ? c : string.CompareOrdinal(x.Name, y.Name);
});

var arr = people.ToArray();
Array.Sort(arr, byScoreThenName);
foreach (var p in arr) Console.WriteLine($"  {p.Name,-8} {p.Score}");

// Array.Sort is NOT stable, and here is exactly where that starts to show.
Console.WriteLine($"\n{"n",4}  {"Array.Sort keeps input order?",32}");
foreach (int n in new[] { 8, 16, 17, 32 })
{
    var items = Enumerable.Range(0, n).Select(i => (Id: i, Key: i % 2)).ToArray();

    var viaSort = items.ToArray();
    Array.Sort(viaSort, (x, y) => x.Key.CompareTo(y.Key));

    var viaOrderBy = items.OrderBy(p => p.Key).ToArray();

    Console.WriteLine($"{n,4}  {viaSort.SequenceEqual(viaOrderBy),32}");
}

Console.WriteLine("\n.NET's introsort drops to insertion sort for 16 elements or fewer,");
Console.WriteLine("and insertion sort happens to be stable. At 17 it partitions, and does not.");

It prints:

  ada      90
  alan     90
  barbara  90
  edsger   85
  grace    85

   n     Array.Sort keeps input order?
   8                              True
  16                              True
  17                             False
  32                             False

.NET's introsort drops to insertion sort for 16 elements or fewer,
and insertion sort happens to be stable. At 17 it partitions, and does not.

The multi-key comparer is routine: compare on the first key, and only fall through to the second when the first ties. Descending means reversing the operands — y.CompareTo(x) — not negating the result, which breaks on int.MinValue.

The second half is the part that catches people.

Array.Sort is not stable. OrderBy is. And look at where it starts to matter: n = 16 agrees, n = 17 does not. .NET’s introsort drops to insertion sort for partitions of 16 or fewer, and insertion sort happens to preserve order. Above that it partitions, and equal elements move.

A stability bug tests clean on sixteen items and fails on seventeen. That is not a size anyone picks for a test case.

If order among equal items matters, either use OrderBy/ThenBy, or add a tie-breaker to the comparer so no two items ever compare equal. The second is what contest code does, because Array.Sort on a raw array is faster and allocates nothing.

Reach for it when sorting by anything other than the natural order. And any time equal elements need to keep their input order.

Pattern 29 — Coordinate compression

Values up to a million, but only a handful of distinct ones. You want an array indexed by value, and it would need a million cells.

The values are only ever being compared. So throw them away and keep their ranks.

int[] a = [1_000_000, 5, 300, 5, 99_999, 300];

// The values matter only by their ORDER, so replace each with its rank.
int[] sorted = a.Distinct().Order().ToArray();
Dictionary<int, int> rank = sorted
    .Select((v, i) => (v, i))
    .ToDictionary(t => t.v, t => t.i);

int[] compressed = a.Select(v => rank[v]).ToArray();

Console.WriteLine($"original   : [{string.Join(", ", a)}]");
Console.WriteLine($"distinct   : [{string.Join(", ", sorted)}]");
Console.WriteLine($"compressed : [{string.Join(", ", compressed)}]");
Console.WriteLine();
Console.WriteLine($"an array indexed by value would need {a.Max() + 1:N0} cells");
Console.WriteLine($"an array indexed by rank needs      {sorted.Length:N0}");
Console.WriteLine();

// Order is preserved, which is the only property that had to survive.
for (int i = 0; i < a.Length; i++)
    for (int j = 0; j < a.Length; j++)
        if (a[i].CompareTo(a[j]) != compressed[i].CompareTo(compressed[j]))
            throw new Exception("order not preserved");
Console.WriteLine("every pairwise comparison gives the same answer as before: True");

// And it is reversible.
Console.WriteLine($"decompressed: [{string.Join(", ", compressed.Select(r => sorted[r]))}]");

It prints:

original   : [1000000, 5, 300, 5, 99999, 300]
distinct   : [5, 300, 99999, 1000000]
compressed : [3, 0, 1, 0, 2, 1]

an array indexed by value would need 1,000,001 cells
an array indexed by rank needs      4

every pairwise comparison gives the same answer as before: True
decompressed: [1000000, 5, 300, 5, 99999, 300]

The check in the middle is the whole justification: every pairwise comparison gives the same answer after compression as before. Nothing that the algorithm relied on was lost. And the last line shows it is reversible — keep the sorted distinct array and you can map any rank back.

Cost: O(n log n) for the sort, O(n) afterwards.

Reach for it when the values are huge or sparse but the count of them is small — segment trees over coordinates, sweep lines, “count distinct in a range”, anything with timestamps.

Pattern 30 — PriorityQueue<TElement, TPriority>

This arrived in .NET 6. A lot of C# competitive programming material is older, and works around its absence with a SortedSet and a tie-breaking key. That is no longer necessary.

Two things about it are worth knowing before you use it.

It is a min-heap: the lowest priority comes out first. And the element is separate from the priority, which is what makes Dijkstra in part 8 readable — you enqueue a node with a distance, rather than packing both into a tuple and writing a comparer.

To keep the k largest values, use a min-heap of size k. That sounds backwards and is not: the root is the weakest of your current survivors, which is exactly the value a newcomer has to beat, and the only one worth comparing against.

int[] a = [5, 1, 9, 3, 7, 2, 8];
int k = 3;

// PriorityQueue is a MIN-heap: the smallest priority comes out first.
// To keep the k LARGEST, hold a min-heap of size k and evict its smallest.
PriorityQueue<int, int> topK = new();

foreach (int x in a)
{
    if (topK.Count < k)
    {
        topK.Enqueue(x, x);
        Console.WriteLine($"{x}  heap not full, keep it        -> [{string.Join(",", topK.UnorderedItems.Select(t => t.Element).Order())}]");
    }
    else if (x > topK.Peek())
    {
        // One operation instead of Dequeue then Enqueue: one sift, not two.
        int evicted = topK.EnqueueDequeue(x, x);
        Console.WriteLine($"{x}  beats the smallest ({evicted}), swap  -> [{string.Join(",", topK.UnorderedItems.Select(t => t.Element).Order())}]");
    }
    else
    {
        Console.WriteLine($"{x}  loses to the smallest ({topK.Peek()})   -> unchanged");
    }
}

List<int> result = [];
while (topK.Count > 0) result.Add(topK.Dequeue());
Console.WriteLine($"\ntop {k} largest, ascending: [{string.Join(", ", result)}]");

// Priority and element are separate, which is what makes Dijkstra readable.
PriorityQueue<string, int> tasks = new();
tasks.Enqueue("write tests", 2);
tasks.Enqueue("fix the bug", 1);
tasks.Enqueue("refactor", 3);
Console.WriteLine();
while (tasks.TryDequeue(out string? task, out int p))
    Console.WriteLine($"  priority {p}: {task}");

It prints:

5  heap not full, keep it        -> [5]
1  heap not full, keep it        -> [1,5]
9  heap not full, keep it        -> [1,5,9]
3  beats the smallest (1), swap  -> [3,5,9]
7  beats the smallest (3), swap  -> [5,7,9]
2  loses to the smallest (5)   -> unchanged
8  beats the smallest (5), swap  -> [7,8,9]

top 3 largest, ascending: [7, 8, 9]

  priority 1: fix the bug
  priority 2: write tests
  priority 3: refactor

EnqueueDequeue is the detail worth stealing. Pushing then popping sifts the heap twice; EnqueueDequeue does it in one, because it knows the new element is about to be compared with the root anyway.

Two things it does not have. There is no DecreaseKey, which is why Dijkstra in C# uses the lazy approach — push duplicates, skip stale ones on the way out. And UnorderedItems is exactly what it says: heap order, not sorted order. It is fine for inspecting, useless for output.

Cost: O(log n) per push and pop, O(n) space. Top-k over n items is O(n log k).

Reach for it when you need repeated “smallest remaining” — Dijkstra, k-way merge, task scheduling, top-k.

What to remember

• GetValueOrDefault then assign hashes the key twice. CollectionsMarshal.GetValueRefOrAddDefault does it once and hands back a ref.

• Small dense integer keys do not need a dictionary. An int[] is faster, simpler, and usually the intended solution.

• A grouping is only as good as its signature. It must be identical within a group and different outside it — no weaker, no stronger.

• Descending means reversing the operands, not negating the result. Negation breaks on int.MinValue.

• Array.Sort is unstable above 16 elements. Exactly 16 is stable by accident. Use OrderBy, or make ties impossible with a tie-breaker key.

• Compression keeps order and discards magnitude, which is all these problems ever used. Keep the sorted distinct array and it is reversible.

• PriorityQueue is a min-heap, and for the k largest that is what you want. Use EnqueueDequeue to sift once instead of twice, and remember there is no DecreaseKey.

Part 7 starts on graphs, and it opens with the representation — because List<List<int>> is what most C# contest solutions use, and it is also why they time out.