class Solution {

    public static int result = 0;

    public int findKthLargest(int[] nums, int k) {
        quickSelect(nums, 0, nums.length-1, k);
        return result;
    }

    public void quickSelect(int[] nums, int start, int end, int k) {
        //base

        if(start>end) return;
        if(start == end) {
            result = nums[start];
            return;
        }

        //recursive case

        Random random = new Random();

        int pivotIndex = start + random.nextInt(end - start);

        //swap pivot element with start element

        int temp = nums[start];
        nums[start] = nums[pivotIndex];
        nums[pivotIndex] = temp;

        int smaller = start;


        for(int bigger = start + 1; bigger <= end; bigger++ ) {
            if(nums[bigger] < nums[start]){
                smaller++;
                int temp1 = nums[bigger];
                nums[bigger] = nums[smaller];
                nums[smaller] = temp1;
            }
        }

        //unswap pivot at start with element at smaller
        int temp2 = nums[smaller];
        nums[smaller] = nums[start];
        nums[start] = temp2;

        if(smaller == nums.length-k) {result = nums[smaller]; return;}
        else if (nums.length-k < smaller) {
            quickSelect(nums, start, smaller -1, k);
        }
        else if (nums.length-k > smaller) {
            quickSelect(nums, smaller+1, end, k );
        }

    }
}