DSA & System Design

Kth Largest Element in a Stream

EasyHeaps: Top-K, K-way Merge and Two Heaps

A leaderboard receives scores one at a time, and after every new score it must show the score in kth place: the kth largest value among all scores received so far.

Implement the class KthLargest:

  • new KthLargest(k, nums) sets k and loads the scores already known, nums (possibly empty).
  • add(val) records the new score val and returns the kth largest score among everything stored so far.

Duplicates count separately: in [8, 8, 3] the 2nd largest value is 8. Each call to add leaves at least k scores stored (counting val itself), so the answer always exists.

JavaScript has no built-in priority queue. Write your own small heap inside your solution.

Constraints

  • 1 <= k <= 10^4
  • 0 <= nums.length <= 10^4
  • -10^4 <= nums[i], val <= 10^4
  • At most 10^4 calls to add.

Examples

Example 1

Input: ["KthLargest","add","add","add","add","add"]
       [[3,[7,1,9,4]],[5],[2],[8],[10],[6]]
Output: [null,5,5,7,8,8]

k = 3. After adding 5 the values are 9, 7, 5, 4, 1, so the 3rd largest is 5. Adding 2 changes nothing at the top. After 8 the top three are 9, 8, 7; after 10 they are 10, 9, 8; 6 is too small to enter.

Example 2

Input: ["KthLargest","add","add","add","add","add"]
       [[1,[]],[-3],[-5],[0],[0],[-1]]
Output: [null,-3,-3,0,0,0]

With k = 1 the answer is simply the largest value so far. The class starts empty; duplicates count, so the second 0 keeps the answer at 0.

Example 3

Input: ["KthLargest","add","add","add","add"]
       [[2,[5]],[3],[8],[6],[1]]
Output: [null,3,5,6,6]

The constructor gets fewer than k values. After adding 3 there are exactly two (5 and 3), so the 2nd largest is 3. Then 8 arrives: the top two are 8 and 5.

Each test creates the class with the first operation, then calls the methods in order. Output lists what each call returns; null marks the constructor and methods that return nothing, and their return values aren't checked.

JavaScript you'll use: Heaps and priority queues Classes for data structures

// JavaScript has no built-in heap: write a small one (push, pop, peek, size) above this class.

class KthLargest {
  /**
   * @param {number} k
   * @param {number[]} nums the values seen before the first add
   */
  constructor(k, nums) {
    
  }

  /**
   * Adds val to the stream.
   * @param {number} val
   * @return {number} the kth largest value seen so far
   */
  add(val) {
    
  }
}

Ctrl/⌘ + ' runs the examples, Ctrl/⌘ + Enter submits. Use console.log freely: output shows under Console. In the editor, press Esc then Tab to move focus out.