Solution For Kth Largest Element In A Stream

Problem Statement:

The kth largest element in a stream is the kth largest element that appears in an infinite stream (i.e., a stream of integers that are not finite and are not predetermined). Implement the KthLargest class:

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

Solution:

We can use a max heap to store the k largest elements seen so far in the stream. We initialize our heap with the first k elements of the stream, and then for every new element, we compare it with the root of our heap (which is the largest element seen so far), if the new element is smaller than the root of the heap, we can discard it since it cannot be one of the k largest elements in the stream. However, if the new element is larger than the root of the heap (i.e., it potentially could be one of the k largest elements in the stream), we add it to the heap and remove the smallest element in the heap since it has been replaced by a larger element. The kth largest element in the stream is always the root of the heap.

Algorithm:

1. Initialize an empty max heap of size k.
2. Add the first k elements of the stream to the max heap.
3. For every new element x in the stream:
   a. If x is smaller than or equal to the root of the heap, ignore it.
   b. If x is larger than the root of the heap, add it to the heap and remove the smallest element in the heap.
4. The kth largest element in the stream is the root of the heap.

Time Complexity:

Adding an element to a heap takes O(log k) time, and we perform this operation for every element in the stream, so the total time complexity is O(n log k), where n is the length of the stream.

Space Complexity:

We are using a max heap of size k to store the k largest elements seen so far in the stream, so the space complexity is O(k).

Code:

class KthLargest {
PriorityQueue pq;
int k;
public KthLargest(int k, int[] nums) {
this.k = k;
pq = new PriorityQueue<>(k);
for (int num : nums) {
add(num);
}
}
public int add(int val) {
if (pq.size() < k) {
pq.offer(val);
} else if (pq.peek() < val) {
pq.poll();
pq.offer(val);
}
return pq.peek();
}
}

Step by Step Implementation For Kth Largest Element In A Stream

import java.util.*; 

class KthLargest { 

    int k; 
    PriorityQueue pq; 

    public KthLargest(int k, int[] a) { 
        this.k = k; 
        pq = new PriorityQueue<>(k); 

        for (int n : a) 
            add(n); 
    } 

    public int add(int n) { 

        if (pq.size() < k) 
            pq.offer(n); 

        else if (pq.peek() < n) { 
            pq.poll(); 
            pq.offer(n); 
        } 

        return pq.peek(); 
    } 
}

# Python3 program to find k'th largest 
# element in stream 
  
# Function to insert heap 
# elements 
def insertHeap(heap, n, k): 
      
    # Base case 
    if n < k: 
        heap.append(n) 
        return
  
    # If new number is less than 
    # root, replace root 
    if n > heap[0]: 
        heap[0] = n 
  
    # Call heapify on root element 
    heapify(heap, k, 0) 
  
# A recursive method to heapify a 
# subtree with the root at given 
# index. This method assumes that 
# the subtrees are already heapified 
def heapify(heap, k, i): 
    n = len(heap) 
    largest = i 
    l = 2 * i + 1      # left = 2*i + 1 
    r = 2 * i + 2      # right = 2*i + 2 
  
    # See if left child of root exists 
    # and is greater than root 
    if l < n and heap[i] < heap[l]: 
        largest = l 
  
    # See if right child of root exists 
    # and is greater than the largest 
    # so far 
    if r < n and heap[largest] < heap[r]: 
        largest = r 
  
    # Change root, if needed 
    if largest != i: 
        heap[i], heap[largest] = heap[largest], heap[i]  # swap 
  
        # Heapify the root. 
        heapify(heap, k, largest) 
  
# Function to print k largest 
# numbers in a stream 
def kLargest(arr, k): 
      
    # Insert first k elements into a max heap 
    heap = arr[:k] 
    k = len(heap) 
  
    # Build a max heap 
    for i in range(k, 0, -1): 
        heapify(heap, k, i) 
  
    # Process remaining elements 
    for i in range(k, len(arr)): 
        insertHeap(heap, arr[i], k) 
  
    # Print heap 
    print(heap) 
  
# Driver Code 
if __name__ == '__main__': 
    arr = [1, 5, 17, 10, 25, 8] 
    k = 3
    kLargest(arr, k)

var kthLargest = function(k, nums) {
    // sort the array in reverse order
    nums.sort((a, b) => b - a);
    // return the kth element
    return nums[k - 1];
};

class KthLargest {
public:
    KthLargest(int k, vector& nums) {
        size = k;
        for(int i : nums) {
            add(i);
        }
    }
    
    int add(int val) {
        if(pq.size() < size) {
            pq.push(val);
        }
        else if(val > pq.top()) {
            pq.pop();
            pq.push(val);
        }
        return pq.top();
    }
    
    int getKth() {
        return pq.top();
    }
    
private:
    int size;
    priority_queue, greater> pq;
};

public class KthLargest
{
    public int K { get; set; }
    public List Numbers { get; set; }

    public KthLargest(int k, int[] nums)
    {
        this.K = k;
        this.Numbers = new List(nums);
    }

    public int Add(int val)
    {
        this.Numbers.Add(val);
        this.Numbers.Sort();
        return this.Numbers[this.Numbers.Count - this.K];
    }
}