Kth Largest Element in an Array

In this article, we will learn how to find the kth largest element in an array. We will see various approaches to finding the kth largest element in an array with the time and space complexity of each approach. We will also see a dry run to solve the problem.

What is the kth largest element in an array?

Let’s see an example to understand what is the kth largest element in an array.

Example:

Let’s find 3rd largest element in the above array.

3rd largest element in the array = 64 ( 1st = 94, 2nd = 75 )

Let’s see a few other largest elements in the above array.

5th largest element in the array = 45

7th largest element in the array = 22

How to find the kth largest element in an array?

Let’s see different approaches to finding the kth largest element in an array.

Approach 1: Sorting

Below are the steps to find the kth largest element in an array using the sorting method,

• Sort the array into descending order
• The kth largest element will be arr[k-1] because of 0-based indexing.
• The kth smallest element will be arr[n-k] where n is the length of an array.
• If the array is sorted into ascending order then,
• The kth largest element will be arr[n-k]
• The kth smallest element will be arr[k-1]

Let’s understand this approach to find the kth largest element in an array with an example.

In the above example, if k=3 then the 3rd largest element will be 64. If k=4 then the 4th largest element will be 61.

Now, let’s see how to write a program to find the kth largest element in an array.

# Python program to find kth largest element in an array

def kthSmallest(arr, N, K):

    # Sort the given array in descending order
    arr.sort(reverse=True)

    # Return k'th element in the
    # sorted array
    return arr[K-1]


# Driver code
if __name__ == '__main__':
    arr = [30, 15, 75, 7, 94, 45, 64, 22, 61]
    N = len(arr)
    K = 3

    print("The kth smallest element in an array: ",
        kthSmallest(arr, N, K))

Output:

The kth largest element in an array:  64

*Time Complexity: O(nlogn)* where n is the size of an array, we are sorting the array which takes nlogn time.

Space Complexity: O(1) as we are not using any extra space.

Approach 2: Heap

In this approach, we will use max-heap to find the kth largest element in an array. We know that the first element of the max-heap is always the largest one. So, we will remove k-1 elements from the max-heap and now the largest element present in the max-heap is our answer. Let’s see a dry run of this approach to understand it better.

In the above image, we can see that we have inserted all the elements into the max-heap and all the elements are in sorted order.

Now, we will extract the first k-1 elements from the max-heap.

Now, 3rd largest element is 64 here.

# python program to find kth largest element in an array using max-heap

from heapq import heappush,heappop

arr=[30, 15, 75, 7, 94, 45, 64, 22, 61]
K=3

# create heap
heap=[]
n=len(arr)

# insert all elements into heap
for i in range(n):
    # by default heap is mean heap so we will make element negative to perform max heap
    heappush(heap,-1*arr[i])

# remove first k-1 max elements from the heap
for i in range(K-1):
    heappop(heap)
    
ans=-heappop(heap)

print("The kth largest element in an array is:",ans)

Output:

The kth largest element in an array is: 64

*Time Complexity: O(k+(n-k)log(k))** where n is the size of an array

Space Complexity: O(k)

Approach 3: Quickselect Algorithm

In this approach, we will use the technique of the quicksort algorithm to find the kth largest element in an array. Below are steps to find the kth largest element in an array using the quickselect algorithm.

• First, choose any random position as a pivot position.
• Now, use the partition algorithm to split the array into two halves and find the correct position of the pivot.
• In the partition algorithm, all the elements are compared with the pivot, elements that are less than the pivot will be shifted to the left of the pivot, and elements that are greater than the pivot will be shifted to the right of the pivot.
• After performing the partition algorithm, all the elements left to the pivot are smaller than it, and all the elements right to the pivot are greater than it.
• Compare the index of pivot to (n-k) where n is the size of an array.
• If the index matches then return the answer otherwise find other partition recursively.

# python program to find kth largest element in an array using quickselect

def kthLargest(arr, K):
    left=0
    right=len(arr)-1
    ans=0
    
    while(True):
        index=partition(arr,left,right)
        if index==K-1:
            ans=arr[index]
            break
        if index<K-1:
            left=index+1
        else:
            right=index-1
    return ans
    
    
def partition(arr, left, right):
    
    pivot=arr[left]
    l=left+1
    r=right
    
    while(l<=r):
        if arr[l]<pivot and arr[r]>pivot:
            arr[l],arr[r]=arr[r],arr[l]
            l+=1
            r-=1
        if arr[l]>=pivot:
            l+=1
        if arr[r]<=pivot:
            r-=1
    arr[left],arr[r]=arr[r],arr[left]
    return r

arr = [30, 15, 75, 7, 94, 45, 64, 22, 61]
N = len(arr)
K = 3
print("The kth largest element in an array is:",
        kthLargest(arr, K))

Output:

The kth largest element in an array is: 64

Time Complexity: Average time complexity O(n) Worst time complexity O(n^2)

Space Complexity: O(1)

FAQs

1. How to sort an array in reverse order in various languages?
Python: arr.sort(reverse = True)
Java: Arrays.sort(arr, Collections.reverseOrder())
C++: arr.sort(arr, arr+n, greater< int>())

2. How to initialize heap data structure in different languages?
Python: heapq.heapify(heap)
Java: PriorityQueue< Integer> pQueue = new PriorityQueue< Integer>()
C++: priority_queue< int> pq;

3. What is the best technique to find the kth largest element in an array?
Out of the above-mentioned techniques using heap is the best technique to find the kth largest element in an array because it always provides the guarantee that the algorithm will work in O(n*long) time.