Kth Largest Element in a Stream

Leetcode Problem 703: Kth Largest Element in a Stream

Problem Summary

Design a class KthLargest that, given an integer k and an initial list of values, maintains a running data stream and always returns the k-th largest value after each new integer is added. The k-th largest is the k-th element when all values seen so far are sorted in descending order.

Implement:

• KthLargest(int k, int[] nums) — initializes with k and a seed list.
• int add(int val) — adds val to the stream and returns the current k-th largest value.

Constraints:

• The initial list can be empty or contain up to 10,000 elements.
• k is at least 1 and at most the initial list size plus one.
• All values (initial and added) are in the range [−10,000, 10,000].
• At most 10,000 calls will be made to add.

k=3,  initial nums = [4, 5, 8, 2]

Initial sorted desc: [8, 5, 4, 2]   → 3rd largest = 4

add(3):  desc [8, 5, 4, 3, 2]        → 3rd largest = 4
add(5):  desc [8, 5, 5, 4, 3, 2]     → 3rd largest = 5
add(10): desc [10, 8, 5, 5, 4, 3, 2] → 3rd largest = 5
add(9):  desc [10, 9, 8, 5, 5, 4, ...] → 3rd largest = 8

Output: [4, 5, 5, 8, 8]

Techniques

• Tree
• Design
• Binary Search Tree
• Heap (Priority Queue)
• Binary Tree
• Data Stream

Solution

import { Heap } from "../heap";
  
class KthLargest {
    private minHeap = new Heap<number>((a, b) => a - b);

    constructor(
        private readonly k: number, 
        nums: number[]
    ) {
        for (const num of nums) {
            this.addToHeap(num, k)
        }
    }

    add(val: number): number {
        this.addToHeap(val, this.k)
        return this.minHeap.peek()!
    }

    private addToHeap(num: number, k: number) {
        this.minHeap.insert(num)

        if (this.minHeap.size() > k) {
            this.minHeap.extract()
        }        
    }
}