# 215. Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

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

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

# Solution

Approach 1: Sorting.

Approach 2: Max heap.

Approach 3: Partitioning.

# Code (Python)

Approach 1:

    def findKthLargest(self, nums: List[int], k: int) -> int:
        # most general solution
        # O(NlogN)
        nums.sort(reverse=True)
        return nums[k-1]

Approach 2:

    def findKthLargest(self, nums: List[int], k: int) -> int:
        # max heap, good when k is close to len(nums)
        # max(O(KlogN), O(N))
        neg_nums = [-num for num in nums]
        heapq.heapify(neg_nums)
        for _ in range(k):
            popped = heapq.heappop(neg_nums)
        return -popped

Approach 3:

    def findKthLargest(self, nums: List[int], k: int) -> int:
        # QuickSelect / idea of quicksort
        # O(N) 
        if len(nums) == 1 or k == 1:
            return max(nums)
        if k == len(nums):
            return min(nums)
        
        return self._quick_select(nums, len(nums) - k, 0, len(nums) - 1)
    
    # returns the kth smallest(0 indexed!) of the entire array, guaranteed to be in between indices lo and hi (inclusive)
    def _quick_select(self, nums, k, lo, hi):
        if lo == hi:
            return nums[lo]
        pivot = nums[(lo + hi) // 2] # better to be random
        left, right = lo, hi
        while left <= right: # ensure exhaustion
            while left <= right and nums[left] < pivot: # left <= right makes sure they don't go too far
                left += 1
            while left <= right and nums[right] > pivot:
                right -= 1 
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
            # ends up with right + 1 or 2 == left when array exhausted
            # where [lo, right](inclusive) <= pivot, [left, hi] >= pivot
        if k <= right: # k is the absolute array index
            return self._quick_select(nums, k, lo, right)
        elif k >= left:
            return self._quick_select(nums, k, left, hi)
        else:
            return pivot

# Code (C++)

Approach 1:

// Sorting.
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        std::sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

Approach 2:

// Max heap.
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(), nums.end());
        for (int i = 1; i < k; ++i)
        {
            pq.pop();
        }
        return pq.top();
    }
};

Approach 3:

// Partitioning.
// Everytime we get an element and get its position in the sorted array.
class Solution {
private:
    int tryPartition(vector<int>& nums, int head, int tail) {
        int left = head + 1;
        int right = tail;
        while (left <= right)
        {
            if (nums[left] <= nums[head])
                left++;
            else if (nums[right] >= nums[head])
                right--;
            else
                std::swap(nums[left], nums[right]);
        }
        std::swap(nums[head], nums[right]); // need a swap.
        return right;
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        int head = 0;
        int tail = nums.size() - 1;
        int headIndex = -1;
        int targetIndex = nums.size() - k;
        while (head <= tail)
        {
            headIndex = tryPartition(nums, head, tail);
            if (headIndex < targetIndex)
                head = headIndex + 1;
            else if (headIndex > targetIndex)
                tail = headIndex - 1;
            else
                break;
        }
        return nums[headIndex];
    }
};