Kth Largest Element in an Array

Given an integer array nums and an integer k, return the k<sup>th</sup> largest element in the array. Note that it is the k<sup>th</sup> largest element in the sorted order, not the k<sup>th</sup> distinct element. Can you solve it without sorting?

Example 1: Input: nums = [3,2,1,5,6,4], k = 2 Output: 5

Example 2: Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4

# Finding the Kth Largest Element in an Array

This problem asks us to find the kth largest element in an unsorted array. It's important to note that we're looking for the kth largest element in sorted order, not the kth distinct element.

## 1. Naive Solution: Sorting

A straightforward approach is to sort the array in descending order and then return the element at index `k-1`. This works because after sorting, the kth largest element will be at that position.

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

# Example Usage
nums = [3, 2, 1, 5, 6, 4]
k = 2
result = find_kth_largest_naive(nums, k)
print(f"The {k}th largest element is: {result}")  # Output: 5

Explanation:

• We use the sort() method with reverse=True to sort the input array nums in descending order.
• Then, we simply return the element at index k-1 of the sorted array, which corresponds to the kth largest element.

2. Optimal Solution: Using a Min-Heap (Priority Queue)

A more efficient approach involves using a min-heap (priority queue). We maintain a min-heap of size k. We iterate through the array. If the current element is larger than the smallest element in the heap (the root), we replace the root with the current element and heapify to maintain the min-heap property. After processing all elements, the root of the min-heap will be the kth largest element.

import heapq

def find_kth_largest(nums, k):
    min_heap = []

    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        elif num > min_heap[0]:
            heapq.heapreplace(min_heap, num)

    return min_heap[0]

# Example Usage
nums = [3, 2, 1, 5, 6, 4]
k = 2
result = find_kth_largest(nums, k)
print(f"The {k}th largest element is: {result}")  # Output: 5

nums = [3,2,3,1,2,4,5,5,6]
k = 4
result = find_kth_largest(nums, k)
print(f"The {k}th largest element is: {result}") # Output 4

Explanation:

1. Initialization: We create an empty min-heap called min_heap.
2. Iteration: We iterate through each num in the nums array.
3. Heap Size Check:
   • If the size of min_heap is less than k, we simply push the current num onto the heap.
4. Comparison and Replacement:
   • If the size of min_heap is equal to k, we compare the current num with the smallest element in the heap (i.e., the root, which is min_heap[0]).
   • If num is greater than the root, it means num is among the k largest elements we've seen so far. So, we replace the root with num using heapq.heapreplace(min_heap, num). This operation removes the smallest element (the root) and inserts the new element, maintaining the min-heap property.
5. Result: After iterating through all the elements in nums, the root of the min_heap (i.e., min_heap[0]) will be the kth largest element. We return this value.

3. Big(O) Run-time Analysis

• Naive Solution (Sorting): O(n log n), where n is the number of elements in the array, due to the sorting step.
• Optimal Solution (Min-Heap): O(n log k), where n is the number of elements in the array. For each element, we potentially perform a heap insertion or replacement, which takes O(log k) time. We do this for n elements, so the total time complexity is O(n log k).

4. Big(O) Space Usage Analysis

• Naive Solution (Sorting): O(1) in-place or O(n) depending on the sorting algorithm implementation. Some sorting algorithms like heapsort or insertion sort can be done in-place. However, other sorting algorithms, like merge sort, require O(n) auxiliary space.
• Optimal Solution (Min-Heap): O(k), as we maintain a min-heap of size k.

5. Edge Cases

• Empty Array: If the input array is empty, we should raise an exception or return a specific value (e.g., None) depending on the problem's requirements.
• Invalid k: If k is less than 1 or greater than the length of the array, we should also raise an exception or return an appropriate value.
• Duplicate Elements: The algorithm should handle duplicate elements correctly. It should return the kth largest element considering the duplicates.

import heapq

def find_kth_largest_edge_cases(nums, k):
    if not nums:
        raise ValueError("Input array cannot be empty")
    
    if k < 1 or k > len(nums):
        raise ValueError("k must be between 1 and the length of the array")

    min_heap = []

    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        elif num > min_heap[0]:
            heapq.heapreplace(min_heap, num)

    return min_heap[0]