# Kth largest element in an Array Leetcode Solutions  Difficulty Level Medium
algorithms Array coding Divide and Conquer Heap Interview interviewprep LeetCode LeetCodeSolutions

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.

## Example  ```A = {4 , 2 , 5 , 3 , 1}
K = 2```
`4`
```A = {7 , 2 , 6 , 4 , 3 , 5}
K = 4```
`4`

## 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

1. Sort the array
2. Access the Kth largest element from the back of the array

### 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

Minimum Value to Get Positive Step by Step Sum Leetcode Solution

#### 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.

Kruskal Algorithm

### Algorithm

1. Create a quickSelect() function that returns the (N – K)th “smallest” element
2. Create a partition() helper function which will return the correct index of any randomly chosen pivot
3. 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
4. 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):