Posts Kth Largest Element in a Stream
Post
Cancel

Kth Largest Element in a Stream

Problem 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.

leetcode

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class KthLargest {
    
    PriorityQueue<Integer> pq;
    int size;

    public KthLargest(int k, int[] nums) {
        
        this.size=k;
        
        pq = new PriorityQueue<>();
        
        for(int i=0; i<nums.length; i++) pq.add(nums[i]);
        
        while(pq.size() > k) pq.poll();
        
    }
    
    public int add(int val) {
        
        pq.add(val);
        
        if(pq.size() > size)
            pq.poll();
        
        return pq.peek();
        
    }
}
This post is licensed under CC BY 4.0 by the author.