- Prepare
- All Platforms
- Programming
- Aptitude
- Syllabus
- Interview Preparation
- Interview Exp.
- Off Campus
- Prime Video
- Prime Mock

- PrepInsta Prime
- OffCampus
- Internship
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

No New notification

- Login
- Get Prime

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

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

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

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

**Naive Approach**

**
****1. Using Sorting**

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

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

**Optimized Algorithms**

**
****1. Using Quick Select Algorithm**

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

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

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

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