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

For example,
Given[3,2,1,5,6,4]and k = 2, return 5.

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

Credits:
Special thanks to@mithmattfor adding this problem and creating all test cases.

tag: Heap, Quick Sort

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) return -1;

        return helper(nums, k, 0, nums.length - 1);
    }

    public int helper(int[] nums, int k, int start, int end){
        int pos = partition(nums, start, end);

        if (pos < k - 1){
            return helper(nums, k, pos + 1, end);
        }
        else if (pos > k - 1){
            return helper(nums, k, start, pos - 1);
        }
        else{
            return nums[pos];
        }
    }

    public int partition(int[] nums, int start, int end){
        int i = start, j = start;

        while (j < end){
            if (nums[j] > nums[end]){
                swap(nums, i, j);
                i++;
            }
            j++;
        }
        swap(nums, i, end);

        return i;
    }

    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}