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...

• dheeraj sing­hal

after line swap(arrA, pivot, right), ele­ment at index ‘right’ will be at cor­rect posi­tion not ele­ment at pivot index.
Code need lit­tle mod­i­fi­ca­tion as men­tioned below.

if (right == k)
return arrA[right];
else if (right < k)
return kSmall(arrA, right + 1, end, k);
else
return kSmall(arrA, start, right — 1, k);