Do you think IIT Guwahati certified course can help you in your career?
Introduction
Arrays are one of the simplest Data Structures which are also one of the most important ones. Operations on arrays is an important area to master when it comes to programming. Finding the kth largest element in an array is one such frequently asked coding question in coding interviews. This problem has multiple approaches as to how to solve it here in this blog we are going to discuss this problem in detail and provide you with a clear understanding of the problem.
What is Kth largest element in an array?
Finding the Kth largest element in an array involves determining the value that occupies the Kth position when the array is sorted in descending order. This can be achieved using various algorithms such as sorting the array and then accessing the Kth element, using a max-heap, or implementing quickselect algorithm for optimal performance.
Understanding the problem
The given task is to find the Kth largest element in an array. Here we must note that the question is one level higher compared to finding the largest or the smallest element in an array. In this task, ‘K’ refers to the cardinality of array values.
For example, you have to find the 4th largest element in the array given below:-
int arr[4] = {12, 34, 56, 2, 18, 21};
The 4th largest element in this array is 18. The kth largest element is simply the element at the (k-1)th index from left if you sorted this array in a non-increasing order as follows:-
{56, 34, 21, 18, 12, 2}; //the element at the (4-1)th index from left is the 4th largest in this array.
In the next section, you will learn about the brute force approach to solving this problem along with it's time and space complexity.
Brute Force Approach: Sorting the Array Using Bubble Sort
The brute force way of solving this problem is first to sort the array in non-increasing order so that the first largest element comes at the 0th index, the second largest element comes at the 1st index, and similarly, the kth largest element occupies the (k-1)th index.
Implementation in C++
C++
C++
#include <bits/stdc++.h> using namespace std;
void bubbleSort(vector<int>& nums){ int n = nums.size();
for (int i = 0; i < n - 1; ++i) { bool no_swap = true; for (int j = 0; j < n - i - 1; ++j) { if (nums[j] < nums[j + 1]) { swap(nums[j], nums[j + 1]); no_swap = false; } }
if(no_swap) return;/* array is now sorted, further iterations are not needed */ } }
int kthLargest(vector<int>&nums, int k){ if(k>nums.size()) return -1;/* return some flag for edge case */
bubbleSort(nums);
return nums[k-1]; }
int main() { vector<int> nums = {5, 6, 7, 10, 11, 15, 21, 32, 14}; int k = 4;
cout<<k<<"th largest element: "<<kthLargest(nums, k); }
You can also try this code with Online C++ Compiler
Best Case:O(N) We have used the optimized version of bubble sort which terminates early if no swaps occur in the inner loop, this occurs when the array is sorted, and further iterations are not needed. In the case, where the input is sorted, the outer loop runs once, and the inner loop performs N iterations, thus the best case time complexity will be O(N).
Worst Case:O(N2) The worst case occurs when the array is sorted in the reverse order, for eg. if you want to sort it in ascending, it is sorted in descending and vice versa. The inner loop runs N times, and the outer loop runs N times as well, so the time complexity becomes O(N2).
Space Complexity: O(1)
Additional memory is not required by the algorithm, it only uses the input array.
Implementation in Java
Java
Java
import java.util.Arrays;
public class KthLargestElement {
static void bubbleSort(int[] nums) { int n = nums.length;
for (int i = 0; i < n - 1; ++i) { boolean noSwap = true; for (int j = 0; j < n - i - 1; ++j) { if (nums[j] < nums[j + 1]) { // Swapping elements int temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; noSwap = false; } }
if (noSwap) return; // Array is now sorted, further iterations are not needed } }
static int kthLargest(int[] nums, int k) { if (k > nums.length) return -1; // Return some flag for edge case
bubbleSort(nums);
return nums[k - 1]; }
public static void main(String[] args) { int[] nums = {5, 6, 7, 10, 11, 15, 21, 32, 14}; int k = 4;
for i in range(n - 1): no_swap = True for j in range(n - i - 1): if nums[j] < nums[j + 1]: # Swapping elements nums[j], nums[j + 1] = nums[j + 1], nums[j] no_swap = False
if no_swap: return # Array is now sorted, further iterations are not needed
def kth_largest(nums, k): if k > len(nums): return -1 # Return some flag for edge case
bubble_sort(nums)
return nums[k - 1]
if __name__ == "__main__": nums = [5, 6, 7, 10, 11, 15, 21, 32, 14] k = 4
print(f"{k}th largest element: {kth_largest(nums, k)}")
You can also try this code with Online Python Compiler
The quickselect algorithm is a popular method to find the Kth largest element in an unsorted array. It has an average time complexity of O(n), making it more efficient than sorting the array using the sort function in cases where we need to find the Kth largest element multiple times or when the array is very large.
The algorithm works by selecting a pivot element, partitioning the array into elements smaller than and greater than the pivot, and recursively repeating this process on the subarray that contains the Kth largest element until the pivot element is the Kth largest element.
Now let’s see the implementation of quick select.
Implementation in C++
C++
C++
#include <bits/stdc++.h> using namespace std;
int partition(vector<int>& arr, int left, int right) { int pivot = arr[right]; /* Choose the rightmost element as the pivot */ int i = left - 1;
for (int j = left; j < right; j++) { if (arr[j] <= pivot) { swap(arr[++i], arr[j]); } }
swap(arr[i + 1], arr[right]); return i + 1; }
int quickSelect(vector<int>& arr, int left, int right, int k) { if (left == right) /* Base case: Only one element */ return arr[left];
int pivotIndex = partition(arr, left, right);
// Check the position of the pivot element if (pivotIndex == k) return arr[pivotIndex]; else if (pivotIndex > k) return quickSelect(arr, left, pivotIndex - 1, k); else return quickSelect(arr, pivotIndex + 1, right, k); }
int kthLargest(vector<int>&nums, int k){ if(k>nums.size()) return -1;/* return some flag for edge case */ return quickSelect(nums, 0, nums.size() - 1, nums.size() - k); }
int main() { vector<int> nums = {5, 6, 7, 10, 11, 15, 21, 32, 14}; int k = 4;
cout<<k<<"th largest element: "<<kthLargest(nums, k); }
You can also try this code with Online C++ Compiler
Here, the worst-case time complexity is O(N2). Similar to the quick sort algorithm, the worst case occurs when the array is sorted in increasing order and you have to find the 1st largest element.
Space Complexity: O(N)
This algorithm requires stack memory. In the worst case, the longest recursive depth is N.
Implementation in Java
Java
Java
import java.util.Arrays; import java.util.List;
public class KthLargestElement {
static int partition(List<Integer> arr, int left, int right) { int pivot = arr.get(right); // Choose the rightmost element as the pivot int i = left - 1;
for (int j = left; j < right; j++) { if (arr.get(j) <= pivot) { // Swap elements int temp = arr.get(++i); arr.set(i, arr.get(j)); arr.set(j, temp); } }
// Swap pivot to its correct position int temp = arr.get(i + 1); arr.set(i + 1, arr.get(right)); arr.set(right, temp);
return i + 1; }
static int quickSelect(List<Integer> arr, int left, int right, int k) { if (left == right) // Base case: Only one element return arr.get(left);
int pivotIndex = partition(arr, left, right);
// Check the position of the pivot element if (pivotIndex == k) return arr.get(pivotIndex); else if (pivotIndex > k) return quickSelect(arr, left, pivotIndex - 1, k); else return quickSelect(arr, pivotIndex + 1, right, k); }
public static void main(String[] args) { List<Integer> nums = Arrays.asList(5, 6, 7, 10, 11, 15, 21, 32, 14); int k = 4;
A max-heap stores the largest element at the topmost node. In order to find the kth largest element, you can insert all the elements in the array into a max-heap and pop the max element k-1 times. After that, the topmost element in the heap will be the kth largest element.
Implementation in C++
C++
C++
#include <bits/stdc++.h> using namespace std;
int kthLargest(vector<int>&nums, int k){ if(k>nums.size()) return -1;/* return some flag for edge case */ priority_queue<int> pq; /* initialize max-heap */
for(auto &num: nums){ pq.push(num); }
k = k-1;
while(k--){ /* pop k-1 times */ pq.pop(); }
return pq.top(); } int main() { vector<int> nums = {5, 6, 7, 10, 11, 15, 21, 32, 14}; int k = 4;
cout<<k<<"th largest element: "<<kthLargest(nums, k); }
You can also try this code with Online C++ Compiler
The array of size N is traversed once, and at each step, an element is inserted to a max-heap which has maximum size N (insertion takes log(size of the heap)).
Space Complexity: O(N)
Additional space is used by the max-heap, all the N elements are inserted into it.
This approach involves using a min-heap while limiting the maximum elements it can store to K.
The idea is to iterate through the array and insert each element to the min-heap, if at any point the size of min-heap exceeds K, remove the topmost element. This ensures, at the end of the traversal, the K largest elements from the array are present in the min-heap.
The Kth largest element is the smallest element in the min-heap, which can be accessed in an O(1) operation.
This is the most commonly used approach for finding the Kth largest element in an unsorted array.
Implementation in C++
C++
C++
#include <bits/stdc++.h> using namespace std;
int kthLargest(vector<int>&nums, int k){ if(k>nums.size()) return -1;/* return some flag for edge case */ priority_queue<int, vector<int>, greater<int>> pq; /* initialize min-heap */
for(auto &num: nums){ pq.push(num); if(pq.size()>k){ /* k+1 elements present in pq, so erase the minimum */ pq.pop(); } }
return pq.top(); } int main() { vector<int> nums = {5, 6, 7, 10, 11, 15, 21, 32, 14}; int k = 4;
cout<<k<<"th largest element: "<<kthLargest(nums, k); }
You can also try this code with Online C++ Compiler
The array of size N is traversed once, and at each step, an element is inserted to a min-heap which has maximum size K (insertion takes log(size of the heap)).
Space Complexity: O(K)
The min-heap only contains at most K elements.
Approach - 5: Using Standard Template Library
This approach involves using the sorting functionality provided by the Standard Template Library (STL) in C++. We sort the array/vector in descending order, ensuring that the largest elements come first. Then, we simply access the Kth element of the sorted array/vector, which gives us the Kth largest element.
This approach is straightforward and efficient, as the sorting algorithm used by the STL (std::sort function) typically has a time complexity of O(n log n), where n is the number of elements in the array/vector. After sorting, accessing the Kth element is a constant-time operation. Let us look the implementation in different languages:
public class KthLargestElement { public static int kthLargest(List<Integer> nums, int k) { Collections.sort(nums, Collections.reverseOrder()); return nums.get(k - 1); }
public static void main(String[] args) { List<Integer> nums = Arrays.asList(3, 1, 4, 2, 5); int k = 2; System.out.println("Kth largest element: " + kthLargest(nums, k)); } }
You can also try this code with Online Java Compiler
What is the best way to find the kth smallest element in an array?
The best way to find the kth smallest element in an array is using the QuickSelect algorithm, which is an efficient variation of the QuickSort algorithm, providing average-case linear time complexity.
Why do we use KTH largest element in an array?
Finding the Kth largest element in an array is useful in various scenarios, such as identifying outliers, determining top performers, or solving specific algorithmic problems like finding the median or selecting elements above a certain threshold.
How do you find the Kth largest element in a sequence?
The Kth largest element can be found by either sorting the array or inserting the elements into a heap. Using a heap is more efficient, as the space will be bound by K and not by the size of input array.
Conclusion
In this article, we discussed the Kth largest element in an array problem and a few approaches to it. We first started from the most straightforward approach i.e., the Brute Force approach, and then move on to more optimized approaches.
85+ registered