Theory

• Quickselect on Wikipedia

Implementation in Java

class Solution {
    void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    int partition(int[] nums, int start, int end, int pivot) {
        int val = nums[pivot];
        swap(nums, pivot, end - 1);
        int x = start;
        for (int i = start; i + 1 < end; i++) {
            if (nums[i] < val) {
                swap(nums, x, i);
                x++;
            }
        }
        swap(nums, x, end - 1);
        return x;
    }

    public int findKth(int[] nums, int k) {
        int low = 0, high = nums.length;
        while (low < high) {
            if (low + 1 == high) {
                return nums[low];
            }
            int x = low + (high - low) / 2;
            int pivot = partition(nums, low, high, x);
            if (pivot + 1 == k) {
                return nums[pivot];
            }

            if (pivot + 1 < k) {
                low = pivot + 1;
            } else {
                high = pivot;
            }
        }
        return -1;
    }

    public int findKthLargest(int[] nums, int k) { return findKth(nums, nums.length - k + 1); }
}

Practice

• https://leetcode.com/problems/kth-largest-element-in-an-array/