DEV Community

loading...
Cover image for 🏁Kth Max and Min Element in the array🏁

🏁Kth Max and Min Element in the array🏁

kaiwalyakoparkar profile image Kaiwalya Koparkar ・2 min read

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.
Enter fullscreen mode Exit fullscreen mode

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
            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));
    }
}
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

Forem Open with the Forem app