Start learning free

LESSON 291 OF 347 · HEAP

Smallest K Integers in C#: O(n log k) with a Max Heap

Practice O(n log k) Read the full explanation

Given an array of positive integers nums, return the smallest k values, in any order you want.

Example:

Input: nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5], k = 4
Output: [1, 2, 2, 3]
Explanation: Smallest number is 1, 2nd smallest is 2, 
            3rd smallest is 2, 4th smallest is 3

The result can be in any order, [2, 1, 3, 2] is also a correct answer.

Note:

For this lesson, your algorithm should run in O(n log k) time and use O(k) extra space.
(There are faster solutions which we will discuss in future lessons)


STEP 1 OF 6
    Ctrl + Enter to check

    C# · HEAP

    Smallest K in C#, explained

    Problem overview

    The method KSmallest receives an array nums of positive integers and a count k. It returns the k smallest values of the array, in any order. Duplicates count separately: they are values, not distinct numbers.

    In the example, nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5] and k = 4. Sorted, the array begins 1, 2, 2, 3, so the answer contains those four values. [1, 2, 2, 3] and [2, 1, 3, 2] are both correct.

    This lesson asks for O(n log k) time and O(k) extra space. Sorting the whole array would cost O(n log n). When k is much smaller than n, the heap approach in this lesson does less work and never stores more than k numbers.

    Approach: keep the k best so far, with the worst on top

    Scan the array once while holding the k smallest values seen so far. For each new value there are two cases:

    • If fewer than k values are held, keep the new one.
    • Otherwise, the new value only matters if it is smaller than the largest value held. In that case, the largest one is no longer among the k smallest, so it leaves and the new value takes its place.

    Both cases need quick access to the largest value held, and that is what a max heap provides: the greatest element is always on top, and inserting or removing costs O(log k) when the heap holds at most k items. With n values, the loop costs O(n log k).

    The trace for the example with k = 4 shows the heap's contents after each interesting value:

    • 5, 9, 3 and 6 fill the heap: {9, 6, 5, 3}.
    • 2 is smaller than the top, 9, so 9 leaves: {6, 5, 3, 2}.
    • 1 beats 6: {5, 3, 2, 1}.
    • 3 beats 5: {3, 3, 2, 1}.
    • 2 beats 3: {3, 2, 2, 1}.
    • 7 and 5 are not smaller than the top, 3, so they are ignored.

    The heap ends up holding exactly the four smallest values. The lesson lists other versions of this problem; this one stays with the max heap of size k.

    Step by step

    1. Create the max heap. C#'s PriorityQueue<TElement, TPriority> dequeues the element with the lowest priority first, so by default it is a min heap. Passing a comparer that reverses the order of priorities turns it into a max heap. Here the element and the priority are both an int.
    2. Loop over nums with foreach, naming the variable value.
    3. Fill the heap first. While Count is below k, every value is kept. Enqueue(value, value) uses the value as both the element and its priority.
    4. Handle a full heap. Compare value with Peek(), which reads the top, the largest value kept, without removing it.
    5. Swap when the new value is smaller. Dequeue() removes the largest, and Enqueue adds the new value, so the heap keeps exactly k values.
    6. Copy the heap into an array. After the loop, create result with length k and fill it by calling Dequeue() k times. The values come out from largest to smallest, which is fine because any order is accepted.

    The solution in C#

    class Solution {
    public int[] KSmallest(int[] nums, int k) {
        PriorityQueue<int, int> smallestKNums = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y - x));

        foreach (int value in nums) {
            if (smallestKNums.Count < k) {
                smallestKNums.Enqueue(value, value);
            } else if (value < smallestKNums.Peek()) {
                smallestKNums.Dequeue();
                smallestKNums.Enqueue(value, value);
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k; ++i) {
            result[i] = smallestKNums.Dequeue();
        }
        return result;
    }
}

    The C# details worth a closer look:

    • Two type arguments. PriorityQueue<int, int> stores elements and priorities separately. Enqueue(element, priority) takes both, while Dequeue() and Peek() return only the element. Because each value is its own priority, ordering by priority orders the values.
    • The comparer. Comparer<int>.Create builds a comparer from a lambda. A comparison returns a negative number when the first argument should come out first. Writing y - x swaps the arguments, so a larger priority comes out first.
    • Overflow in y - x. Subtraction on int wraps around silently when the result is out of range. With x = int.MinValue + 10 and y = 100, y - x wraps to a negative number instead of a large positive one. The lesson's values are small positive numbers, so the shortcut is safe here. Code that must handle any int is safer with y.CompareTo(x).
    • Count is a property. It has no parentheses, unlike Peek() and Dequeue().
    • Empty queues throw. Calling Peek() or Dequeue() on an empty PriorityQueue throws an InvalidOperationException.
    • Fixed-size result. new int[k] creates an array of k zeros. The loop overwrites each slot, with ++i and i++ behaving the same way in a loop header.

    Complexity

    Time: O(n log k). Each of the n values costs at most one Peek and one Dequeue/Enqueue pair, each O(log k) because the heap never holds more than k items. Emptying the heap into result costs O(k log k), which is no more than O(n log k) when k is at most n.

    Space: O(k). The heap holds at most k values, and the result array holds k more.

    Edge cases and common mistakes

    • Using a min heap by mistake. A default PriorityQueue puts the smallest value on top. Comparing with that top would tell you nothing about which kept value to throw away.
    • Duplicates. With [4, 4, 4] and k = 2, the answer is [4, 4]. The test value < Peek() is strict, so a value equal to the largest kept is skipped, and that is still correct because the kept set has the same values.
    • k equal to the array length. The heap just fills up and the result contains every value, largest first.
    • k below 1 or above the array length. The code assumes 1 <= k <= nums.Length. With k = 0, the first iteration calls Peek() on an empty queue. With k larger than the array, the final loop calls Dequeue() too many times. Both throw.
    • Peeking before the heap is full. The Count < k branch comes first, so Peek() is never called on an empty queue for valid k.
    • Result order. The returned array is in descending order. For the example it is [3, 2, 2, 1], which is an accepted answer.

    Testing

    • nums = [5, 9, 3, 6, 2, 1, 3, 2, 7, 5], k = 4 gives [3, 2, 2, 1], which has the same values as [1, 2, 2, 3].
    • nums = [4, 4, 4], k = 2 gives [4, 4].
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free