215. QuickSelect!

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int target = nums.length-k;
        return quickSelect(nums, target, 0, nums.length-1);
    }
    // target is index not value
    private int quickSelect(int[] nums, int target, int start, int end){
        int index = partition(nums, start, end);
        if(index==target) return nums[target];
        if(index<target){
            return quickSelect(nums, target, index+1, end);
        }else{
            return quickSelect(nums, target, start, index-1);
        }
    }
    private int partition(int[] nums, int start, int end){
        int pivit = end;
        int left = start;
        int right = end-1;
        while(left<=right){
            if(nums[left]>nums[pivit] && nums[right]<nums[pivit]){
                swap(nums, left, right);
                left++;
                right--;
            }
            
            if(nums[left]<=nums[pivit]){
                left++;
            }
            
            if(nums[right]>=nums[pivit]){
                right--;
            }
        }
        swap(nums, pivit, left);
        return left;
    }
    
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}