Python Program to Find kth Largest Element

You can find the kth largest element in a list using sorted(arr, reverse=True)[k-1] which sorts the list in descending order and picks the element at index k-1.

Examples

Input[3, 1, 5, 12, 2], k=3

Output3

Input[10, 4, 7, 9, 1], k=1

Output10

Input[5, 5, 5, 5], k=2

Output5

How to Think About It

To find the kth largest element, first think about sorting the list from largest to smallest. Once sorted, the kth largest is simply the element at position k-1 because counting starts at zero. This way, you don't have to search manually; sorting organizes the numbers so you can pick the right one easily.

Algorithm

1

Get the list of numbers and the value k.

2

Sort the list in descending order (largest to smallest).

3

Pick the element at index k-1 from the sorted list.

4

Return this element as the kth largest.

Code

python

def kth_largest(arr, k):
    sorted_arr = sorted(arr, reverse=True)
    return sorted_arr[k-1]

# Example usage
numbers = [3, 1, 5, 12, 2]
k = 3
print(kth_largest(numbers, k))

Output

3

Dry Run

Let's trace the example with input list [3, 1, 5, 12, 2] and k=3 through the code.

1

Input list and k

arr = [3, 1, 5, 12, 2], k = 3

2

Sort list in descending order

sorted_arr = [12, 5, 3, 2, 1]

3

Select kth largest element

kth element = sorted_arr[3-1] = sorted_arr[2] = 3

4

Return result

Return 3

Step	sorted_arr	kth largest element
After sorting	[12, 5, 3, 2, 1]	N/A
Pick element at index 2	[12, 5, 3, 2, 1]	3

Why This Works

Step 1: Sorting the list

Sorting the list in descending order arranges numbers from largest to smallest, making it easy to find the kth largest by position.

Step 2: Indexing for kth element

Since list indexes start at 0, the kth largest element is at index k-1 in the sorted list.

Step 3: Returning the result

Returning the element at index k-1 gives the correct kth largest number from the original list.

Alternative Approaches

Using heapq.nlargest

python

import heapq

def kth_largest(arr, k):
    return heapq.nlargest(k, arr)[-1]

# Example usage
numbers = [3, 1, 5, 12, 2]
k = 3
print(kth_largest(numbers, k))

This method uses a heap to efficiently find the k largest elements and returns the smallest among them, which is the kth largest overall. It is faster for large lists when k is small.

Using quickselect algorithm

python

def partition(arr, low, high):
    pivot = arr[high]
    i = low
    for j in range(low, high):
        if arr[j] >= pivot:
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[high] = arr[high], arr[i]
    return i

def quickselect(arr, low, high, k):
    if low == high:
        return arr[low]
    pivot_index = partition(arr, low, high)
    if pivot_index == k:
        return arr[pivot_index]
    elif pivot_index > k:
        return quickselect(arr, low, pivot_index - 1, k)
    else:
        return quickselect(arr, pivot_index + 1, high, k)

def kth_largest(arr, k):
    return quickselect(arr, 0, len(arr) - 1, k - 1)

# Example usage
numbers = [3, 1, 5, 12, 2]
k = 3
print(kth_largest(numbers, k))

Quickselect finds the kth largest element without fully sorting the list, offering better average performance on large datasets but is more complex to implement.

Complexity: O(n log n) time, O(n) space

Time Complexity

Sorting the list takes O(n log n) time, which dominates the runtime. Picking the kth element is O(1).

Space Complexity

Sorting creates a new sorted list, so it uses O(n) extra space.

Which Approach is Fastest?

Using heapq.nlargest or quickselect can reduce time to O(n log k) or average O(n), making them faster for large lists and small k.

Approach	Time	Space	Best For
Sorting	O(n log n)	O(n)	Small to medium lists, simple code
heapq.nlargest	O(n log k)	O(k)	Large lists with small k
Quickselect	Average O(n)	O(1)	Large lists, performance critical