Find the Kth Smallest Element in Array

Link will be apear in 15 seconds.

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

Find the Kth Smallest Element in Array.

Ex: int arr[]={2,3,6,5,10,45};
      int k=3;
Output: 5

Find the Kth Smallest Element in Array.

Code:

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

public class FindKthSmallestElement {
    public static void main(String[] args) {
        int arr[]={10,7,11,5,27,2,9,45};
        findKthSmallestBySort(arr,4);
        findKthSmallestByMinHeap(arr,4);
        findKthSmallestByMaxHeap(arr,4);
    }


    //Method 1: Sort the value  O(nlogn)    private static void findKthSmallestBySort(int[] arr, int k) {
        Arrays.sort(arr);

        System.out.println(arr[k-1]);
    }
    //Using Priority Queue(MinHeap)  O(logn)+O(k-1)*O(logn)(for heapify)    private static void findKthSmallestByMinHeap(int[] arr, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int value : arr) {
            pq.add(value);
        }

        for (int i = 0; i < k - 1; i++) {
            pq.poll();
        }

        System.out.println(pq.peek());
    }

    //Using Priority Queue(MaxHeap)  O(logk)+O(n-k)*O(logn)(for heapify)
    private static void findKthSmallestByMaxHeap(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(Collections.reverseOrder());

        //Suppose k=3 Now insert first three element of arr in pq.        //Now the root element is the third smallest in the pq.        //Loop again from k to size of array        //If the value at the root is greater than the value in array that means the root element is no longer the        //3rd smallest element so therefore remove the root element and insert arr element now again root have the 3rd smallest value.        //Print root value

        for (int i = 0; i < k; i++) {
            priorityQueue.add(arr[i]);
        }

        for (int i = k; i < arr.length; i++) {
            if(priorityQueue.peek()>arr[i])
            {
                priorityQueue.poll();
                priorityQueue.add(arr[i]);
            }
        }

        System.out.println(priorityQueue.peek());
    }
}