Kth Largest Element in an Array

Problem Statement

Given an integer array nums[] and an integer k, find the kth largest element in the array.

Exanple: Input: val = [3, 2, 1], wt = [5, 6, 4], k=2, Output: 2

Approach 1: Sorting

Explanation: Sort the array and then find the kth largest element.

Time Complexity: O(nlogn)

Space Complexity: O(1) excluding the auxiliary array required 

function Kthlargestelement(arr, k):
    sort(arr) // Sort the array in ascending order
    return arr[n-k] // Return the kth largest element

Approach 2: Using MaxHeap

Explanation: Store all the elements in the heap and pop k times to get kth largest element.

Time Complexity: O(nlogn+klogn)=O(nlogn)

Space Complexity: O(n)

pq = new MaxHeap()
function Kthlargestelement(arr, k):
    for i in range(0, n):
        pq.push(arr[i])
    for i in range(0, k-1):
        pq.pop()
    return pq.top()

Approach 3: Using Quickselect(Divide and Conquer)

Explanation: Using modified QuickSort and during each step with help of index of pivot performing Binary Search to look for kth Largest element.

Time Complexity: O(nlogn) worst case:O(n2)

Space Complexity: O(logn) worst case:O(n) due to recursive stack 

function partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j = low to high - 1:
        if arr[j] <= pivot:
            i = i + 1
            swap arr[i] and arr[j]
    swap arr[i + 1] and arr[high]
    return i + 1

function quickselect(arr, low, high, k):
    if low == high:
        return arr[low]
    pivotIndex = partition(arr, low, high)
    if k == pivotIndex:
        return arr[k]
    else if k < pivotIndex:
        return quickselect(arr, low, pivotIndex - 1, k)
    else:
        return quickselect(arr, pivotIndex + 1, high, k)

function Kthlargestelement(arr, k):
    n = length(arr)
    return quickselect(arr, 0, n - 1, n - k)
Flowchart