Medium

# 86. Find Kth Smallest or Largest element in an Array

Objective: Find Kth Smallest or Largest element in an Array

Example:

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

Approach:

Naive Approach: Use Sorting

Sort the array and return the kth element. Time Complexity - O(nlogn).

Better Approach: Use Quick Sort Technique

Here we are finding the kth smallest element in the array. The same approach you can apply to find the kth largest element.

• In this technique, we select a pivot element and after one round of operation, the pivot element takes its correct place in the array.
• Once that is done we check if the pivot element is the kth element in the array, if yes then return it.
• But if the pivot element is less than the kth element, that means that the kth element is on the right side of the pivot. So make a recursive call from pivot+1 to end.
• Similarly, if the pivot element is greater than the kth element, that means that the kth element is on the left side of the pivot. So make a recursive call from start to pivot-1.

Average Time Complexity: O(n)

NOTE: Instead of printing the kth element, you can print all elements from index 0 to k and this will be the solution of the problem "Print First K smallest or largest elements in an array".

Output:

```The 4th smallest element is : 8
```