## DEV Community is a community of 853,399 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # 🏁Kth Max and Min Element in the array🏁

Question:
Given an array arr[ ] and a number K where K is smaller than size of array, the task is to find the Kth smallest and largest element in the given array. It is given that all array elements are distinct.

Example 1:

``````Input:N = 6
arr[] = 7 10 4 3 20 15
K = 3
Output : 7
Explanation :3rd smallest element in the given
array is 7.
``````

Logic:

1. Sorting Technique:
• Take the array and sort it in ascending order. ( Using inbuilt or curtomized function )
• the kth smallest element will be arr [ k - 1 ];
• the kth largest element will be arr [ arr.length - k ];
2. Max Heap and Min heap:
• For Min Heap : Take the array and " k " as inputs ( because it passed to the function as shown below)
• declare Priority queue ( which heapifies the array in ascending order )
• add all the elements in the array to the heap ( heap.add( ) as shown below)
• pop the elements in the heap for " k - 1 " times (heap.poll( ) as shown below)
• now the peek of the heap will be the kth smallest element (heap.peek( ) as shown below)
• return heap.peek( )
• For Max Heap : Take the array and " k " as inputs ( because it passed to the function as shown below)
• declare Priority queue but this time in reverse order by ( Collections.reverseOrder( ) as shown below)
• add all the elements in the array to the heap ( heap.add( ) as shown below)
• pop the elements in the heap for " k - 1 " times (heap.poll( ) as shown below)
• now the peek of the heap will be the kth smallest element (heap.peek( ) as shown below)
• return heap.peek( )
``````import java.util.*;

public class Solution{

public static int minHeap(int[] arr, int k){
PriorityQueue<Integer> heap = new PriorityQueue<>();//By default it stores in ascending order
int min = 0;
for(int i = 0; i < arr.length; i++){//adds the array elements to the priority queue/ heap
}
for(int i = 1; i < k; i++){// removing peek element k-1 times to get the answer
heap.poll();
}
min = heap.peek();
return min;
}

public static int maxHeap(int[] arr, int k){
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());//We force is to store in descending order
int max = 0;
for(int i = 0; i < arr.length; i++){//adds the array elements to the priority queue/ heap
}
for(int i = 1; i < k; i++){
heap.poll(); // removing peek element k-1 times to get the answer
}
max = heap.peek();
return max;
}

public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int sortingArr[] = new int[n];
int heapArr[] = new int[n];
for(int i = 0 ; i < sortingArr.length; i++){
sortingArr[i] = sc.nextInt();
heapArr[i] = sortingArr[i];
}
int k = sc.nextInt();

//This is solution using sorting technique
Arrays.sort(sortingArr);
System.out.println("The kth smallest element through sorting is: "+sortingArr[k - 1]);
System.out.println("The kth largest element throught sorting  is: "+sortingArr[sortingArr.length - k]);

//This is solution using Max heap and Min heap
System.out.println("The kth smallest element through heaps is: "+minHeap(heapArr,k));
System.out.println("The kth largest element through heaps is: "+maxHeap(heapArr,k));
}
}
``````