Start learning free

LESSON 402 OF 573 · HEAP

Kth Largest Element in a Stream in TypeScript: 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

    TYPESCRIPT · HEAP

    Kth Largest Element In A Stream in TypeScript, explained

    Problem overview

    Numbers arrive one at a time, and after each one the class must report 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.

    The lesson asks for a class KthLargest with a constructor constructor(k: number, nums: number[]) that receives the numbers that have arrived already, and a method add(val: number): number that takes in a new number and returns the current k-th largest. The lesson provides a ready-to-use MinHeap class with insert, extract, peek, size and isEmpty.

    Take k = 3 and starting numbers [4, 5, 8, 2]. After add(3) the numbers are 2, 3, 4, 5, 8, so the three largest are 8, 5 and 4 and the answer is 4. Running the five calls add(3), add(5), add(10), add(9), add(4) on that object returns:

    4 5 5 8 8

    The last call, add(4), changes nothing at the top: 4 is smaller than the current 3rd largest (8), so it can't enter the top three.

    Approach: keep only the k largest

    The simple approach stores every number, sorts them on each add and reads the element at position k from the top. Sorting costs O(n log n) per call, where n is how many numbers have arrived, and the cost grows with the stream.

    The better idea starts from an observation: a number that is below the k-th largest can never matter again. Numbers only arrive, never leave, so the k-th largest can only stay the same or go up. Only the k largest numbers are worth keeping.

    Keep those k numbers in a min-heap. A min-heap gives the smallest of its values in O(1) and inserts or removes in O(log size). The smallest of the k largest numbers is exactly the k-th largest, so it sits on top, and the answer to every add is one peek().

    To add a value: insert it, and if the heap now holds more than k values, extract the top. The smallest of k + 1 values is not among the k largest, so dropping it is always right. The heap never holds more than k + 1 values, so each add costs O(log k), and the object stores O(k) values, however long the stream gets.

    Step by step

    1. Declare the field k as a number: add needs it later, and a constructor parameter disappears when the constructor ends.
    2. Declare largest as a MinHeap, set to new MinHeap(). It will hold the k largest values seen so far.
    3. In the constructor, store k in this.k.
    4. Loop over nums with for (const num of nums). The starting numbers count like any other number.
    5. Call this.add(num) inside the loop. add already keeps the heap at k values, so the constructor reuses it. The returned value is ignored, because nobody has asked yet.
    6. In add, insert val into this.largest.
    7. Trim the heap: if this.largest.size() is greater than this.k, call extract() to drop the smallest value.
    8. Return this.largest.peek(), the smallest of the k largest values.

    The solution in TypeScript

    class KthLargest {
    k: number;
    largest: MinHeap = new MinHeap();

    constructor(k: number, nums: number[]) {
        this.k = k;
        for (const num of nums) {
            this.add(num);
        }
    }

    add(val: number): number {
        this.largest.insert(val);
        if (this.largest.size() > this.k) {
            this.largest.extract();
        }
        return this.largest.peek();
    }
}

    A few details:

    • The fields are declared with types, and largest is initialized right in the declaration, so every KthLargest object gets its own heap. The types are checked when the file is compiled and erased afterwards; they do nothing at run time.
    • this.add(num) in the constructor is an ordinary method call: by that point this.k and this.largest already exist.
    • peek() reads the top and leaves it in the heap. extract() removes the top and returns it, and the code above discards what it returns.
    • With the starting numbers [4, 5, 8, 2] and k = 3, the constructor ends with a heap of size 3 and the value 4 on top.

    Complexity

    Each add does one insert and at most one extract on a heap of at most k + 1 values, so it takes O(log k) time. The constructor calls add once per starting number, so it takes O(m log k) for m starting numbers. The object keeps at most k values: O(k) space.

    Compare that with sorting on every call: O(n log n) per add and O(n) space, both growing with the stream.

    Edge cases and common mistakes

    • Duplicates count separately. With k = 4 and starting numbers [7, 7, 7, 7, 8, 3], the calls add(2), add(10), add(9), add(9) return 7 7 7 8. Removing duplicates would give wrong answers.
    • Starting with an empty array. new KthLargest(1, []) followed by add(-3), add(-2), add(-4), add(0), add(4) returns -3 -2 -2 0 4. The heap simply starts empty.
    • Fewer than k values so far. The lesson promises that at least k values exist when add returns. Inside the constructor, the heap may hold fewer than k values, and that is fine: the check only extracts when the size goes above k. For new KthLargest(2, [5]), add(1) returns 1, the 2nd largest of 5 and 1.
    • Using a max-heap by mistake. A max-heap would put the largest value on top, which is not what add must return. The top of a min-heap of the k largest is the k-th largest.
    • Sorting with no comparator. If you try the sorting approach on numbers, remember that sort() with no comparator sorts as strings: [10, 9, 1].sort() gives [1, 10, 9]. Pass (a, b) => a - b.
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free