Start learning free

LESSON 401 OF 572 · HEAP

Kth Largest Element in a Stream in C#: A Min-Heap of Size k

Practice O(log k) Read the full explanation

Numbers arrive one at a time, like the scores of a game coming in live, and after each one you must say which number is in k-th place: the k-th largest of all the numbers so far. Equal numbers count separately: in [8, 7, 7, 5] the 2nd largest is 7, and so is the 3rd.

Implement the class KthLargest:

  • KthLargest(k, nums) creates the object with the integer k and the numbers nums that have arrived already.
  • add(val) adds the number val and returns the k-th largest of all the numbers so far.

The input describes one new KthLargest and a list of add calls, applied in order. The output lists what the add calls return, in order. The starter code spells these names the way your language does.

 

Example 1:

Input:
    KthLargest(3, [4, 5, 8, 2])
    add(3)
    add(5)
    add(10)
    add(9)
    add(4)
Output: 4 5 5 8 8
Explanation:
After add(3) the numbers are [2, 3, 4, 5, 8]: the three largest are 8, 5 and 4, so the 3rd largest is 4.
After add(5): 8, 5, 5 are the three largest, so the answer is 5.
After add(10): 10, 8, 5, answer 5. After add(9): 10, 9, 8, answer 8.
add(4) changes nothing at the top: 4 is smaller than the 3rd largest, so the answer stays 8.

Example 2:

Input:
    KthLargest(1, [])
    add(-3)
    add(-2)
    add(-4)
    add(0)
    add(4)
Output: -3 -2 -2 0 4
Explanation: With k = 1, add returns the largest number so far. No numbers have arrived when the object is created, so after the first add, -3 is the only one, and the largest.

Example 3:

Input:
    KthLargest(4, [7, 7, 7, 7, 8, 3])
    add(2)
    add(10)
    add(9)
    add(9)
Output: 7 7 7 8
Explanation: Equal numbers count separately: in [8, 7, 7, 7, 7, 3, 2] the 4th largest is the third 7. After 10 and 9 arrive the four largest are 10, 9, 8, 7. The second 9 pushes the last 7 out: 10, 9, 9, 8, so the answer becomes 8.

 

Constraints:

  • 1 <= k <= 105
  • 0 <= nums.length <= 105
  • -104 <= nums[i], val <= 104
  • At most 105 calls are made to add.
  • When add returns, at least k numbers have arrived, so the k-th largest always exists.

Note:

Each add should run in O(log k) time, and the object should keep only O(k) values. Sorting all the numbers again on every add would take O(n log n) time per call, where n is how many numbers have arrived so far.

STEP 1 OF 8
    Ctrl + Enter to check

    C# · HEAP

    Kth Largest Element In A Stream in C#, explained

    Problem overview

    You write the class KthLargest. Its constructor receives k and the numbers that have already arrived. Each call to Add(val) takes in one more number and returns the k-th largest of everything seen so far. Equal numbers count separately: in [8, 7, 7, 5] the 2nd largest and the 3rd largest are both 7.

    Take k = 3 and the starting numbers [4, 5, 8, 2]. Calling Add with 3, 5, 10, 9 and 4 returns this:

    Add(3) -> 4
Add(5) -> 5
Add(10) -> 5
Add(9) -> 8
Add(4) -> 8

    After Add(3) the numbers are 2, 3, 4, 5, 8. The three largest are 8, 5 and 4, so the 3rd largest is 4. The last call adds a 4, which is smaller than the current 3rd largest (8), so the answer stays 8.

    With k = 1 and no starting numbers, adding -3, -2, -4, 0 and 4 returns -3 -2 -2 0 4: each answer is the largest number so far.

    Approach: keep only the k largest

    The direct way is to store every number, sort the list on each Add, and read the element at position k from the top. If n numbers have arrived, each call costs O(n log n). With up to 100,000 starting numbers and 100,000 calls, that is far too slow.

    The key observation is that most numbers can never be the answer. New numbers only push the k-th largest up, never down. So a number that is not among the k largest now will not be among them later, and it can be thrown away. You only need to remember the k largest numbers.

    Keep those k numbers in a min-heap, a structure that always hands out its smallest value first. The smallest of the k largest values is, by definition, the k-th largest. It sits on top of the heap, so reading the answer is a single Peek().

    To add a value, put it in the heap. If the heap now holds k + 1 values, remove the smallest: it cannot be among the k largest. The heap never holds more than k + 1 values, so each push and pop costs O(log k), and the object stores only O(k) values.

    Here is the heap for k = 3 as the starting numbers 4, 5, 8 and 2 go in one by one. Each line shows the heap's top and its size after the step:

    after 4: top 4, count 1
after 5: top 4, count 2
after 8: top 4, count 3
after 2: top 4, count 3

    The 2 went in and came straight out again, because it was the smallest of four values. The heap holds 4, 5 and 8, with 4 on top.

    Step by step

    1. Declare the field k, because Add needs to know how many values to keep.
    2. Declare largest, a PriorityQueue<int, int>. C#'s PriorityQueue<TElement, TPriority> stores each element with a priority and returns the smallest priority first, so a plain one is already a min-heap.
    3. In the constructor, store the parameter in the field with this.k = k. The parameter and the field share a name, so this.k is the field.
    4. Loop over nums and call Add for each value. The starting numbers go through the same filter as every later one, and the constructor does not repeat the heap logic. The returned value is ignored: nobody has asked yet.
    5. In Add, Enqueue the value with itself as its priority, so the heap orders the values themselves.
    6. If largest.Count is now more than k, call Dequeue() to drop the smallest.
    7. Return largest.Peek(), the top of the heap.

    The solution in C#

    class KthLargest {
    int k;
    PriorityQueue<int, int> largest = new PriorityQueue<int, int>();

    public KthLargest(int k, int[] nums) {
        this.k = k;
        foreach (int num in nums) {
            Add(num);
        }
    }

    public int Add(int val) {
        largest.Enqueue(val, val);
        if (largest.Count > k) {
            largest.Dequeue();
        }
        return largest.Peek();
    }
}

    Two C# details matter here. First, PriorityQueue takes the element and its priority as two separate arguments, which is why val appears twice in Enqueue(val, val). Second, Dequeue() removes and returns the element with the smallest priority, while Peek() only reads it.

    Run on the other two examples, the class gives -3 -2 -2 0 4 for k = 1, and 7 7 7 8 for k = 4 with starting numbers [7, 7, 7, 7, 8, 3] and the calls 2, 10, 9, 9.

    Complexity

    • Time: each Add does one Enqueue and at most one Dequeue on a heap of at most k + 1 values, so O(log k). The constructor makes one Add per starting number, O(n log k) for n numbers.
    • Space: O(k), because the heap never holds more than k values after an Add finishes.

    Edge cases and common mistakes

    • Duplicates count separately. With k = 4 and the numbers 8, 7, 7, 7, 7, the 4th largest is a 7. A set would collapse the equal numbers and give the wrong answer.
    • Fewer than k starting numbers. The constructor may receive fewer than k numbers, or none at all. The heap then holds fewer than k values until enough have arrived. At least k numbers have arrived whenever Add returns, so Peek() is safe there.
    • A max-heap is the wrong tool. It puts the largest value on top, and you would have to pop k - 1 values to reach the k-th. The min-heap of size k puts the answer on top.
    • Forgetting the field. Without storing k in the class, Add cannot tell when to drop a value.
    • Sorting on every call. It passes small tests and runs out of time on large ones.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free