You almost never need the data sorted. You need its extremes. A heap of size K gives you those in O(n log K) instead of O(n log n). It also works on a stream you cannot hold in memory.
Sorting a million items to find the top three does far more work than the question asks for. A heap answers “what is the smallest thing I am keeping?” in O(1). It lets you replace that item in O(log K). That one move is the whole pattern. In C#, the heap is PriorityQueue<TElement, TPriority>, built into .NET since version 6.
n with a small k.Add method”, “you cannot store everything”.PriorityQueuePriorityQueue<TElement, TPriority> lives in System.Collections.Generic. Each entry is an element plus a separate priority. The queue only ever compares priorities. Six facts cover almost every interview.
Peek() and Dequeue() return the element with the smallest priority. Both throw InvalidOperationException on an empty queue. TryPeek and TryDequeue return false instead.Comparer<int>.Create((a, b) => b.CompareTo(a)). Or enqueue with priority -value. Negation breaks on int.MinValue, so the comparer is the safer habit.IEnumerable<(TElement, TPriority)> heapifies in one pass. That beats n separate Enqueue calls at O(n log n).DequeueEnqueue(e, p) removes the root, then adds the new entry with one sift. EnqueueDequeue(e, p) adds first, then removes the smallest. If the new priority is not bigger than the root, it hands the new element straight back and leaves the heap alone.Remove (.NET 9 and later). Remove is a linear search, so it costs O(n).UnorderedItems is not sorted. It walks the internal array in heap order. Only the root is in its final place. To get sorted output, dequeue until empty, or sort the items yourself.heapq compares whole tuples, so a tie can crash on an unorderable payload. C# never compares elements, so nothing crashes. But two equal priorities come out in no promised order. When the order matters, make the priority a value tuple such as (score, index). Value tuples compare left to right, so the index settles every tie.The class below shows the max-heap tricks, an O(n) build, an in-order drain, and the Remove workaround for decrease-key.
public static class PqFacts
{
/// <summary>Largest value, read from a max-heap built with a reversed comparer.</summary>
/// <param name="nums">Values to scan. Must not be empty.</param>
/// <returns>The maximum of <paramref name="nums"/>.</returns>
/// <example><c>PqFacts.MaxWithReverseComparer([4, 9, 2])</c> returns 9.</example>
public static int MaxWithReverseComparer(int[] nums)
{
// b.CompareTo(a) flips the order, so the biggest priority sits at the root.
var reverse = Comparer<int>.Create((a, b) => b.CompareTo(a));
var maxHeap = new PriorityQueue<int, int>(reverse);
// value is the next number. Invariant: the root is the max of all enqueued so far.
foreach (int value in nums)
{
// The value is both the element and its priority.
maxHeap.Enqueue(value, value);
}
return maxHeap.Peek();
}
/// <summary>Largest value, read from a min-heap keyed on the negated value.</summary>
/// <param name="nums">Values to scan. Must not be empty or hold int.MinValue.</param>
/// <returns>The maximum of <paramref name="nums"/>.</returns>
/// <example><c>PqFacts.MaxWithNegation([4, 9, 2])</c> returns 9.</example>
public static int MaxWithNegation(int[] nums)
{
var heap = new PriorityQueue<int, int>();
// value is the next number. Invariant: the root is the max of all enqueued so far.
foreach (int value in nums)
{
// Minus sign: the biggest value gets the smallest priority, so it is the root.
// -int.MinValue overflows back to int.MinValue, which is why the comparer is safer.
heap.Enqueue(value, -value);
}
return heap.Peek();
}
/// <summary>Heapify all values in O(n), then dequeue until empty.</summary>
/// <param name="nums">Values to sort.</param>
/// <returns>The values in ascending order.</returns>
/// <example><c>PqFacts.DrainInOrder([5, 1, 4])</c> returns [1, 4, 5].</example>
public static List<int> DrainInOrder(int[] nums)
{
// The constructor that takes (element, priority) pairs heapifies them in one O(n) pass.
var heap = new PriorityQueue<int, int>(nums.Select(value => (value, value)));
// nums.Length: final size, so the list never has to grow.
var sorted = new List<int>(nums.Length);
// Invariant: sorted holds the smallest values dequeued so far, in ascending order.
while (heap.TryDequeue(out int value, out _))
{
sorted.Add(value);
}
return sorted;
}
/// <summary>Changes one task's priority. No decrease-key, so remove and re-add.</summary>
/// <returns>The task at the root after the change.</returns>
/// <example><c>PqFacts.Reprioritize()</c> returns "email".</example>
public static string Reprioritize()
{
var tasks = new PriorityQueue<string, int>();
tasks.Enqueue("email", 5); // 5: low urgency, a small number means more urgent
tasks.Enqueue("deploy", 2); // 2: smaller than 5, so deploy is the root for now
// Remove (.NET 9+) does a linear search for "email". O(n), so use it sparingly.
tasks.Remove("email", out _, out _);
// 1: smaller than 2, so email becomes the new root.
tasks.Enqueue("email", 1);
return tasks.Peek();
}
}
nlargest. The production one-liner is nums.OrderDescending().Take(k). It is short and clear, and it is fine for most real data. In an interview, write the heap loop first. Then say “in real code I would reach for OrderDescending().Take(k) unless the data is a stream.” Both halves of that sentence score.public static class KLargestTemplate
{
/// <summary>The k largest values, in no particular order.</summary>
/// <param name="nums">Values to scan.</param>
/// <param name="k">How many to keep. 0 gives an empty list.</param>
/// <returns>The k largest values in heap order, not sorted.</returns>
/// <example><c>KLargestTemplate.KLargest([5, 1, 9, 3, 7], 3)</c> holds 5, 7 and 9.</example>
public static List<int> KLargest(int[] nums, int k)
{
// Min-heap: the root is the weakest value kept. k: initial capacity, so no regrowth.
var heap = new PriorityQueue<int, int>(k);
// value is the next number.
// Invariant: heap holds the k largest values seen so far (fewer at the start).
foreach (int value in nums)
{
if (heap.Count < k)
{
// Still filling up: every value earns a seat until there are k.
heap.Enqueue(value, value);
}
// TryPeek is false only when k is 0. Then nothing is ever admitted.
else if (heap.TryPeek(out _, out int weakest) && value > weakest)
{
// Beats the weakest survivor: drop the root and add value in one sift.
heap.DequeueEnqueue(value, value);
}
}
// UnorderedItems walks the internal array. Only the root is in order.
return heap.UnorderedItems.Select(pair => pair.Element).ToList();
}
}
For the K smallest, flip both. Build the queue with a reversed comparer and admit when value < weakest.
Reading the figure. Amber is the incoming value. Blue boxes change the heap. Red means the value is dropped. Notice that once the heap is full, only one test runs: value > heap.Peek().
Once the heap is full, EnqueueDequeue can replace the test and the call together. It hands back whichever is smallest: the new value or the old root. If the new value loses, it bounces straight back out and the heap does not change.
// Heap already holds k values. One call does the compare and the swap.
// The return value is whatever left: the old root, or value itself if it lost.
int leaving = heap.EnqueueDequeue(value, value);
public static class KBestTemplate
{
/// <summary>The k items with the largest score, in no particular order.</summary>
/// <typeparam name="TItem">Item type. Items are never compared, only scores.</typeparam>
/// <param name="items">Items to rank.</param>
/// <param name="k">How many to keep.</param>
/// <param name="score">Ranking key. Bigger is better.</param>
/// <returns>The k best items in heap order.</returns>
/// <example><c>KBestTemplate.KBest(["aa", "b", "cccc"], 2, s => s.Length)</c>
/// holds "aa" and "cccc".</example>
public static List<TItem> KBest<TItem>(IEnumerable<TItem> items, int k, Func<TItem, long> score)
{
// Priority is (score, index). Value tuples compare left to right,
// so a tie on score falls back to index and the order is fixed.
var heap = new PriorityQueue<TItem, (long Score, int Index)>();
// 0: the first item gets index 0.
int index = 0;
// item is the next candidate. Invariant: heap holds the k best items seen so far.
foreach (TItem item in items)
{
// score(item) is the placeholder ranking key, bigger is better.
// Top K Frequent: the count. K Closest: -(x * x + y * y).
var priority = (score(item), index);
index++; // +1: the next item gets the next index
if (heap.Count < k)
{
// Fewer than k kept: admit without a contest.
heap.Enqueue(item, priority);
}
// weakest is the root's priority. CompareTo above 0 means priority beats it.
else if (heap.TryPeek(out _, out var weakest) && priority.CompareTo(weakest) > 0)
{
// Swap out the weakest for the new item. Size stays at k.
heap.DequeueEnqueue(item, priority);
}
}
return heap.UnorderedItems.Select(pair => pair.Element).ToList();
}
}
Reading the figure. A value tuple compares one slot at a time, left to right. Amber shows the tie on score. Green shows the index that settles it. The grey item is the element, and the queue never looks at it. The red bar shows what goes wrong with no index.
Enqueue then Dequeue instead of DequeueEnqueue. Correct, but twice the sifting. It also briefly holds K+1 items.UnorderedItems as sorted. It is not. Only the root is meaningful. Printing it to “check” the heap will mislead you.Peek() on an empty queue. It throws. Guard with Count or use TryPeek. This bites when k is 0.int.MinValue for a fake max-heap. It overflows to itself. Use a reversed comparer or a long priority.Remove.Return the k-th largest element in an unsorted array. This is the k-th largest in sorted order, not the k-th distinct value.
k largest values seen. When the scan ends, the root is the smallest of the top k. That is exactly the k-th largest.k values through the constructor. It heapifies them in O(k), not one at a time.nums.OrderDescending().ElementAt(k - 1) ready as the one-liner.public static class KthLargest
{
/// <summary>The k-th largest value in nums, counting duplicates.</summary>
/// <param name="nums">Integers, unsorted.</param>
/// <param name="k">1-based rank from the top, with 1 <= k <= nums.Length.</param>
/// <returns>The k-th largest value.</returns>
/// <exception cref="ArgumentOutOfRangeException">k is outside 1..nums.Length.</exception>
/// <example><c>KthLargest.WithHeap([3, 2, 1, 5, 6, 4], 2)</c> returns 5.</example>
public static int WithHeap(int[] nums, int k)
{
// 1: k is a 1-based rank, so 1 is the smallest legal k. nums.Length is the largest.
if (k < 1 || k > nums.Length)
{
throw new ArgumentOutOfRangeException(nameof(k), $"k must be in 1..{nums.Length}");
}
// nums[..k]: indexes 0..k-1, exactly k values. The constructor heapifies in O(k).
var heap = new PriorityQueue<int, int>(nums[..k].Select(value => (value, value)));
// AsSpan(k): a view from index k to the end, no copy. These were not seeded.
// Invariant: heap holds the k largest of the values scanned so far.
foreach (int value in nums.AsSpan(k))
{
// Peek() is the root, the smallest of the k kept.
if (value > heap.Peek())
{
// Evict the root, insert value. Size stays at k.
heap.DequeueEnqueue(value, value);
}
}
// The root is the weakest of the k largest, which is the k-th largest.
return heap.Peek();
}
}
nums = [3, 2, 1, 5, 6, 4], k = 2. Seed the heap with the first two values. Then scan the other four.
Reading the figure. Each frame is one step of the loop. The top circle is the root, the weakest value kept. Amber is a value that gets in. Red is a value that is skipped or evicted. The green root in the last frame is the answer.
public static class KthLargestQuickselect
{
/// <summary>The k-th largest value in O(n) expected time. Reorders nums in place.</summary>
/// <param name="nums">Integers, unsorted. This array is mutated.</param>
/// <param name="k">1-based rank from the top, with 1 <= k <= nums.Length.</param>
/// <returns>The k-th largest value.</returns>
/// <exception cref="ArgumentOutOfRangeException">k is outside 1..nums.Length.</exception>
/// <example><c>KthLargestQuickselect.Find([3, 2, 1, 5, 6, 4], 2)</c> returns 5.</example>
public static int Find(int[] nums, int k)
{
// 1: the smallest legal rank. nums.Length: the largest.
if (k < 1 || k > nums.Length)
{
throw new ArgumentOutOfRangeException(nameof(k), $"k must be in 1..{nums.Length}");
}
// In ascending order the k-th largest sits k slots from the end.
int target = nums.Length - k;
// 0 is the first index. nums.Length - 1 is the last index.
int left = 0, right = nums.Length - 1;
// Invariant: target lies inside nums[left..right], the unsettled window.
while (left <= right)
{
// A random pivot makes the O(n^2) worst case vanishingly unlikely.
// Next's upper bound is exclusive, so right + 1 lets right be picked.
int pivotIndex = Partition(nums, left, right, Random.Shared.Next(left, right + 1));
if (pivotIndex == target)
{
// The pivot landed exactly on the rank we want.
return nums[pivotIndex];
}
if (pivotIndex < target)
{
left = pivotIndex + 1; // + 1: target is right of the settled pivot
}
else
{
right = pivotIndex - 1; // - 1: target is left of the settled pivot
}
}
// Unreachable: k was checked, so target is always inside the window.
throw new InvalidOperationException("k out of range");
}
/// <summary>Lomuto partition. Returns the pivot's final, sorted index.</summary>
private static int Partition(int[] nums, int left, int right, int pivotIndex)
{
int pivot = nums[pivotIndex];
// Park the pivot at the right end so the scan below never moves it.
(nums[pivotIndex], nums[right]) = (nums[right], nums[pivotIndex]);
// store is the next slot for a value smaller than the pivot.
int store = left;
// i stops before right: right holds the parked pivot.
// Invariant: nums[left..store-1] are all less than pivot.
for (int i = left; i < right; i++)
{
if (nums[i] < pivot)
{
// Move the small value into the "less than" zone.
(nums[store], nums[i]) = (nums[i], nums[store]);
store++; // +1: the zone grew by one slot
}
}
// Drop the pivot between the two zones. It is now in its sorted position.
(nums[store], nums[right]) = (nums[right], nums[store]);
return store;
}
}
T(n) = 2T(n/2) + n, which is O(n log n). Quickselect recurses into one half: T(n) = T(n/2) + n. The series n + n/2 + n/4 + … sums to 2n. That one comparison is the answer the interviewer wants.nums.OrderDescending().ElementAt(k - 1). It sorts, but it is clear and hard to get wrong.k == 1: the maximum. k == nums.Length: the minimum.[3, 3, 3] with k = 2 gives 3. Rank counts positions, not distinct values.k out of range: both versions throw ArgumentOutOfRangeException up front.nums.ToArray() to work on a copy.Given an array nums and an integer k, return the k most frequent elements, in any order.
Dictionary<int, int> pass in O(n). The real choice is in the selection.k highest counts. That is O(m log k), where m is the number of distinct values.n. So index an array of lists by count and walk it downward. That is O(n) and beats the heap. “Better than O(n log k)” means this.using System.Runtime.InteropServices;
public static class TopKFrequent
{
/// <summary>The k most frequent values in nums, in no particular order.</summary>
/// <param name="nums">Input values.</param>
/// <param name="k">How many to return, with 0 <= k <= number of distinct values.</param>
/// <returns>The k values with the highest counts.</returns>
/// <example><c>TopKFrequent.WithHeap([1, 1, 1, 2, 2, 3], 2)</c> holds 1 and 2.</example>
public static int[] WithHeap(int[] nums, int k)
{
// Phase 1: count each value in one O(n) pass.
var counts = new Dictionary<int, int>();
foreach (int value in nums)
{
// A ref to the slot: one hash lookup instead of a read plus a write.
ref int slot = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, value, out _);
slot++; // +1: one more sighting. A new slot starts at 0, the int default.
}
// Priority is the frequency, so the root is the least frequent value kept.
var heap = new PriorityQueue<int, int>();
// Invariant: heap holds the k highest-count values seen so far.
foreach (var (value, frequency) in counts)
{
if (heap.Count < k)
{
// Fewer than k kept: admit without a contest.
heap.Enqueue(value, frequency);
}
// weakest is the root's frequency. TryPeek is false only when k is 0.
else if (heap.TryPeek(out _, out int weakest) && frequency > weakest)
{
// More frequent than the weakest kept: swap it in. Size stays at k.
heap.DequeueEnqueue(value, frequency);
}
}
// Drop the priorities and keep only the values.
return [.. heap.UnorderedItems.Select(pair => pair.Element)];
}
}
public static class TopKFrequentBuckets
{
/// <summary>Same answer in linear time, by using each count as an array index.</summary>
/// <param name="nums">Input values.</param>
/// <param name="k">How many to return.</param>
/// <returns>Up to k values, highest count first. Ties come out in no fixed order.</returns>
/// <example><c>TopKFrequentBuckets.Find([1, 1, 1, 2, 2, 3], 2)</c> returns [1, 2].</example>
public static List<int> Find(int[] nums, int k)
{
var counts = new Dictionary<int, int>();
foreach (int value in nums)
{
// GetValueOrDefault gives 0 for a new value. + 1 counts this sighting.
counts[value] = counts.GetValueOrDefault(value) + 1;
}
// buckets[f] holds every value that occurs exactly f times.
// nums.Length + 1 slots so index nums.Length exists: counts run 1..nums.Length.
var buckets = new List<int>?[nums.Length + 1];
foreach (var (value, frequency) in counts)
{
// ??= makes the list on first use. Empty buckets stay null and cost nothing.
(buckets[frequency] ??= []).Add(value);
}
var result = new List<int>();
// frequency walks from the largest possible count, nums.Length, down to 1.
// Stop at 0: no value occurs 0 times. -- steps downward.
// Invariant: result holds values whose counts are above frequency.
for (int frequency = nums.Length; frequency > 0; frequency--)
{
// Most buckets are empty. Skip them.
if (buckets[frequency] is not { } bucket)
{
continue;
}
foreach (int value in bucket)
{
// Checked before adding, so k = 0 returns an empty list.
if (result.Count == k)
{
return result;
}
result.Add(value);
}
}
// Reached when k is at least the number of distinct values.
return result;
}
}
nums = [1, 1, 1, 2, 2, 3], k = 2. Counts are {1: 3, 2: 2, 3: 1}. Bucket 1 holds [3]. Bucket 2 holds [2]. Bucket 3 holds [1]. Walk down from index 6. Buckets 6, 5 and 4 are empty. Bucket 3 gives 1. Bucket 2 gives 2. Now we have two, so return [1, 2].
Reading the figure. Blue cells hold counts or values not yet taken. Grey cells are empty buckets. The amber arrow is the walk from high counts to low. Green buckets are the ones the walk takes before it reaches k.
public static class TopKFrequentLinq
{
/// <summary>What you would actually ship: count, sort by count, take k.</summary>
/// <param name="nums">Input values.</param>
/// <param name="k">How many to return.</param>
/// <returns>The k most frequent values, highest count first.</returns>
/// <example><c>TopKFrequentLinq.Find([1, 1, 1, 2, 2, 3], 2)</c> returns [1, 2].</example>
public static int[] Find(int[] nums, int k) =>
// CountBy (.NET 9+) yields one (Key, Value) pair per distinct value, Value = count.
[.. nums.CountBy(value => value)
.OrderByDescending(pair => pair.Value)
.Take(k)
.Select(pair => pair.Key)];
}
CountBy arrived in .NET 9. On older targets, use GroupBy(v => v) and g.Count(). The sort makes this O(m log m), not O(m log k). Write your own version first. Then show this one.
k equals the number of distinct values: returns all of them.k of them is a valid answer.k = 0: returns an empty array. Ask whether k can be zero.Given a list of points on a plane and an integer k, return the k points closest to the origin. Distance is the usual Euclidean distance.
Math.Sqrt only ever goes up as its input goes up. So ordering by x² + y² gives the same ranking as ordering by √(x² + y²). Skipping it saves n floating-point calls. It also keeps every comparison in exact integers. Say this unprompted.long. C# int is 32-bit. 46341 * 46341 already passes int.MaxValue, and the overflow is silent. Cast to long before you multiply.public static class KClosest
{
/// <summary>The k points nearest the origin, in no particular order.</summary>
/// <param name="points">Each point is [x, y] in integer coordinates.</param>
/// <param name="k">How many to return, with 0 <= k <= points.Length.</param>
/// <returns>The k closest points.</returns>
/// <example><c>KClosest.Find([[1, 3], [-2, 2], [5, 8], [0, 1]], 2)</c>
/// holds [-2, 2] and [0, 1].</example>
public static int[][] Find(int[][] points, int k)
{
// Reversed comparer: the biggest squared distance sits at the root.
// So the root is the furthest point we are keeping.
var furthestFirst = Comparer<long>.Create((a, b) => b.CompareTo(a));
var heap = new PriorityQueue<int[], long>(furthestFirst);
// point is the next candidate. Invariant: heap holds the k closest points seen so far.
foreach (int[] point in points)
{
// point[0] is x and point[1] is y. long first, so squaring cannot overflow.
long x = point[0], y = point[1];
// Squared distance: same order as the true distance, and no Math.Sqrt.
long distance = x * x + y * y;
if (heap.Count < k)
{
// Fewer than k kept: admit without a contest.
heap.Enqueue(point, distance);
}
// worst is the root's distance. TryPeek is false only when k is 0.
else if (heap.TryPeek(out _, out long worst) && distance < worst)
{
// Closer than the furthest kept: evict it. Size stays at k.
heap.DequeueEnqueue(point, distance);
}
}
// Drop the distances and keep only the points.
return [.. heap.UnorderedItems.Select(pair => pair.Element)];
}
}
Python fakes a max-heap by negating the distance. That works in C# too: enqueue with priority -distance on a default queue. The reversed comparer reads more plainly, and it has no edge case at long.MinValue.
points = [[1,3],[-2,2],[5,8],[0,1]], k = 2. Squared distances are 10, 8, 89 and 1.
[1, 3], d² = 10. The heap is not full, so enqueue it.[-2, 2], d² = 8. The heap is not full, so enqueue it. The root is now [1, 3] at 10.[5, 8], d² = 89. Root is 10. 89 > 10, so reject it.[0, 1], d² = 1. Root is 10. 1 < 10, so evict [1, 3] and keep [0, 1].Result: [[-2, 2], [0, 1]].
Reading the figure. Each frame handles one point. Boxes inside a frame are the heap, with the root on top and a thick border. Amber is a point that gets in. Red is a point that is skipped or evicted. Green marks the final two points.
points.OrderBy(p => (long)p[0] * p[0] + (long)p[1] * p[1]).Take(k). O(n log n). Production.k == points.Length: every point is returned.int[] elements, so nothing throws.0, always closest.int without warning. The solution squares in long. Mention checked as the way to make overflow throw.long. Square root keeps the order, so skipping it keeps everything in exact integers. I want the K smallest, so the size-K heap is a max-heap. In C# that means a reversed comparer.”PriorityQueue is a min-heap. Use a reversed comparer for a max-heap. Heapify through the constructor in O(n). Use DequeueEnqueue or EnqueueDequeue to pop and push at once.Math.Sqrt. Square in long so nothing overflows.Pattern 10, Subsets and Backtracking, goes the other way. It does not shrink the problem to K items. It walks an exponential space on purpose. The skill is pruning that space before it eats the clock.