# Kth Largest Element in an Array
###### tags: `Medium`
>question : https://leetcode.com/explore/interview/card/top-interview-questions-medium/110/sorting-and-searching/800/

>reference : [quick selection](https://magiclen.org/quickselect/)

>related problem :
## My Solution

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

## Other Solution

class Solution {
    public int findKthLargest(int[] nums, int k) {
        
        if (nums == null || nums.length == 0)
            return -1;
        
        return quickSelect(nums, 0, nums.length - 1, k);
    }
    
    private int quickSelect(int[] nums, int start, int end, int k) {
        if (start == end)
            return nums[start];
        
        int left = start, right = end;
        int pivot = nums[left + (right - left) / 2];
        
        while (left <= right) {
            while (left <= right && nums[left] > pivot)
                left++;
            while (left <= right && nums[right] < pivot)
                right--;
            if (left <= right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
        
        //Be careful about the recursive functions here
        if (start + k - 1 <= right)
            return quickSelect(nums, start, right, k);
        if (start + k - 1 >= left)
            return quickSelect(nums, left, end, k - (left - start));
        return nums[left - 1];
    }
    
    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
        return;
    }
}