Python Programg to Find Kth Largest Number in an Array.

Input: arr = [2, 5, 1, 6, 3, 9]  k = 2
Output: 6
Explanation: The second largest element in the array in 6

Input: arr = [12, 5, 1, 6, 3, 9, 10]  k = 3
Output: 9
Explanation: The third largest element in the array in 9

• Sort the entire array in descending order using an efficient sorting algorithm like Quicksort.

• Return the kth element from the sorted array, which represents the kth largest number.

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

arr = [2, 5, 1, 6, 3, 9]
k = 2
print("Kth largest element is",kth_largest(arr, k))  

Kth largest element is 6

• Time Complexity: O(n log n) for sorting + O(1) for retrieving kth element = O(n log n).

• Space Complexity: Depends on the sorting algorithm, generally O(log n) for efficient algorithms, up to O(n) in worst-case scenarios.

• Create a min-heap of size k and insert the first k elements from the array into the heap.

• The root of the min-heap will always be the smallest element among the k elements.

• For the remaining elements in the array, compare each element with the root of the heap.

• If the element is larger than the root, replace the root with this element and re-heapify the min-heap to maintain its structure.

• After traversing through the entire array, the root of the min-heap will be the kth largest element.

import heapq

def kth_largest_heap(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    
    for num in arr[k:]:
        if num > heap[0]:
            heapq.heappop(heap)
            heapq.heappush(heap, num)
    
    return heap[0]

arr =[12, 5, 1, 6, 3, 9, 10]  
k = 3
print("Kth largest element is", kth_largest_heap(arr, k))  

Quickselect Algorithm to Find the Kth Largest Number.

Quickselect is an algorithm used to find the kth smallest or largest element in an unsorted array. It's an optimization of the quicksort algorithm.

Algorithm:

• Choose a pivot element from the array. Rearrange the elements in the array such that elements smaller than the pivot are on the left, and elements greater than the pivot are on the right.

• Based on the position of the pivot after partitioning, the pivot's index is compared to k - 1.

• If the pivot index is equal to k - 1, then the pivot is the kth largest element. Return the pivot.

• If the pivot index is less than k - 1, the kth largest element must be in the right subarray. Recur for the right subarray.

• If the pivot index is greater than k - 1, the kth largest element must be in the left subarray. Recur for the left subarray.

• Repeat the process until the pivot's index is equal to k - 1.

# Python code to find kth largest element from array
def partition(arr, low, high):
    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 quickselect(arr, low, high, k):
    if low <= high:
        pivot_index = partition(arr, low, high)     

        if pivot_index == k - 1:
            return arr[pivot_index]
        elif pivot_index > k - 1:
            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)

arr = [3, 6, 8, 9, 12, 51, 13] 
k = 3
print("Kth largest element is", kth_largest(arr, k))