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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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