Start learning free

LESSON 398 OF 569 · HEAP

Kth Largest Element in a Stream in JavaScript: Min-Heap

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 7
    Ctrl + Enter to check

    JAVASCRIPT · HEAP

    Kth Largest Element In A Stream in JavaScript, 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 is 7, and so is the 3rd.

    The class is KthLargest. Its constructor receives k and the numbers that have already arrived, nums. The method add(val) takes in one more number and returns the current k-th largest. The constraints promise that at least k numbers have arrived whenever add returns, so the answer always exists.

    Here is the first example in use: new KthLargest(3, [4, 5, 8, 2]), then add(3), add(5), add(10), add(9) and add(4). The calls return:

    4 5 5 8 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. Adding 5 makes the top three 8, 5, 5, so the answer becomes 5. The last call, add(4), changes nothing at the top: 4 is smaller than the current 3rd largest, so the answer stays 8.

    Approach: keep only the k largest, in a min-heap

    The simple approach stores every number, sorts them on each add and reads the element at position k - 1 of the descending order. That costs O(n log n) per call, where n is how many numbers have arrived. With up to 100,000 numbers and 100,000 calls it becomes slow. On 20,000 add calls with k = 10, a version that re-sorts an array each time took 2727 ms in a test run, while the heap version below took 6 ms, with identical answers.

    The better idea starts with an observation: a number that is not among the k largest can never become the answer again. Numbers only arrive, never leave, so the k-th largest value can only stay the same or go up. Anything below it is dead weight. The class therefore keeps just the k largest values seen so far.

    It keeps them in a min-heap, a structure that always has its smallest value on top and can insert a value or remove the top in O(log size). The smallest of the k largest values is exactly the k-th largest, so the answer is always sitting on top. When a new value arrives:

    1. Insert it. The heap now holds up to k + 1 values.
    2. If it holds more than k, remove the top. The smallest of k + 1 values cannot be among the k largest.
    3. Read the top: that is the k-th largest.

    The heap never holds more than k + 1 values, so each insert and each removal costs O(log k), and the object stores O(k) values, whatever the length of the stream.

    A small trace with k = 3 and the starting numbers [4, 5, 8, 2]: inserting 4, 5 and 8 fills the heap with three values, and the top is 4. Inserting 2 makes four values, so the smallest, 2, is removed. The heap holds 4, 5, 8, and its top, 4, is the 3rd largest. Right after construction the heap holds 3 values with top 4. After add(3) it still holds 3 values and the top is still 4: the 3 went in and straight out again.

    Step by step

    1. Store k as this.k. add needs it to know how many values to keep.
    2. Create this.largest as a new MinHeap from the algorithms library offered in the lesson, reached as algorithms.DataStructures.Heap.MinHeap. It holds the k largest values so far, smallest on top.
    3. Loop over nums with for (let num of nums). The starting values count like any other, and the same filter applies to them: each is kept only while it is among the k largest.
    4. Call this.add(num) inside the loop. add already keeps the heap at k values, so the constructor reuses it instead of repeating that work. The return value is ignored, because nobody has asked a question yet.
    5. In add, insert val into this.largest.
    6. Trim the heap. If this.largest.n, the number of values in the heap, is above this.k, call extract() to remove the smallest.
    7. Return this.largest.peek(). peek() reads the top and leaves it in the heap. Because the answer always exists, the heap holds exactly k values here, and its top is the k-th largest.

    The solution in JavaScript

    var algorithms = require('algorithms')
class KthLargest {
    constructor(k, nums) {
        this.k = k;
        this.largest = new algorithms.DataStructures.Heap.MinHeap();
        for (let num of nums) {
            this.add(num);
        }
    }

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

    A few JavaScript details:

    • The class and this. k and the heap are properties of each object, created in the constructor. Every KthLargest has its own heap, so two objects never interfere.
    • Calling a method from the constructor. this.add(num) works inside the constructor because this.k and this.largest are already set by then. Move the loop above those two lines and add would fail on an undefined heap.
    • n is a property, not a method. Write this.largest.n, with no parentheses. insert, extract and peek are methods.
    • for...of goes over the values of an array. for...in would give the indexes as strings.

    Complexity

    Time: each add is O(log k): one insert and at most one extract on a heap of at most k + 1 values, plus a constant-time peek. The constructor makes one add per starting number, so it takes O(m log k) for m starting numbers.

    Space: O(k). Values below the k-th largest are dropped as soon as they fall out of the top k, so the heap never grows with the stream.

    Edge cases and common mistakes

    • Equal values. With k = 4 and the numbers [7, 7, 7, 7, 8, 3], the heap ends up with the four values 7, 7, 7, 8 (the 3 never stays in), and the top is 7. Equal values are separate entries, so do not collapse them with a set.
    • Starting with no numbers. new KthLargest(1, []) gives an empty heap. The first add(-3) inserts one value, the size stays at k, and the answer is -3. Adding -2, -4, 0 and 4 returns -2, -2, 0, 4, which makes the full output -3 -2 -2 0 4.
    • Using a max-heap. A max-heap would put the largest value on top, which is not the one the question asks for. To read the k-th largest from the top, the heap must hold the k largest values with the smallest of them on top: a min-heap.
    • Removing before inserting. Insert first, then trim. The new value may be larger than the current top, in which case the old top is the one to remove, and only after the insert can you compare them.
    • Using >= instead of > in the size check. With >= the heap would shrink to k - 1 values and the top would be the (k-1)-th largest.
    • Sorting a plain array. [10, 9, 1].sort() without a comparator gives [1, 10, 9], because it compares as strings. If you ever sort numbers, pass (a, b) => b - a.

    Testing

    Outputs of the solution above:

    • new KthLargest(3, [4, 5, 8, 2]), then add(3), add(5), add(10), add(9), add(4) returns 4 5 5 8 8.
    • new KthLargest(1, []), then add(-3), add(-2), add(-4), add(0), add(4) returns -3 -2 -2 0 4.
    • new KthLargest(4, [7, 7, 7, 7, 8, 3]), then add(2), add(10), add(9), add(9) returns 7 7 7 8.
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free