Array Sorting Binary Search Two Pointers
Intermediate Level

Implement the kthLargestQuickSelect method that returns the kth largest value using selection logic.

The input contains an integer array nums, its length size, and an integer k. Your task is to return the kth largest element in the array.

The answer is based on sorted order, not on unique values. Duplicate numbers are counted as separate elements.

For example, in [3,2,1,5,6,4], the second largest value is 5.

Example 1
Input:
nums (int[]) = [3,2,1,5,6,4]
size (int) = 6
k (int) = 2
Return:
(int) 5
Example 2
Input:
nums (int[]) = [3,2,3,1,2,4,5,5,6]
size (int) = 9
k (int) = 4
Return:
(int) 4
Example 3
Input:
nums (int[]) = [1]
size (int) = 1
k (int) = 1
Return:
(int) 1

Use the QuickSelect idea to avoid fully sorting the array.

If the array were sorted in ascending order, the kth largest value would be at index size - k. QuickSelect repeatedly partitions the array around a pivot and keeps only the side that can contain this target index.

When the pivot lands exactly at the target index, that value is the answer.

Pseudocode:

function kthLargestQuickSelect(nums, size, k):
    targetIndex = size - k
    left = 0
    right = size - 1
    while left <= right:
        pivotIndex = partition nums between left and right
        if pivotIndex == targetIndex:
            return nums[pivotIndex]
        else if pivotIndex < targetIndex:
            left = pivotIndex + 1
        else:
            right = pivotIndex - 1
function partition(nums, left, right):
    pivot = nums[right]
    store = left
    for i from left to right - 1:
        if nums[i] <= pivot:
            swap nums[i] and nums[store]
            store++
    swap nums[store] and nums[right]
    return store
Run your code to see the result.