215_Kth Largest Element in an Array

Find the kth largest element in an unsorted array. There might be duplicates in the array.

Example 1:

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

Example 2:

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

Solution 1:

Idea:

• Sort the array in descending order, then get the kth element.

Time Complexity: $O(n \log{n})$

Space Complexity: $O(1)$

def findKthLargest(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    nums.sort(reverse=True)
    return nums[k-1]

Solution 2: ??

Idea:

• store a candidate set of k elements in a min-heap

Time Complexity: $O(n \log{k})$

Space Complexity: $O(k)$

Solution 3

Idea:

• Similar to quick sort

• Randomly choose a pivot, store the elements less than the pivot, larger than the pivot and the number of duplicated pivot n.

• If including some or all the pivot, the elements larger than (or equal to) the pivot can be k, then the pivot is the kth largest.

• If less than k, the values in the larger group and pivot are not enough for kth largest, so we focus on the array with smaller values and find the next several largest.

• If larger than k, focus on the larger group for the kth largest element.

Time Complexity: $O(n \log{n})$

Space Complexity: $O(n)$ we can reduce the extra space to $O(1)$by in-place partition around the pivot.

def findKthLargest(nums, k):
    """
    :type nums: List[int]
    :type k: int
    :rtype: int
    """
    if not nums: return False
    if len(nums) < k: return False

    import random
    index = random.randint(0, len(nums)-1)
    pivot = nums[index]

    # partition the array around the pivot
    nums_smaller = []
    nums_larger = []
    n = 0   # number of pivot duplicates
    for i in range(len(nums)):
        if nums[i] > pivot:
            nums_larger.append(nums[i])
        elif nums[i] < pivot:
            nums_smaller.append(nums[i])
        else:
            n += 1

    if k-n<= len(nums_larger) <= k-1 :
        return pivot
    elif len(nums_larger) > k-1:
        # focus on the larger part
        return findKthLargest(nums_larger, k)
    else:
        # focus on the smaller part
        return findKthLargest(nums_smaller, k-len(nums_larger)-n)