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 Kth Smallest or Largest element in an Array.

Objec­tive: Find Kth Small­est or Largest ele­ment in an Array

Exam­ple:

int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 };
Output: The 4th smallest element is : 8

Approach:

Naive Approach: Use Sort­ing

Sort the array and return kth ele­ment. Time Com­plex­ity — O(nlogn).

Bet­ter Approach: Use Quick Sort Tech­nique

Here we are find­ing the kth small­est ele­ment in array. Same approach you can apply to find the kth largest element.

  • In this tech­nique we select a pivot ele­ment and after a one round of oper­a­tion the pivot ele­ment takes its cor­rect place in the array.
  • Once that is done we check if the pivot ele­ment is the kth ele­ment in array, if yes then return it.
  • But if pivot ele­ment is less than the kth ele­ment, that clearly means that the kth ele­ment is on the right side of the pivot. So make a recur­sive call from pivot+1 to end.
  • Sim­i­larly if pivot ele­ment is greater than the kth ele­ment, that clearly means that the kth ele­ment is on the left side of the pivot. So make a recur­sive call from start to pivot-1.

Aver­age Time Com­plex­ity : O(n)

NOTE: Instead of print­ing the kth ele­ment, you can print all ele­ments from index 0 to k and this will the solu­tion of the prob­lemPrint First K small­est or largest ele­ments in an array”.

Com­plete Code:

Out­put:

The 4th smallest element is : 8

You may also like...