Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Find the Kth Smallest/Largest Element in an Array

Objec­tive: Given an array of inte­gers. find the Kth Smallest/largest ele­ment 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 Small­est Element)

  • Use min-Heap. (Click here to read about Pri­or­ity Queue).
  • Insert all the ele­ments in the Pri­or­ity Queue.
  • Extract K ele­ments from the pri­or­ity queue. The last ele­ment (kth) extracted with be the kth small­est ele­ment in the array.

Com­plete Code:

Output:
4th smallest element:10

Note: For kth largest ele­ment, imple­ment pri­or­ity queue for max-Heap.

You may also like...

  • Kamal Chaya

    Is it faster to use hte quick­s­e­lect algorithm ?

  • eugen_nw

    It is also pos­si­ble to just sort the input array in ascend­ing 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 pri­or­ity queue or quick sort (i.e. par­ti­tion only k times) and pivot will land in its cor­rect position.