In this problem, we have to return the kth largest element in an unsorted array. Note that the array can have duplicates. So, we have to find the Kth largest element in the sorted order, not the distinct Kth largest element.
Table of Contents
Example
A = {4 , 2 , 5 , 3 , 1}
K = 24
A = {7 , 2 , 6 , 4 , 3 , 5}
K = 44
Approach(Sorting array)
This approach is straight-forward. Sort the whole array. And you are now able to tell any largest element in the array. But, it is sufficient enough for us to just find the Kth largest element. That is why we can come up with a better approach.
Algorithm
- Sort the array
- Access the Kth largest element from the back of the array
- Print the answer
Implementation of algorithm to find Kth largest element in an unsorted array
C++ Program
#include <bits/stdc++.h>
using namespace std;
int KthLargest(vector <int> &a , int &k)
{
int n = a.size();
//kth largest = element on (n - k) index
sort(a.begin() , a.end());
return a[n - k];
}
int main()
{
vector <int> a = {4 , 2 , 5 , 3 , 1};
int k = 2;
cout << KthLargest(a , k) << '\n';
}
Java Program
import java.util.Arrays;
class Kth_largest
{
public static int KthLargest(int[] a, int k)
{
int n = a.length;
Arrays.sort(a);
return a[n - k];
}
public static void main(String args[])
{
int a[] = {4 , 2 , 5 , 3 , 1} , k = 2;
System.out.println(KthLargest(a , k));
}
}
4
Complexity Analysis of finding Kth largest element in an unsorted array
Time Complexity
O(NlogN), as we need to sort the array. N = Size of the array
Space complexity
O(1), as we use constant space. Note: sort() function can use O(N) memory. But that is not always the case.
Approach(Quick Select)
As we discussed in our previous approach, we just need to find the kth largest element in the array. In a simpler way, we need the (n – k + 1)th smallest element in the array. Talking about sort, we can think of quicksort, which has a similar approach. In quicksort, while choosing a pivot, we ensure that it gets to its correct index in the array after the partition.
What if, we did a similar partitioning until the (n – k) th index gets its correct value. This is what we are going to do in this approach:
Choose some random pivot and partition the array around it. If it gets to the index we desire(n – k). Then, this is the Kth largest element. Otherwise, we know that the required index lies either to the left of it or to right of it. We can then call the partition() function in the corresponding subarray to find the required index, and therefore, its value.
But, is the above approach certainly better than the sorting one? We know that the worst case of quicksort occurs when we pick the smallest/greatest element as our pivot as in that case,
T(N) = T(N – 1) + O(1)
and the subproblem is almost the same as the problem, causing O(N * N) time complexity. Similarly, our partition function can make such calls. In order to resolve this, we will ensure that we choose a random pivot at every point of partitioning.
Algorithm
- Create a quickSelect() function that returns the (N – K)th “smallest” element
- Create a partition() helper function which will return the correct index of any randomly chosen pivot
- Now, till we reach the point where partition() returns the index equal to ‘K‘:
- call partition() on a random pivot
- If pivot index returned is same as K
- return the pivot element
- Else If pivot index returned is less than K
- call partition() on right subarray of the pivot index
- Else If pivot index returned is more than K
- call partition() on left subarray of the pivot index
- Now that quickSelect() has returned the (N – K) th index, print the result
Implementation of algorithm to find Kth largest element in an unsorted array
C++ Program
#include <bits/stdc++.h>
using namespace std;
int partition(int &l , int &r , vector <int> &a)
{
int rnd = (rand() % (r - l + 1)) + l;
swap(a[rnd] , a[r]);
int idx = l;
for(int i = l ; i < r ; i++)
{
if(a[i] < a[r])
{
swap(a[i] , a[idx]);
idx++;
}
}
swap(a[idx] , a[r]);
return idx;
}
int quickSelect(int l , int r , int k , vector <int> &a)
{
while(l <= r)
{
int pivotIdx = partition(l , r , a);
if(pivotIdx == k)
return a[pivotIdx];
if(pivotIdx < k)
l = pivotIdx + 1;
else
r = pivotIdx - 1;
}
return -1;
}
int KthLargest(vector <int> &a , int &k)
{
int n = a.size();
//kth largest = element on (n - k) index
return quickSelect(0 , n - 1 , n - k , a);
}
int main()
{
vector <int> a = {4 , 2 , 5 , 3 , 1};
int k = 2;
cout << KthLargest(a , k) << '\n';
}
Java Program
import java.util.Random;
class Kth_largest
{
static void swap(int x , int y , int [] a)
{
int temp = a[y];
a[y] = a[x];
a[x] = temp;
return;
}
static int partition(int l , int r , int [] a)
{
Random rndObject = new Random();
int rnd = rndObject.nextInt(r - l + 1) + l , idx = l;
swap(rnd , r , a);
for(int i = l ; i < r ; i++)
{
if(a[i] < a[r])
{
swap(i , idx , a);
idx++;
}
}
swap(idx , r , a);
return idx;
}
static int quickSelect(int l , int r , int k , int [] a)
{
while(l <= r)
{
int pivotIdx = partition(l , r , a);
if(pivotIdx == k)
return a[pivotIdx];
if(pivotIdx < k)
l = pivotIdx + 1;
else
r = pivotIdx - 1;
}
return -1;
}
public static int KthLargest(int[] a, int k)
{
int n = a.length;
return quickSelect(0 , n - 1 , n - k , a);
}
public static void main(String args[])
{
int a[] = {4 , 2 , 5 , 3 , 1} , k = 2;
System.out.println(KthLargest(a , k));
}
}
4
Complexity Analysis of finding Kth largest element in an unsorted array
Time Complexity
The recurrence relation can be expressed as(N = size of the array):
T(N) = T(N / 2) + O(N – 1)
Because we expect that a randomly chosen pivot divided the array into two halves. Based on it, the complexity can be roughly estimated as T(N) = 2N – logN = ~O(N).
So, the algorithm is linear. However, in the worst case, when the random pivots selected are all largest/smallest in the array, Time Complexity becomes O(N*N). But in a large-sized array, it is very less probable to happen.
Space complexity
O(1), as only constant space is used.