Find the Kth Smallest/Largest Element in an Array

by

Objective: Given an array of integers. find the Kth Smallest/largest element in the array.

Example:

int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 };

K=4. 4th smallest element in given array: 10

Approach: (Kth Smallest Element)

  • Use min-Heap. (Click here to read about Priority Queue).
  • Insert all the elements in the Priority Queue.
  • Extract K elements from the priority queue. The last element (kth) extracted with be the kth smallest element in the array.

Complete Code:

import java.util.PriorityQueue;
public class KthSmallestElementInArray {
public static int find(int [] A, int k){
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for(int i=0;i<A.length;i++){
pq.offer(A[i]);
}
int n = –1;
while(k>0){
n = pq.poll();
k—;
}
return n;
}
public static void main(String[] args) {
int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 };
int k = 4;
System.out.println("4th smallest element:" + find(A,4));
}
}

view raw
KthSmallestElementInArray.java
hosted with ❤ by GitHub 

Output:
4th smallest element:10

Note: For kth largest element, implement priority queue for max-Heap.

Related Posts: