Find Kth Largest element (QuickSelect)

215.Kth Largest Element in an Array

Divide and Conquer

Array

QuickSelect

Problem Statement:

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example:

Input:

nums = [3,2,1,5,6,4] k = 2

→

Output:

5

After partitioning around pivots, 5 is placed in its correct position as the 2nd largest element.

Algorithm:

1. Use QuickSelect algorithm (optimized version of QuickSort)
2. Partition array around a pivot value
3. Recursively search left or right partition based on pivot position
4. Continue until pivot index matches k

public int findKthLargest(int[] nums, int k) {
    // Adjust k for zero-based indexing as we're looking for (k-1)th index
    return quickSelect(nums, k - 1, 0, nums.length - 1);
}

public int quickSelect(int[] nums, int k, int low, int high) {
    // Find the position of the pivot after partitioning
    int pIndex = partition(nums, low, high);
    
    // If pivot is at k, we found our element
    if (k == pIndex) {
        return nums[pIndex];
    }
    // If k is less than pivot, search left partition
    else if (k < pIndex) {
        return quickSelect(nums, k, low, pIndex - 1);
    }
    // If k is greater than pivot, search right partition
    else {
        return quickSelect(nums, k, pIndex + 1, high);
    }
}

public int partition(int[] nums, int low, int high) {
    // Choose rightmost element as pivot
    int pivot = nums[high];
    // pIndex tracks position for elements greater than pivot
    int pIndex = low;
    
    // Compare each element with pivot
    for (int i = low; i < high; i++) {
        // Put larger elements to the left (descending order)
        if (nums[i] > pivot) {
            swap(nums, i, pIndex);
            pIndex++;
        }
    }
    
    // Place pivot in its final position
    swap(nums, pIndex, high);
    return pIndex;  
}

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

Complexity:

Time: O(n) average, O(n²) worst case | Space: O(1)