Find the Kth Largest Element in Array

Link will be apear in 15 seconds.

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

Given an array we need to find the Kth largest element in Array.

Find Kth Largest Element in Array

Code:

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

public class FindKthLargestValue {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
        }

        int k = s.nextInt();

        findKthLargestBySort(arr, k);
        findKthLargestByMaxHeap(arr, k);
        findKthLargestByMinHeap(arr, k);

    }

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

        System.out.println(arr[arr.length - k]);
    }

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

        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(MinHeap)  O(klogk)+O(n-k)*O(logn)(for heapify)
    private static void findKthLargestByMinHeap(int[] arr, int k) {
        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();

        //Suppose k=3 Now insert first three element of arr in pq.        //Now the root element is the third largest in the pq.        //Loop again from k to size of array        //If the value at the root is smaller than the value in array that means the root element is no longer the        //3rd largest element so therefore remove the root element and insert arr element now again root have the 3rd largest 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());
    }
}