Find Kth smallest element in the stream of number

Link will be apear in 15 seconds.

Well done! you have successfully gained access to Decrypted Link.

Find Kth smallest element in the stream of number?

Ex:
array=[10,7,11,5,27,2,9,45]
k=3

Output: -1 -1 11 10 10 7 7 7

Find Kth smallest element in the stream of number

Code:

import java.util.Collections;
import java.util.PriorityQueue;

public class FindKthSmallestInStream {
    public static void main(String[] args) {
        int arr[]={10,7,11,5,27,2,9,45};
        findKthSmallestInStreamByMaxHeap(arr,3);
    }

    private static void findKthSmallestInStreamByMaxHeap(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(Collections.reverseOrder());

        //First put k value in the Max Heap.
        for (int i = 0; i < k; i++) {
            priorityQueue.add(arr[i]);

        }

        //For first k-1 value, there is no kth smallest element in stream therefore it prints "-1"        for (int i = 0; i < k - 1; i++) {
            System.out.println("-1");
        }
        //After k value has been inserted into Max Heap The root value is Kth smallest.        System.out.println(priorityQueue.peek());

        //Now loop over from k to array size.        for (int i = k; i < arr.length; i++) {
            //If the root value is greater than array element we remove the root value and then put the array element in the heap.            //After that print the root value            if(priorityQueue.peek()>arr[i])
            {
                priorityQueue.poll();
                priorityQueue.add(arr[i]);
                System.out.println(priorityQueue.peek());
            }
            //Else we simply print the value as the value is smaller in root as compared to array element            //Therefore still the smallest Kth value is root value.            else            {
                System.out.println(priorityQueue.peek());
            }
        }

        
    }
}

Time Complexity: O(k)*O(logk)+O(n-k)*O(log(n-k))