Quick Select solution

• The average case is O(n), but worst case is O(n^2)
• read up more on https://notes.yxy.ninja/Algorithm/Quick-Select

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

    public int quickSelect(int[] nums, int left, int right, int k) {
        // to avoid O(n^2) worst case
        Random rand = new Random();
        int pivotIdx = rand.nextInt(right-left+1)+left;

        int finalPivotIdx = partition(nums, left, right, pivotIdx);

        if (finalPivotIdx == k) {
            return nums[k];
        } else if (finalPivotIdx < k) {
            return quickSelect(nums, finalPivotIdx+1, right, k);
        } else return quickSelect(nums, left, finalPivotIdx-1, k);
    }

    // Make sure element at the left are smaller, elements at the right are bigger
    // return the final index of the pivot element
    public int partition(int[] nums, int left, int right, int pivotIdx) {
        // int[] subArray = Arrays.copyOfRange(nums, left, right+1);
        // System.out.println("Pivot Index: " + pivotIdx);
        // System.out.println("Before Subarray: " + Arrays.toString(subArray));
        // int oldLeft = left;

        int pivotVal = nums[pivotIdx];
        swap(nums, pivotIdx, right);

        for (int i=left; i<right; i++) {
            if (nums[i] < pivotVal) {
                swap(nums, left, i);
                left++;
            }
        }

        swap(nums, left, right);

        // subArray = Arrays.copyOfRange(nums, oldLeft, right+1);
        // System.out.println("After Subarray: " + Arrays.toString(subArray));
        // System.out.println();
        return left;
    }

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

My solution (priority queue)

• This is not an optimised solution. The time complexity is O(n log n), and the space complexity is O(n). We use the integer value as a form of priority. The priority queue utilises a max heap, so when we poll, it will return values from highest to lowest.

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(a, b) * -1);

        for (int n:nums) pq.offer(n);

        for (int i=0; i<k-1; i++) pq.poll();

        return pq.poll();
    }
}