# 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 kth element. Time Complexity – O(nlogn).

Better Approach: Use Quick Sort Technique

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

• In this technique we select a pivot element and after a 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 array, if yes then return it.
• But if pivot element is less than the kth element, that clearly 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 pivot element is greater than the kth element, that clearly 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 the solution of the problemPrint First K smallest or largest elements in an array”.

Complete Code:

 public class KthSmallestElement { public int findkthSmallestElement(int[] arrA, int k) { k = k – 1; // since array index starts with 0 return kSmall(arrA, 0, arrA.length – 1, k); } public int kSmall(int[] arrA, int start, int end, int k) { int left = start; int right = end; int pivot = start; while (left <= right) { while (left <= right && arrA[left] <= arrA[pivot]) left++; while (left <= right && arrA[right] >= arrA[pivot]) right—; if (left < right) { swap(arrA, left, right); left++; right—; } } swap(arrA, pivot, right); if (pivot == k) return arrA[pivot];// if pivot is kth element , return else if (pivot < k) // if pivot is less than k, then kth element will be on the right return kSmall(arrA, pivot + 1, end, k); else // if pivot is greater than k, then kth element will be on the right return kSmall(arrA, start, pivot – 1, k); } public void swap(int[] arrA, int a, int b) { int x = arrA[a]; arrA[a] = arrA[b]; arrA[b] = x; } public static void main(String args[]) { int[] arrA = { 2, 3, 11, 16, 27, 4, 15, 9, 8 }; KthSmallestElement k = new KthSmallestElement(); int a = 4; int x = k.findkthSmallestElement(arrA, a); System.out.print("The " + a + "th smallest element is : " + x); } }

Output:

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