Kth Largest Element in an Array

Last Updated on August 21, 2023 by Mayank Dham

The objective is to identify the Kth largest item within an array. It’s important to recognize that this problem is slightly more complex than simply locating the largest or smallest element in the array. Here, ‘K’ signifies the size of the array’s set of values.

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)

Conclusion
In conclusion, determining the Kth largest element within an array involves leveraging techniques such as max-heap data structures. This approach allows us to efficiently identify the desired element by iteratively removing k-1 elements from the max-heap. By understanding the mechanics of this method and its underlying principles, we can effectively solve the problem of finding the Kth largest element in an array.

Frequently Asked Questions (FAQs) related to Kth largest element in an array

Below are some FAQs related the kth largest element in an array:

1. What is the significance of finding the Kth largest element in an array?
Finding the Kth largest element is crucial in various scenarios, such as data analysis, sorting algorithms, and optimizing algorithms that require prioritizing items based on their magnitude.

2. How is the problem of finding the Kth largest element different from finding the largest element?
While finding the largest element involves identifying a single maximum value, finding the Kth largest element entails determining the element that would be ranked Kth if the array were sorted in descending order.

3. Why is a max-heap employed to solve the Kth largest element problem?
A max-heap efficiently maintains the largest element at the root, simplifying the process of removing elements in descending order of magnitude. This property makes it an effective choice for solving the Kth largest element problem.

4. Are there alternative methods for solving the Kth largest element problem?
Yes, there are alternative approaches, such as sorting the array in descending order and directly accessing the Kth element. However, this method has a higher time complexity compared to using data structures like max-heaps.

5. What is the time complexity of the max-heap approach for finding the Kth largest element?
The time complexity is O(n + k log n), where n is the size of the array and k is the desired rank. This is more efficient than sorting the entire array when k is much smaller than n.