215. Kth Largest Element in an Array

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < nums.length; i++) {
            pq.add(nums[i]);
            if (pq.size() > k) pq.poll();
        }

        return pq.poll();
    }
}

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

    private int quickSelect(int[] nums, int left, int right, int target) {
        int pivotIndex = (left + right) >> 1;
        pivotIndex = partition(nums, left, right, pivotIndex);

        if (pivotIndex == target) return nums[pivotIndex];
        else if (pivotIndex < target) return quickSelect(nums, pivotIndex + 1, right, target);
        else return quickSelect(nums, left, pivotIndex - 1, target);
    }

    private int partition(int[] nums, int left, int right, int pivotIndex) {
        if (left == right) return left;

        int pivot = nums[pivotIndex];
        swap(nums, right, pivotIndex);  // must be right, or the cur in swap before right can exceed boundary

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

        swap(nums, cur, right);
        return cur;
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}