Welcome to Subscribe On Youtube

703. Kth Largest Element in a Stream

Description

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Implement KthLargest class:

  • KthLargest(int k, int[] nums) Initializes the object with the integer k and the stream of integers nums.
  • int add(int val) Appends the integer val to the stream and returns the element representing the kth largest element in the stream.

 

Example 1:

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

Explanation
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

 

Constraints:

  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • At most 104 calls will be made to add.
  • It is guaranteed that there will be at least k elements in the array when you search for the kth element.

Solutions

  • class KthLargest {
        private PriorityQueue<Integer> q;
        private int size;
    
        public KthLargest(int k, int[] nums) {
            q = new PriorityQueue<>(k);
            size = k;
            for (int num : nums) {
                add(num);
            }
        }
    
        public int add(int val) {
            q.offer(val);
            if (q.size() > size) {
                q.poll();
            }
            return q.peek();
        }
    }
    
    /**
     * Your KthLargest object will be instantiated and called as such:
     * KthLargest obj = new KthLargest(k, nums);
     * int param_1 = obj.add(val);
     */
    
  • class KthLargest {
    public:
        priority_queue<int, vector<int>, greater<int>> q;
        int size;
    
        KthLargest(int k, vector<int>& nums) {
            size = k;
            for (int num : nums) add(num);
        }
    
        int add(int val) {
            q.push(val);
            if (q.size() > size) q.pop();
            return q.top();
        }
    };
    
    /**
     * Your KthLargest object will be instantiated and called as such:
     * KthLargest* obj = new KthLargest(k, nums);
     * int param_1 = obj->add(val);
     */
    
  • class KthLargest:
        def __init__(self, k: int, nums: List[int]):
            self.q = []
            self.size = k
            for num in nums:
                self.add(num)
    
        def add(self, val: int) -> int:
            heappush(self.q, val)
            if len(self.q) > self.size:
                heappop(self.q)
            return self.q[0]
    
    
    # Your KthLargest object will be instantiated and called as such:
    # obj = KthLargest(k, nums)
    # param_1 = obj.add(val)
    
    
  • type KthLargest struct {
    	h *IntHeap
    	k int
    }
    
    func Constructor(k int, nums []int) KthLargest {
    	h := &IntHeap{}
    	heap.Init(h)
    	for _, v := range nums {
    		heap.Push(h, v)
    	}
    
    	for h.Len() > k {
    		heap.Pop(h)
    	}
    
    	return KthLargest{
    		h: h,
    		k: k,
    	}
    }
    
    func (this *KthLargest) Add(val int) int {
    	heap.Push(this.h, val)
    	for this.h.Len() > this.k {
    		heap.Pop(this.h)
    	}
    
    	return this.h.Top()
    }
    
    func connectSticks(sticks []int) int {
    	h := IntHeap(sticks)
    	heap.Init(&h)
    	res := 0
    	for h.Len() > 1 {
    		val := heap.Pop(&h).(int)
    		val += heap.Pop(&h).(int)
    		res += val
    		heap.Push(&h, val)
    	}
    	return res
    }
    
    type IntHeap []int
    
    func (h IntHeap) Len() int           { return len(h) }
    func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
    func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
    func (h *IntHeap) Push(x any) {
    	*h = append(*h, x.(int))
    }
    func (h *IntHeap) Pop() any {
    	old := *h
    	n := len(old)
    	x := old[n-1]
    	*h = old[0 : n-1]
    	return x
    }
    
    func (h *IntHeap) Top() int {
    	if (*h).Len() == 0 {
    		return 0
    	}
    
    	return (*h)[0]
    }
    
    /**
     * Your KthLargest object will be instantiated and called as such:
     * obj := Constructor(k, nums);
     * param_1 := obj.Add(val);
     */
    
  • /**
     * @param {number} k
     * @param {number[]} nums
     */
    var KthLargest = function (k, nums) {
        this.k = k;
        this.heap = new MinHeap();
        for (let num of nums) {
            this.add(num);
        }
    };
    
    /**
     * @param {number} val
     * @return {number}
     */
    KthLargest.prototype.add = function (val) {
        this.heap.offer(val);
        if (this.heap.size() > this.k) {
            this.heap.poll();
        }
        return this.heap.peek();
    };
    
    class MinHeap {
        constructor(data = []) {
            this.data = data;
            this.comparator = (a, b) => a - b;
            this.heapify();
        }
    
        heapify() {
            if (this.size() < 2) return;
            for (let i = 1; i < this.size(); i++) {
                this.bubbleUp(i);
            }
        }
    
        peek() {
            if (this.size() === 0) return null;
            return this.data[0];
        }
    
        offer(value) {
            this.data.push(value);
            this.bubbleUp(this.size() - 1);
        }
    
        poll() {
            if (this.size() === 0) {
                return null;
            }
            const result = this.data[0];
            const last = this.data.pop();
            if (this.size() !== 0) {
                this.data[0] = last;
                this.bubbleDown(0);
            }
            return result;
        }
    
        bubbleUp(index) {
            while (index > 0) {
                const parentIndex = (index - 1) >> 1;
                if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
                    this.swap(index, parentIndex);
                    index = parentIndex;
                } else {
                    break;
                }
            }
        }
    
        bubbleDown(index) {
            const lastIndex = this.size() - 1;
            while (true) {
                const leftIndex = index * 2 + 1;
                const rightIndex = index * 2 + 2;
                let findIndex = index;
                if (
                    leftIndex <= lastIndex &&
                    this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
                ) {
                    findIndex = leftIndex;
                }
                if (
                    rightIndex <= lastIndex &&
                    this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
                ) {
                    findIndex = rightIndex;
                }
                if (index !== findIndex) {
                    this.swap(index, findIndex);
                    index = findIndex;
                } else {
                    break;
                }
            }
        }
    
        swap(index1, index2) {
            [this.data[index1], this.data[index2]] = [this.data[index2], this.data[index1]];
        }
    
        size() {
            return this.data.length;
        }
    }
    
    /**
     * Your KthLargest object will be instantiated and called as such:
     * var obj = new KthLargest(k, nums)
     * var param_1 = obj.add(val)
     */
    
    
  • class KthLargest {
        #pq = new MinPriorityQueue();
        #k = 0;
    
        constructor(k: number, nums: number[]) {
            this.#k = k;
            for (const x of nums) {
                this.#pq.enqueue(x);
                if (this.#pq.size() > k) {
                    this.#pq.dequeue();
                }
            }
        }
    
        add(val: number): number {
            this.#pq.enqueue(val);
            if (this.#pq.size() > this.#k) {
                this.#pq.dequeue();
            }
            return this.#pq.front().element;
        }
    }
    
    /**
     * Your KthLargest object will be instantiated and called as such:
     * var obj = new KthLargest(k, nums)
     * var param_1 = obj.add(val)
     */
    
    

All Problems

All Solutions