Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

Additional information

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

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

Brute Force (Sorting)

Intuition

The most straightforward way to find the kth largest element is to simply sort the entire array in descending order. Once the array is sorted from largest to smallest, the kth largest element is just sitting exactly at index k - 1.

Algorithm

1. Sort the nums array in descending order. In Python, you can do this using nums.sort(reverse=True).
2. Return the element at the k - 1 index.

def find_kth_largest(nums: list[int], k: int) -> int:
    nums.sort(reverse=True)
    return nums[k - 1]

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: Sorting an array of size N takes O(N log N) time in the average and worst cases. Accessing the index takes O(1) time.

• Space complexity: O(1) or O(N)

• Reason: We are sorting the array in place, so the auxiliary space is technically O(1). However, Python's Timsort algorithm requires up to O(N) space under the hood.

Min-Heap (Priority Queue) - Optimal

Intuition

Sorting the whole array is overkill because we only care about the top k elements. Everything smaller than the top k is useless to us.

We can optimize this by maintaining a Min-Heap of strictly size k. As we iterate through the nums array, we push elements into our heap. If the heap grows larger than k, we pop the smallest element out.

By using a Min-Heap, the smallest element of our "top k" group is always sitting at the root. When we finish scanning the entire array, the heap will contain exactly the k largest elements, and the absolute smallest of those k elements (which is the kth largest overall) will be right at the top!

Algorithm

1. Initialize an empty list min_heap.
2. Iterate through each number num in the nums array.
3. Push num onto the min_heap using heapq.heappush().
4. Check if the length of min_heap is strictly greater than k. If it is, pop the smallest element out using heapq.heappop().
5. After the loop finishes, the root of the heap (min_heap[0]) is the kth largest element. Return it.

def find_kth_largest(nums: list[int], k: int) -> int:
    min_heap = []
    
    for num in nums:
        heapq.heappush(min_heap, num)
        
        # Keep the heap size restricted to k
        if len(min_heap) > k:
            heapq.heappop(min_heap)
            
    # The root of the min-heap is the kth largest element
    return min_heap[0]

Time & Space Complexity

• Time complexity: O(N log k)

• Reason: We iterate through all N elements. Pushing and popping from a heap of size k takes O(log k) time. Thus, the total time is bounded by O(N log k). This is faster than sorting the entire array when k is much smaller than N.

• Space complexity: O(k)

• Reason: The heap strictly holds exactly k elements at any given time.