Others
Find kth Smallest and Largest Element in an Array in C++
Here’s a great article from The Crazy Programmer
Hello everyone, in this post we are going to go through a very popular and recently asked coding question.
Finding the kth smallest and largest element in an array.
From the problem statement, it is clear that the main task is to find the kth smallest or largest element in an unsorted array.
You cannot loop the array and try to find the solution as we do for the minimum or maximum element as in the case of the kth element it is difficult to keep track of the number of elements before any particular element.
Method 1: By Sorting Array
If the array is sorted then it is easy to find the kth smallest or largest element. Fetching arr[k-1] will give us the kth smallest and fetching arr[n-k] will give us the kth largest element, as we just need to find kth element from start and end. We can simply, therefore, sort the array and find the element. Below is the code illustration of the same.
#include <bits/stdc++.h>
using namespace std;
int main() {
int k = 5, n=12;
vector<int> arr = {5,9,1,4,6,7,8,2,0,4,-5,-3};
sort(arr.begin(), arr.end());
cout<<"kth smallest: "<<arr[k-1]<<endl;
cout<<"kth largest: "<<arr[n-k]<<endl;
}
Output:
kth smallest: 2
kth largest: 5
The time complexity for the above approach is O(nlogn) because of sorting cost and space complexity is O(1). If the array order is to be maintained then a copy of the array is required on which sorting can be done, in the case space complexity will be O(n).
Method 2: Using Max and Min Heap
Max-heap: Every element with size k will have a parent greater than both of the child nodes. So a max heap of size k will hold the greatest element at the root node and all the other small elements will be ancestors of that node.
The idea to find kth smallest element:
First, build a max heap with the first k elements, now the heap root node will hold the largest of all k elements.
Iterate through the rest of the elements.
If the current element is greater than the root node then that element need not be included as we already have k small elements so this element won’t add value in our final answer.
If the current element is smaller than the root node then the greatest element i.e. root node element can be removed from the heap as now we have other k small elements than the root node element. So just replace the root node element with the new element and call heapify at the root node so the Heap can be rearranged accordingly.
Here is an illustration of the same with code:
#include <bits/stdc++.h>
using namespace std;
void maxHeapify(vector<int> &arr, int i, int k) {
int largest = i;
if(2*i+1 < k && arr[2*i+1] > arr[i])
largest = 2*i + 1;
if(2*i+2 < k && arr[2*i+2] > arr[largest])
largest = 2*i + 2;
if(largest != i) {
swap(arr[i], arr[largest]);
maxHeapify(arr, largest, k);
}
return ;
}
void buildHeap(vector<int> &arr, int k) {
int i = (k-1)/2;
while(i>=0) {
maxHeapify(arr,i,k);
i--;
}
return;
}
int kthsmallest(vector<int> &arr, int k) {
buildHeap(arr,k);
for(int i=k;i<arr.size();i++) {
if(arr[i]<arr[0]) {
swap(arr[i],arr[0]);
maxHeapify(arr,0,k);
}
}
return arr[0];
}
int main() {
int k = 5;
vector<int> arr = {5,9,1,4,6,7,8,2,0,4,-5,-3};
sort(arr.begin(), arr.end());
cout<<"Kth smallest: "<<kthsmallest(arr,k);
}
Output:
Kth smallest: 2
The time complexity for the building of Heap is O(k) and for checking for remaining n-k elements its O(logn) per element as maxHeapify cost O(logn) so the overall complexity becomes O(k + (n-k)logn). This method is used widely to find the kth smallest element. Using a Min heap instead of the max heap can similarly be used to find kth largest element as below:
#include <bits/stdc++.h>
using namespace std;
void minHeapify(vector<int> &arr, int i, int k) {
int smallest = i;
if(2*i+1 < k && arr[2*i+1] < arr[i])
smallest = 2*i + 1;
if(2*i+2 < k && arr[2*i+2] < arr[smallest])
smallest = 2*i + 2;
if(smallest != i) {
swap(arr[i], arr[smallest]);
minHeapify(arr, smallest, k);
}
return ;
}
void buildHeap(vector<int> &arr, int k) {
int i = (k-1)/2;
while(i>=0) {
minHeapify(arr,i,k);
i--;
}
return;
}
int kthlargest(vector<int> &arr, int k) {
buildHeap(arr,k);
for(int i=k;i<arr.size();i++) {
if(arr[i]>arr[0]) {
swap(arr[i],arr[0]);
minHeapify(arr,0,k);
}
}
return arr[0];
}
int main() {
int k = 6;
vector<int> arr = {5,9,1,4,6,7,8,2,0,4,-5,-3};
sort(arr.begin(), arr.end());
cout<<"Kth largest: "<<kthlargest(arr,k);
}
Output:
Kth largest: 4
The time complexity for this remains the same as explained earlier.
Method 3: Quick Sort Variation
While doing a quick sort on an array we select a pivot element and all the elements smaller than that particular element are swapped to the left of the pivot and all the elements greater are swapped to the right of the pivot.
While trying to find kth smallest element, the interesting thing that can be observed is if the partitioning of the array is done based on the pivot, there can arise three conditions
- Index of the pivot is k i.e there are k-1 smaller elements to the left of pivot and others are no right (not necessarily sorted) and so the kth element is the pivot and we return it as an answer.
- Index of the pivot is greater than k i.e. there are more than k smaller elements to the left and therefore we need not sort the right side of the array and need to call the sort function only on the left side.
- Index of the pivot is less than k i.e. there are less than k elements on the left side (say l) and therefore we need not sort the left side and can now find the (k-l)th smallest element on the right side. l elements are subtracted because we already have l elements on the left side of the array.
Below is the implementation of the above logic:
#include <bits/stdc++.h>
using namespace std;
// Partioning is done same as for Quick Sort
int partition(vector<int> &arr, int l, int r) {
int pivot=arr[r], idx = l;
for(int i=l;i<r;i++) {
if(arr[i] <= pivot) {
swap(arr[i], arr[idx]); // Swap element lesser than pivot to left
idx++;
}
}
swap(arr[idx],arr[r]); // Set pivot at right position
return idx;
}
int kthsmallest(vector<int> &arr,int l,int r, int k) {
int p = partition(arr,l,r);
if(p==k) // First Condition
return arr[k];
else if(p>k) // Second Condition
return kthsmallest(arr,l,p-1,k);
else // Third Condition. As l-1 element will already be subtracted in previous calls from k
return kthsmallest(arr,p+1,r,k-p+l-1); // therefore its added after subtracting p again
}
int main() {
int k = 5;
vector<int> arr = {5,9,1,4,6,7,8,2,0,4,-5,-3};
sort(arr.begin(), arr.end());
cout<<"Kth smallest: "<<kthsmallest(arr,0,arr.size()-1,k-1);
}
Output:
Kth smallest: 2
The time complexity of the above code in the worst case would be O(n2) and the worst case will occur if the elements are sorted in descending order and k = n.
For ex. 6 5 4 3 2 1 and we have to find the 6th largest element. This is the same as for Quick sort as we always have to query the right side n times.
But average case time complexity for the above algorithm is O(n) as partitioning is a linear operation and there are less number of recursive calls. This method is widely used in practical implementations. By doing some smart selections and some pre-computations on the array the worst case time complexity for the above code can be brought down to O(n).
The post Find kth Smallest and Largest Element in an Array in C++ appeared first on The Crazy Programmer.