class Solution {
public:
    /*
     * param k : description of k
     * param nums : description of array and index 0 ~ n-1
     * return: description of return
     */
    int kthLargestElement(int k, vector<int> nums) {
        // write your code here
        int size = nums.size();
        if (size < k) {
            return -1;
        }
        return quickSelect(nums, 0, size - 1, k);
    }

    int quickSelect(vector<int>& nums, int startIndex, int endIndex, int k) {
        int pivotIndex = (endIndex - startIndex) / 2 + startIndex;
        int pivot = nums[pivotIndex];

        int left = startIndex;
        int right = endIndex;

        while (left <= right) {
            while (left <= right && nums[left] > pivot) {
                left++;
            }
            while (left <= right && nums[right] < pivot) {
                right--;
            }

            if (left <= right) {
                int tmp = nums[left];
                nums[left] = nums[right];
                nums[right] = tmp;
                left++;
                right--;
            }
        }
//find start to right on left side, if the range >= k, keep searching the left side. 
        if (right - startIndex + 1 >= k) {
            return quickSelect(nums, startIndex, right, k);
        } else if (left - startIndex + 1 <= k) {
//find start to left, if the range < k, search only right side.
            return quickSelect(nums, left, endIndex, k - (left - startIndex));
        } else {
            return nums[right + 1];
        }
    }
};