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:
- 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 ];
- 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
heap.add(arr[i]);
}
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
heap.add(arr[i]);
}
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));
}
}
Top comments (0)