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 problem “Print First K smallest or largest elements in an array”.
Complete Code:
Output:
The 4th smallest element is : 8
