kth Largest Element in an Array

Problem Statement

Given an integer k and an array of size n consisting of unique integers. Find the kth largest element in this array.

Examples

Input : 1

arr : [2,1,4,6,3,9,7]
k : 2

Output : 1

7

---

Input : 1

arr : [12,65,34,90]
k : 4

Output: 2

12

Explanation

• In the first example, we can see that $k=2$, so we have to find the second largest element in this array. If we rearrange the array in descending order $[9,7,6,4,3,2,1]$, we can see that the element 7 is in the second position, so it is considered the second largest element.
• In the second example, we can see that $k=4$, so we have to find the fourth largest element in this array. If we rearrange the array in descending order $[90,65,34,12]$, we can see that the element 12 is in the fourth position, so it is considered the fourth largest element.

Constraints

• $1 <=$ N $= 10^4$
• $1 <=$ arr[i] $<= 10^4$
• $1 <=$ K $<= N$

All the elements of the array are unique

Approach – 1 : Sorting

In this approach, we will use sorting. We will use the fact that in a sorted array the kth largest element will be present at the kth position from the end. The intuition behind this approach is that we will not require any extra space. So we will just sort the array and return the element arr[n-k].

Algorithm

• Sort the array using a built-in function in C++, Java, or Python
• Return arr[n-k].

C++ Implementation :

#include<bits/stdc++.h>
using namespace std;

int KthLargestElement(vector<int> arr,int n,int k){
    sort(arr.begin(),arr.end());  // sorting the array
        return arr[n-k];          // return kth largest element
}

int main(){
    vector<int> arr{2,1,4,6,3,9,7};
    int n = arr.size();
    int k = 2;
    int x = KthLargestElement(arr,n,k);
    cout<<"Kth largest element is "<<x;
    return 0;
}

Output :

Kth largest element is 7

---

Java Implementation :

public class Main {

  public static int KthLargestElement(int arr[], int n, int k) {
    Arrays.sort(arr); // sorting the array
    return arr[n - k]; // return kth largest element
  }

  public static void main(String[] args) {
    int arr[] = { 2, 1, 4, 6, 3, 9, 7 };
    int n = arr.length;
    int k = 2;
    int x = KthLargestElement(arr, n, k);
    System.out.print("Kth largest element is " + x);
  }
}

Output :

Kth largest element is 7

---

Python Implementation :

def KthLargestElement(arr, n, k):
    arr.sort()       # sorting the array
    return arr[n-k]  #return kth largest element

arr = [2,1,4,6,3,9,7]
n = len(arr)
k = 2
x = KthLargestElement(arr, n, k)
print("Kth largest element is ",x)

Output :

Kth largest element is 7

Complexity Analysis

Time Complexity :

• In this approach, we are sorting the array which takes $O(N*LogN)$ time complexity because built-in sorting methods use hybrid sort (which is the combination of 2-3 sorting algorithms from Quick sort, Merge sort, Insertion sort, and heap sort).

So the total worst-case time complexity for this approach to find the kth largest element in an array is $O(N*LogN)$

Space Complexity :

In this approach we are not using any space, so the space complexity of this approach is $O(1)$.

Time Complexity : $O(N*LogN)$

Space Complexity : $O(1)$

Approach – 2 : Using Min Heap

In this approach, we will use a Min Heap of size k and insert the k largest elements of the array into it. We will use the fact that if we put the k largest elements of the array in a min-heap, then the kth largest element will be present on the top of the min-heap, and we can easily return this element.

Note :
A Min Heap is a data structure that has the property that its topmost element is always the minimum element of the heap.

Algorithm

• Create a min-heap
• Run a loop from $i=0$ to $i=n-1$
• Push each element into the min-heap
• If at any point the size of the min-heap becomes greater than k, pop one element from the min-heap (this is because we have to only put k elements in the heap).
• After the loop is over, return the topmost element of the heap, because this is the kth largest element of the array.

C++ Implementation :

#include<bits/stdc++.h>
using namespace std;

int KthLargestElement(vector<int> arr,int n,int k){
    priority_queue<int,vector<int>,greater<int>> q;  // creating min-heap
    int i;
    for(i=0;i<n;i++){
        q.push(arr[i]);  // push every element into the heap
        if(q.size()>k)   // if the size of the heap becomes greater than k, pop the element
            q.pop();
    }
    return q.top();
}

int main(){
    vector<int> arr{2,1,4,6,3,9,7};
    int n = arr.size();
    int k = 2;
    int x = KthLargestElement(arr,n,k);
    cout<<"Kth largest element is "<<x;
    return 0;
}

Output :

Kth largest element is 7

---

Java Implementation :

public class Main {

  public static int KthLargestElement(int arr[], int n, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(); // creating min-heap
    int i;
    for (i = 0; i < n; i++) {
      q.add(arr[i]); // push every element into the heap
      if (q.size() > k) q.remove(q.peek()); // if the size of the heap becomes greater than k, pop the element
    }
    return q.peek();
  }

  public static void main(String[] args) {
    int arr[] = { 2, 1, 4, 6, 3, 9, 7 };
    int n = arr.length;
    int k = 2;
    int x = KthLargestElement(arr, n, k);
    System.out.print("Kth largest element is " + x);
  }
}

Output :

Kth largest element is 7

---

Python Implementation :

def KthLargestElement(arr, n, k):
    x = heapq.nlargest(k, arr)  # x will become an array of k largest elements
    return x[k-1]      # return kth largest element

arr = [2,1,4,6,3,9,7]
n = len(arr)
k = 2
x = KthLargestElement(arr, n, k)
print("Kth largest element is ",x)

Output :

Kth largest element is 7

Complexity Analysis

Time Complexity :

• In this approach, we are pushing k elements of the array into the heap, so the heap will take $O(LogK)$ time complexity for inserting one element.
  We are performing n operations by running a loop from i=0 to i=n-1 , so the average case time complexity for this approach will be $O(N) * O(LogK)$ = $O(NlogK)$ (as the heap size is k).
  But in the worst-case time complexity for k elements to be inserted in a heap can be $O(N) * O(LogN)$ = $O(N*LogN)$ (when k is equal to n).

So the time complexity for this approach to find the kth largest element in an array is $O(N) * O(LogK)$ = $O(N*LogK)$

Space Complexity :

In this approach we are using a heap to store every element, so the worst-case space complexity of this approach is $O(N)$.

Time Complexity : $O(N*LogK)$

Space Complexity : $O(N)$

Approach – 3 : Using QuickSelect

In this approach, we will use a concept similar to Quicksort.
In quicksort, we used a pivot element and a partition function to partition the array around the pivot element (elements lesser than the pivot come on the left side, and elements greater than the pivot come on the right side).
This approach also uses the pivot element and a partition function to find out the (n-k)th smallest element (because it is the same as finding the kth largest element in an array). And finally, we will return to this element.

Algorithm

• First, check if the size of the array is 1, then directly return arr[0]
• Create 3 variables $l = 0$, $h = n-1$ and target $= n-k$
• Run a while loop until $l <= h$, and perform the following steps
• Create a variable pivot and initialize it with the value returned by the partition function
• If pivot $<$ target, then do $l =$ pivot + 1
• Else if pivot $>$ target, do $h =$ pivot – 1
• Else return arr[pivot] (because this is equal to arr[n-k])
• Inside the partition function, perform the following steps
• Create two variables high = arr[h] and $x = l$
• Run a loop from $i = l$ to $i = h-1$
• if(arr[i] < high), then swap arr[x] with arr[i] and incremanet the value of x
• Afer th loop has ended, swap arr[x] with arr[h]

C++ Implementation :

#include<bits/stdc++.h>
using namespace std;
int partition(vector<int> &arr, int l, int h) {
  int high = arr[h];
  int x = l;
  for (int i=l;i<h;i++) {
    if (arr[i] < high) {   // If arr[i] is less than high, then swap arr[x] with arr[i]
      swap(arr[x], arr[i]);
      x++;
    }
  }
  swap(arr[x], arr[h]);  //swap arr[x] with arr[h]
  return x;
}
int KthLargestElement(vector<int> arr,int n,int k){
    if (n == 1) {
    return arr[0];
  }
  int l = 0;
  int h = n - 1;
  int target = n-k;
  while (l <= h) {
    int pivot = partition(arr, l, h);  // Initializing pivot with the value returned by partition function
    if (pivot < target) {        // If the pivot is less than the target, then we have to go to the right side
      l = pivot + 1;
    }
     else if (pivot > target) {  // If the pivot is greater than the target, then we have to go to the left side
      h = pivot - 1;
    }
     else {            // If the pivot is equal to the target, return arr[pivot]
      return arr[pivot];
    }
  }
    return -1;
}

int main(){
    vector<int> arr{2,1,4,6,3,9,7};
    int n = arr.size();
    int k = 2;
    int x = KthLargestElement(arr,n,k);
    cout<<"Kth largest element is "<<x;
    return 0;
}

Output :

Kth largest element is 7

---

Java Implementation :

public class Main {

  public static int partition(int arr[], int l, int h) {
    int high = arr[h];
    int x = l;
    for (int i = l; i < h; i++) {
      if (arr[i] < high) { // If arr[i] is less than high, then swap arr[x] with arr[i]
        int temp = arr[x];
        arr[x] = arr[i];
        arr[i] = temp;
        x++;
      }
    }
    int temp = arr[x]; //swap arr[x] with arr[h]
    arr[x] = arr[h];
    arr[h] = temp;
    return x;
  }

  public static int KthLargestElement(int arr[], int n, int k) {
    if (n == 1) return arr[0];
    int l = 0;
    int h = n - 1;
    int target = n - k;
    while (l <= h) {
      int pivot = partition(arr, l, h); // Initializing pivot with the value returned by partition function
      if (pivot < target) { // If the pivot is less than the target, then we have to go to the right side
        l = pivot + 1;
      } else if (pivot > target) { // If the pivot is greater than the target, then we have to go to the left side
        h = pivot - 1;
      } else { // If the pivot is equal to the target, return arr[pivot]
        return arr[pivot];
      }
    }
    return -1;
  }

  public static void main(String[] args) {
    int arr[] = { 2, 1, 4, 6, 3, 9, 7 };
    int n = arr.length;
    int k = 2;
    int x = KthLargestElement(arr, n, k);
    System.out.print("Kth largest element is " + x);
  }
}

Output :

Kth largest element is 7

---

Python Implementation :

def partition(arr,  l,  h):
    high = arr[h]
    x = l
    for i in range(l,h):
        if (arr[i] < high):   #If arr[i] is less than high, then swap arr[x] with arr[i]
            temp = arr[x]
            arr[x]=arr[i]
            arr[i]=temp
            x+=1
    temp = arr[x]           #swap arr[x] with arr[h]
    arr[x]=arr[h]
    arr[h]=temp
    return x

def KthLargestElement(arr, n, k):
    if (n == 1):
        return arr[0]
    l = 0
    h = n - 1
    target = n-k
    while (l <= h):
        pivot = partition(arr, l, h)  #Initializing pivot with the value returned by partition function
        if(pivot < target):    #If the pivot is less than the target, then we have to go to the right side
            l = pivot + 1;
        elif(pivot > target):  #If the pivot is greater than the target, then we have to go to the left side
            h = pivot - 1
        else:             #If the pivot is equal to the target, return arr[pivot]
            return arr[pivot]
    return -1

arr = [2,1,4,6,3,9,7]
n = len(arr)
k = 2
x = KthLargestElement(arr, n, k)
print("Kth largest element is ",x)

Output :

Kth largest element is 7

Complexity Analysis

Time Complexity :

• In this approach, we are performing at most n operations by running a while loop from $l = 0$ to $h = n-1$ where $l$ is the starting index (lower index) and $h$ is the ending index (higher index), which can take $O(N)$ time complexity in the worst case (when $l=0$ and $h=n-1$).
• Inside the while loop, we are calling the partition function, which is taking $O(N)$ time completely in the worst case because we are running a loop from $i = l$ to $i = h-1$.

So the total worst-case time complexity for this approach to find the kth largest element in an array where n is the size of the array is $O(N) * O(N)$ = $O(N*N)$

Space Complexity :

In this approach we are not using any space, so the space complexity for this approach is $O(1)$.

Time Complexity : $O(N*N)$

Space Complexity : $O(1)$

Approach – 4 : Using Max Heap

In this approach, we will use a Max Heap and insert each element of the array into the heap. We will use the fact that the largest element is present at the top of the max heap.
So if we pop out the first $k-1$ elements from the max heap, the topmost element popped in the heap is the kth largest element of the array.
The fact behind the logic is that if we push each element into the max heap, and then pop out $k-1$ elements from the heap, the $k-1$ popped elements are the $k-1$ largest elements of the array, and now the topmost elements of the heap are the kth largest element of the array.

Note :
A Max Heap is a data structure that has the property that its topmost element is always the maximum element of the heap.

Algorithm

• Create a max heap
• Run a loop from $i=0$ to $i=n-1$
• Push all the elements of the array into the heap
• Run a loop from $i=0$ to $i=k-2$ and each time pop an element from the heap
• Return the topmost element of the heap

C++ Implementation :

#include<bits/stdc++.h>
using namespace std;

int KthLargestElement(vector<int> arr,int n,int k){
    priority_queue<int> q;
    int i;
    for(i=0;i<n;i++){        // push each element into the heap
        q.push(arr[i]);
    }
    for(i=0;i<k-1;i++)
        q.pop();           // pop k-1 elements from heap
    return q.top();
}

int main(){
    vector<int> arr{2,1,4,6,3,9,7};
    int n = arr.size();
    int k = 2;
    int x = KthLargestElement(arr,n,k);
    cout<<"Kth largest element is "<<x;
    return 0;
}

Output :

Kth largest element is 7

---

Java Implementation :

public class Main {

  public static int KthLargestElement(int arr[], int n, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(
      Collections.reverseOrder()
    );
    int i;
    for (i = 0; i < n; i++) { // push each element into the heap
      q.add(arr[i]);
    }
    for (i = 0; i < k - 1; i++) {
      q.remove(q.peek()); // pop k-1 elements from heap
    }
    return q.peek();
  }

  public static void main(String[] args) {
    int arr[] = { 2, 1, 4, 6, 3, 9, 7 };
    int n = arr.length;
    int k = 2;
    int x = KthLargestElement(arr, n, k);
    System.out.print("Kth largest element is " + x);
  }
}

Output :

Kth largest element is 7

---

Python Implementation :

def KthLargestElement(arr, n, k):
    x = heapq.nlargest(k, arr)  # x will become an array of k largest elements
    return x[k-1]      # return kth largest element

arr = [2,1,4,6,3,9,7]
n = len(arr)
k = 2
x = KthLargestElement(arr, n, k)
print("Kth largest element is ",x)

Output :

Kth largest element is 7

Complexity Analysis

Time Complexity :

• In this approach, we are pushing n elements of the array into the heap, and the heap takes $O(LogN)$ time complexity for inserting an element, so for n elements, it will take $O(N*LogN)$ time complexity.

So the total worst-case time complexity for this approach to find the kth largest element in an array is $O(N) * O(logN)$ = $O(N*LogN)$

Space Complexity :

In this approach we are using a heap to store every element, so the worst-case space complexity of this approach is $O(N)$.

Time Complexity : $O(N*LogN)$

Space Complexity : $O(N)$

Approach – 5 : Using Standard Template Library

In this approach, we will be using the Standard Template Library to find the kth largest element in the array. Standard Template Library has a built-in function, which can help us to find the kth largest element.

In C++, we can use the function nth_element which is present in the \ header file in C++. It rearranges the elements such that the element at the nth position comes to its original place, as it will come after sorting.

In Java, we can use the Arrays.sort() method along with a little modification, we can use Collections.reverseOrder() method to reverse the sorting order, and then we can return arr[k-1]

In Python, we can use heapq.nlargest method to find the kth largest element in the array.

Algorithm

• Sort the array
• Return arr[n-k]

C++ Implementation :

#include<bits/stdc++.h>
using namespace std;

int KthLargestElement(vector<int> arr,int n,int k){
    nth_element(arr.begin(), arr.begin() + k - 1, arr.end(), greater<int>());  // the kth element will come to its original place
    return arr[k - 1];
}

int main(){
    vector<int> arr{2,1,4,6,3,9,7};
    int n = arr.size();
    int k = 2;
    int x = KthLargestElement(arr,n,k);
    cout<<"Kth largest element is "<<x;
    return 0;
}

Output :

Kth largest element is 7

---

Java Implementation :

public class Main {

  public static int KthLargestElement(Integer arr[], int n, int k) {
    Arrays.sort(arr, Collections.reverseOrder()); // sort array in reverse order
    return arr[k - 1];
  }

  public static void main(String[] args) {
    Integer arr[] = { 2, 1, 4, 6, 3, 9, 7 };
    int n = arr.length;
    int k = 2;
    int x = KthLargestElement(arr, n, k);
    System.out.print("Kth largest element is " + x);
  }
}

Output :

Kth largest element is 7

---

Python Implementation :

def KthLargestElement(arr, n, k):
    x = heapq.nlargest(k, arr)  # x will become an array of k largest elements
    return x[k-1]      # return kth largest element

arr = [2,1,4,6,3,9,7]
n = len(arr)
k = 2
x = KthLargestElement(arr, n, k)
print("Kth largest element is ",x)

Output :

Kth largest element is 7

Complexity Analysis

Time Complexity :

• The time complexity of C++ will be $O(N)$ in the worst case.
• The time complexity of Java will be $O(NlogN)$, as we are using the built-in sort function which uses hybrid sort (which is the combination of 2-3 sorting algorithms from Quick sort, Merge sort, Insertion sort, and heap sort).
• The time complexity of Python will be $O(NLogN)$, as we are using a heap, and heap takes $O(LogN)$ time complexity to insert an element, and we are having n elements.

Space Complexity :

• In this approach we are not using any space, so the space complexity of this approach is $O(1)$.

Time Complexity : $O(N)$ for C++, $O(NlogN)$ for Java and Python

Space Complexity : $O(1)$

Conclusion

In this quick tutorial, we have discussed 5 different approaches for finding the kth largest element in an array.

• The easiest approach was approach 1, in which we just sorted the array and returned arr[n-k].
• One of the most efficient approaches was approach 2 because we used a min-heap of size k, which will take O(NlogK) time complexity on average.

FAQs

Q.What is the Efficient Approach to Find the Kth Smallest Element?

A. The most efficient approach for finding the kth smallest element is by using a Max Heap.

Just like we used a min-heap to find the kth largest element in $O(NLogK)$ time complexity, we can find the kth smallest element in an array.

We will insert k smallest elements in the min-heap, and now the topmost element of the heap will be the kth smallest element of the array.