Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Kth largest element in an array?
3.
Understanding the problem
4.
Brute Force Approach: Sorting the Array Using Bubble Sort
4.1.
Implementation in C++
4.2.
C++
4.3.
Implementation in Java
4.4.
Java
4.5.
Implementation in Python
4.6.
Python
5.
Approach 1: Sort
5.1.
Implementation in C++
5.2.
C++
5.3.
Implementation in Java
5.4.
Java
5.5.
Implementation in Python
5.6.
Python
6.
Approach 2: Using Quick Select
6.1.
Implementation in C++
6.2.
C++
6.3.
Implementation in Java
6.4.
Java
6.5.
Implementation in Python
6.6.
Python
7.
Approach 3: Using Max Heap
7.1.
Implementation in C++
7.2.
C++
7.3.
Implementation in Java
7.4.
Java
7.5.
Implementation in Python
7.6.
Python
8.
Approach 4: Using Min-Heap
8.1.
Implementation in C++
8.2.
C++
9.
Approach - 5: Using Standard Template Library
9.1.
C++ Implementation
9.2.
C++
9.3.
Java Implementation
9.4.
Java
9.5.
Python Implementation
9.6.
Python
10.
Frequently Asked Questions
10.1.
What is the best way to find the kth smallest element in an array?
10.2.
Why do we use KTH largest element in an array?
10.3.
How do you find the Kth largest element in a sequence?
11.
Conclusion
11.1.
Recommended Readings
11.2.
Recommended Problems
Last Updated: Mar 27, 2024
Medium

K’th Largest Element in an Array

Author Abhinav Anand
0 upvote
gp-icon
Competitive programming
Free guided path
16 chapters
99+ problems
gp-badge
Earn badges and level up

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.

kth largest element in an array

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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);
}

Output: 

4th largest element: 14

Time Complexity: 

  • 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;

System.out.println(k + "th largest element: " + kthLargest(nums, k));
}
}

Output: 

4th largest element: 14

Implementation in Python

  • Python

Python

def bubble_sort(nums):
n = len(nums)

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)}")

Output: 

4th largest element: 14

Approach 1: Sort

Similar to the previous approach, here we will sort the array in non-increasing order. But this time, we will use the in-built Sorting function.

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 */

sort(nums.begin(), nums.end(), greater<int>()); /* sort in non-increasing order */

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);
}


Output:

4th largest element: 14

 

Time Complexity: O(NlogN)

The in-built sort functions have O(NlogN) average case time complexity. For larger sized arrays, it may be O(N2). 
 

Space Complexity: O(1)

Additional memory is not required by the function, it only uses the input array.

Implementation in Java

  • Java

Java

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class KthLargestElement {

static int kthLargest(List<Integer> nums, int k) {
if (k > nums.size()) return -1; // Return some flag for edge case

Collections.sort(nums, Collections.reverseOrder()); // Sort in non-increasing order

return nums.get(k - 1);
}

public static void main(String[] args) {
List<Integer> nums = Arrays.asList(5, 6, 7, 10, 11, 15, 21, 32, 14);
int k = 4;

System.out.println(k + "th largest element: " + kthLargest(nums, k));
}
}

Output:

4th largest element: 14

Implementation in Python

  • Python

Python

def kth_largest(nums, k):
if k > len(nums):
return -1 # Return some flag for edge case

nums.sort(reverse=True) # Sort in non-increasing order

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)}")

Output:

4th largest element: 14

Approach 2: Using Quick Select

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);
}


Output:

4th largest element: 14

 

Time Complexity: O(N2)

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;

System.out.println(k + "th largest element: " + kthLargest(nums, k));
}
}

Output:

4th largest element: 14

Implementation in Python

  • Python

Python

def partition(arr, left, right):
pivot = arr[right] # Choose the rightmost element as the pivot
i = left - 1

for j in range(left, right):
if arr[j] <= pivot:
# Swap elements
i += 1
arr[i], arr[j] = arr[j], arr[i]

# Swap pivot to its correct position
arr[i + 1], arr[right] = arr[right], arr[i + 1]

return i + 1

def quick_select(arr, left, right, k):
if left == right: # Base case: Only one element
return arr[left]

pivot_index = partition(arr, left, right)

# Check the position of the pivot element
if pivot_index == k:
return arr[pivot_index]
elif pivot_index > k:
return quick_select(arr, left, pivot_index - 1, k)
else:
return quick_select(arr, pivot_index + 1, right, k)

def kth_largest(nums, k):
if k > len(nums):
return -1 # Return some flag for edge case
return quick_select(nums, 0, len(nums) - 1, len(nums) - k)

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)}")

Output:

4th largest element: 14

Approach 3: Using Max Heap

 

Max Heap

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);
}

Output: 

4th largest element: 14

 

Time Complexity: O(NlogN)

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.

Implementation in Java

  • Java

Java

import java.util.Arrays;
import java.util.PriorityQueue;

public class KthLargestElement {

static int kthLargest(int[] nums, int k) {
if (k > nums.length) return -1; // Return some flag for edge case

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a); // Initialize max-heap

for (int num : nums) {
pq.add(num);
}

k = k - 1;

while (k-- > 0) {
// Pop k-1 times
pq.poll();
}

return pq.poll();
}

public static void main(String[] args) {
int[] nums = {5, 6, 7, 10, 11, 15, 21, 32, 14};
int k = 4;

System.out.println(k + "th largest element: " + kthLargest(nums, k));
}
}

Output: 

4th largest element: 14

Implementation in Python

  • Python

Python

import heapq

def kth_largest(nums, k):
if k > len(nums):
return -1 # Return some flag for edge case

pq = [-num for num in nums] # Initialize max-heap
heapq.heapify(pq)

k = k - 1

while k > 0:
# Pop k-1 times
heapq.heappop(pq)
k -= 1

return -heapq.heappop(pq)

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)}")

Output: 

4th largest element: 14

Approach 4: Using Min-Heap

using min heap

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);
}

Output: 

4th largest element: 14

 

Time Complexity: O(NlogK)

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:

C++ Implementation

  • C++

C++

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int kthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end(), greater<int>());
return nums[k - 1];
}

int main() {
vector<int> nums = {3, 1, 4, 2, 5};
int k = 2;
cout << "Kth largest element: " << kthLargest(nums, k) << endl;
return 0;
}

 

Java Implementation

  • Java

Java

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

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));
}
}

 

Python Implementation

  • Python

Python

def kth_largest(nums, k):
nums.sort(reverse=True)
return nums[k - 1]

if __name__ == "__main__":
nums = [3, 1, 4, 2, 5]
k = 2
print("Kth largest element:", kth_largest(nums, k))

Output

Kth largest element: 4

Also see,  Euclid GCD Algorithm

Frequently Asked Questions

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.

Recommended Readings

Recommended Problems

To gain an edge over the competition you can also check out some Problems, Interview Experiences, and Guided Paths for topics such as Data Structure and Algorithms and several Courses taught by industry experts on Coding Ninjas Studio.

Happy Coding!

Previous article
How To Find The Kth Smallest Element In An Array?
Next article
Find Smallest Missing Positive Integer
Guided path
Free
gridgp-icon
Competitive programming
16 chapters
217+ Problems
gp-badge
Earn badges and level up
Live masterclass