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.

Language: Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int p = quickSelect(nums, 0, n - 1, n - k + 1);
        return nums[p];
    }
    
    int quickSelect(int nums[], int left, int right, int k){
        if (left < right) {
            int i = left, j = right, pivot = nums[left];
            while (left < right) {
                while (left < right && nums[right] >= pivot) {
                    right--;
                }
                nums[left] = nums[right];
                while (left < right && nums[left] <= pivot) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = pivot;

            if (left + 1 == k) {
                return left;
            } else if (left + 1 > k) {
                return quickSelect(nums, i, left - 1, k);
            } else {
                return quickSelect(nums, right + 1, j, k);
            }
        }
        return left;
    }
    
}

Analysis:

1. Minimum heap
2. Quick sort

Submission Detail

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

Language: Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        
        def partition(nums, l, r):
            i = l - 1
            pivot = nums[r]
            
            for j in range(l, r):
                if nums[j] >= pivot:
                    i += 1
                    nums[i], nums[j] = nums[j], nums[i]
            nums[i + 1], nums[r] = nums[r], nums[i + 1]
            return i + 1
        
        l = 0
        r = len(nums) - 1
        while True:
            pivot_index = partition(nums, l, r)
            if pivot_index == k - 1:
                return nums[k - 1]
            elif pivot_index > k - 1:
                r = pivot_index - 1
            else:
                l = pivot_index + 1

Submission Detail

Accepted Solutions Runtime Distribution

Accepted Solutions Memory Distribution

Summary:

1. Java runtime is shorter than Python;
2. Java uses more memory than Python;
3. Python runtime is horrible;