# 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) {
}
}
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)
}

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:
heap = 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) {
}
}

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);
}