Solution 1: Brute Force (n log(n) Worst-Case Time Complexity)

Intuition:

The brute force approach to finding the kth largest element in an array involves sorting the entire array and then accessing the kth largest element directly:

  • sort the array in descending order.
  • retrieve the element at the (k-1)th index of the sorted array.

It is simple and easy to implement.

Solution:

from typing import List

def find_kth_largest(nums: List[int], k: int) -> int:
    # Step 1: Sort the array in descending order
    nums.sort(reverse=True)
    
    # Step 2: Return the k-th largest element
    return nums[k - 1]

# Test cases
result = find_kth_largest([3, 2, 1, 5, 6, 4], 2)
print(result)  # Output: 5

result = find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
print(result)  # Output: 4

Time Complexity:

  • The time complexity of sorting an array is O(n log(n)), where n is the number of elements in the array.
  • Accessing an element by index takes O(1) time.
  • Thus, the overall time complexity of the brute force approach is dominated by the sorting step, making it O(n log(n)).

Space Complexity:

The space complexity is O(n) due to the space required for the sorting algorithm, which may use auxiliary space.

Solution 2: Min-Heap (n log(k) Worst-Case Time Complexity)

Intuition:

For finding the kth largest element in an array, a min-heap (or priority queue) can be used. This approach maintains a heap of size k containing the k largest elements seen so far. The root of the heap (the smallest element in the heap) will be the kth largest element. This approach ensures an O(n log(k)) time complexity, which is very efficient for small values of k relative to the size of the array.

  1. Initialize a min-heap and add the first k elements of the array to it.
  2. For each of the remaining elements in the array, if the element is greater than the root of the heap, replace the root with this element and re-heapify.
  3. The root of the heap will be the k-th largest element.

Solution:

import heapq
from typing import List

def find_kth_largest(nums: List[int], k: int) -> int:
    # Create a min-heap with the first k elements
    min_heap = nums[:k]
    heapq.heapify(min_heap)
    
    # Process the remaining elements
    for num in nums[k:]:
        if num > min_heap[0]:
            heapq.heappushpop(min_heap, num)
    
    # The root of the heap is the k-th largest element
    return min_heap[0]

# Test cases
result = find_kth_largest([3, 2, 1, 5, 6, 4], 2)
print(result)  # Output: 5

result = find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
print(result)  # Output: 4

Time Complexity:

  • Creating a min-heap from the first k elements takes O(k) time.
  • For each of the remaining n−k elements, the heap operation (push and pop) takes O(log(k)) time.
  • Therefore, the total time complexity is O(k) + O((n−k) log(k)) = O(n log(k)).

Space Complexity:

The space complexity is O(k) due to the space required for the min-heap.

Solution 3: Quickselect (Linear Average-Case Time Complexity)

Intuition:

We can solve this problem efficiently in average case using the Quickselect algorithm, which is a selection algorithm to find the kth smallest/largest element in an unordered list. It is related to the QuickSort sorting algorithm.

  1. Similar to QuickSort, select a pivot and partition the array such that elements greater than the pivot are on one side, and elements less than the pivot are on the other side.
  2. Based on the position of the pivot, decide whether to recur on the left or right partition, or return the pivot as the k-th largest element.

Solution:

import random
from typing import List

def find_kth_largest(nums: List[int], k: int) -> int:
    # Convert kth largest to index
    k = len(nums) - k
    
    def quickselect(left: int, right: int) -> int:
    	# Randomly select a pivot to avoid the worst-case scenario.
        pivot_index = random.randint(left, right)
        pivot = nums[pivot_index]
        
        # Move pivot to the end
        nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
        
        # Partition the array
        # Rearrange such that all elements less than the pivot are to 
        # its left, and all elements greater are to its right.
        store_index = left
        for i in range(left, right):
            if nums[i] < pivot:
                nums[store_index], nums[i] = nums[i], nums[store_index]
                store_index += 1
        
        # Move pivot to its final place
        nums[right], nums[store_index] = nums[store_index], nums[right]
        
        # Determine if we need to go left or right. Recursively 
        # search until the k-th largest element is found.
        if store_index == k:
            return nums[store_index]
        elif store_index < k:
            return quickselect(store_index + 1, right)
        else:
            return quickselect(left, store_index - 1)
    
    return quickselect(0, len(nums) - 1)

# Test cases
result = find_kth_largest([3, 2, 1, 5, 6, 4], 2)
print(result)  # Output: 5

result = find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)
print(result)  # Output: 4

Time Complexity:

The Quickselect algorithm, which is used to find the kth largest (or smallest) element in an unsorted array, has an average-case time complexity of O(n) but a worst-case time complexity of O(n^2). Here’s a detailed breakdown of why this is the case:

  1. Average Case Analysis:
    • In the average case, the Quickselect algorithm partitions the array into two roughly equal parts at each step, similar to Quicksort.
    • At each partitioning step, a pivot is selected, and the array is rearranged such that all elements less than the pivot are on one side and all elements greater than the pivot are on the other side.
    • After partitioning, we know the exact position of the pivot. If the pivot is at the kth position (in the context of kth largest element), we are done.
    • Otherwise, we recurse only on the part of the array that contains the kth element. On average, this results in dividing the problem size roughly in half each time.

    The recurrence relation for the average-case time complexity is: T(n) = T(n/2) + O(n)

    This is because:

    • T(n/2) represents the time to solve the problem for half of the elements.
    • O(n) represents the time to partition the array.

    Solving this recurrence relation gives: T(n) = O(n) + O(n/2) + O(n/4) + … ≈ O(n)

    Thus, the average-case time complexity is O(n).

  2. Worst Case Analysis:
    • The worst case occurs when the pivot selection is poor, such as always picking the smallest or largest element as the pivot. This can happen if the array is already sorted or nearly sorted.
    • In the worst case, the partitioning does not divide the array into two equal parts but rather into parts of size 1 and n−1.

    This leads to the recurrence relation: T(n) = T(n−1) + O(n)

    This is because:

    • T(n−1) represents the time to solve the problem for n−1 elements.
    • O(n) represents the time to partition the array.

    Solving this recurrence relation gives: T(n) = O(n) + O(n−1) + O(n−2) + … + O(1) = O(n(n+1)/2) = O(n^2)

    Thus, the worst-case time complexity is O(n^2).

In practice, using a random pivot helps avoid the worst-case scenario by ensuring that the pivot is unlikely to consistently be the smallest or largest element. This typically results in a well-balanced partition, leading to the average-case time complexity of O(n).

Space Complexity:

  • O(1) auxiliary space for the in-place partitioning, apart from the recursion stack.
  • O(log(n)) space for the recursion stack depth on average.