Find kth largest element in an array
Introduction
The Kth largest element in an array is the element that would appear in the Kth position if the array were sorted in descending order. This problem is significant in scenarios where ranking or ordering elements is crucial, such as in financial analysis or data analytics.
When dealing with arrays, one common task is to find Kth largest element in an array. This page provides an in-depth guide to understanding and implementing algorithms for finding the Kth largest element in an array.
Understanding Kth largest element in an array
The ‘Kth largest element in an array‘ refers to the element that would occupy the Kth position if the array were sorted in descending order.
- In other words, it is the Kth largest value among all the elements in the array.
- The value of K is a positive integer, and it represents the position or rank of the element in the sorted order.
Example :
Example 1:
Input: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3], K = 3
Output: 5
Explanation:
Consider the array: [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]. If we were to find the 3rd largest element in this array, we would sort it in descending order: [9, 6, 5, 5, 4, 3, 3, 2, 1, 1]. The element at the 3rd position is 5, so in this case, the 3rd largest element in the original array is 5.
Approaches to find kth largest element in an array
There are mainly three approaches to find kth largest element in an array :
- Naive Approach
- Optimized Algorithm
- Using Standard Library Templates
Naive Approach
1. Using Sorting
One naive approach involves sorting the array in descending order and then selecting the kth element. While this works, the time complexity is typically O(n log n), where n is the size of the array.
def kth_largest_sorting(arr, k):
# Sort the array in descending order
arr.sort(reverse=True)
# Return the kth largest element
return arr[k - 1]
# Example usage:
my_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
k_value = 3
result = kth_largest_sorting(my_array, k_value)
print("The " + str(k_value) + "th largest element is: " + str(result))
Output :
The 3rd largest element is: 5
Explanation :
The Python program finds the 3rd largest element in the array [3, 1, 4, 1, 5, 9, 2, 6, 5, 3] using sorting. It sorts the array in descending order, and the 3rd largest element, 5, is printed.
2. Using Max Heap
Another naive approach is to use a max heap to keep track of the largest elements. This also has a time complexity of O(n log k), where k is the value of K.
import heapq
def kth_largest_max_heap(arr, k):
# Create a max heap
max_heap = [-num for num in arr]
heapq.heapify(max_heap)
# Pop k-1 elements from the heap
for _ in range(k - 1):
heapq.heappop(max_heap)
# Return the kth largest element (negate the result)
return -heapq.heappop(max_heap)
# Example usage:
my_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
k_value = 3
result = kth_largest_max_heap(my_array, k_value)
print("The " + str(k_value) + "th largest element is: " + str(result))
Output :
The 3rd largest element is: 5
Explanation :
This Python program utilizes a Max Heap to find the 3rd largest element in the array [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]. The array is transformed into a max heap with negative values, using the heapq module. After removing the k-1 smallest elements from the heap, the kth largest element is obtained by negating the result.
Optimized Algorithms
1. Using Quick Select Algorithm
QuickSelect is a popular algorithm for finding the Kth element in an unordered list. It is a variation of the quicksort algorithm and has an average time complexity of O(n).
import random
def partition(arr, low, high):
pivot_index = random.randint(low, high)
arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] >= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_select(arr, low, high, k):
while low <= high:
pivot_index = partition(arr, low, high)
if pivot_index == k - 1:
return arr[pivot_index]
elif pivot_index < k - 1:
low = pivot_index + 1
else:
high = pivot_index - 1
# Example usage:
my_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
k_value = 3
result = quick_select(my_array, 0, len(my_array) - 1, k_value)
print("The " + str(k_value) + "th largest element is: " + str(result))
Output :
The 3rd largest element is: 5
Explanation :
This Python program implements the QuickSelect algorithm to find the 3rd largest element in the array [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]. The “partition” function selects a random pivot and rearranges array elements. The “quick_select” function recursively determines the kth largest element by adjusting the search range based on the pivot.
2. Using Min Heap with Priority Queue
Using a min heap with a priority queue is an efficient approach, especially when dealing with streaming data. It allows constant-time retrieval of the current Kth largest element.
import heapq
def kth_largest_min_heap(arr, k):
# Create a min heap
min_heap = arr[:k]
heapq.heapify(min_heap)
# Iterate through the remaining elements
for num in arr[k:]:
if num > min_heap[0]:
heapq.heappop(min_heap)
heapq.heappush(min_heap, num)
# Return the smallest element in the heap (kth largest overall)
return min_heap[0]
# Example usage:
my_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
k_value = 3
result = kth_largest_min_heap(my_array, k_value)
print("The " + str(k_value) + "th largest element is: " + str(result))
Output :
The 3rd largest element is: 5
Explanation :
This Python program uses a Min Heap with Priority Queue to find the 3rd largest element in the array [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]. Initially, the heap is populated with the first k elements, and then it is updated by iteratively comparing and replacing elements. The smallest element in the heap after processing all array elements represents the kth largest element.
Using Standard Library Template
To find the Kth largest element in an array using the Python standard library, you can leverage the “heapq” module to create a Max Heap. Here’s an example:
import heapq
def kth_largest_standard_library(arr, k):
# Convert the array into a Max Heap
max_heap = [-num for num in arr]
heapq.heapify(max_heap)
# Extract the Kth largest element
kth_largest = heapq.nlargest(k, max_heap)[-1]
return -kth_largest
# Example usage:
my_array = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
k_value = 3
result = kth_largest_standard_library(my_array, k_value)
print("The " + str(k_value) + "th largest element is: " + str(result))
Output :
The 3rd largest element is: 5
Explanation :
In this program, heapq is used to create a Max Heap from the array, and heapq.nlargest is employed to extract the K largest elements. The Kth largest element is then determined as the last element in the list of K largest elements.
Practical Applications to find Kth largest element in an array
Following are the practical application :
To wrap it up:
In conclusion, the quest to find the Kth largest element in an array unveils a spectrum of algorithms and techniques crucial for efficient programming. From naive methods like sorting and using heaps to advanced algorithms like QuickSelect, each approach caters to distinct scenarios.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment