Find the Kth Smallest/Largest Element in an Array

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


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:

4th smallest element:10

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

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

  • Kamal Chaya

    Is it faster to use hte quickselect algorithm ?

  • eugen_nw

    It is also possible to just sort the input array in ascending order and pick the k-1th element.

    • dogbert82

      That will take O(n) time. Idea here is to not sort the entire array. We can use priority queue or quick sort (i.e. partition only k times) and pivot will land in its correct position.

      • gau246

        Why not just use Arrays.sort() and pick the k-1 th element?

%d bloggers like this: