How to Find the Kth Largest Element in an Array Using QuickSort

Problem Statement

The task is to return the kth largest element in an integer array. For example, in the sorted array [1,2,3], the 1st largest element is 3 (index 2), the 2nd largest is 2 (index 1), so the index of the kth largest element is len(nums) - k.

Key Observation

Because the array is sorted in ascending order, the element we need is always located at position len(nums) - k. The algorithm therefore focuses on finding the element that ends up at this index without fully sorting the whole array.

QuickSort‑Based Selection Process

The solution repeatedly applies a quicksort‑style partition (implemented in quickSort) on the current sub‑array [lo, hi]. The partition returns the final position right of the pivot element.

If right == len(nums) - k, the pivot is exactly the kth largest element and the algorithm returns nums[right].

If right > len(nums) - k, the desired index lies in the left sub‑array, so hi is moved to right - 1 and the process repeats.

If right < len(nums) - k, the desired index lies in the right sub‑array, so lo is moved to right + 1 and the process repeats.

This loop continues until the pivot lands on the target index, guaranteeing that the kth largest element is found in average linear time.

Complete Go Implementation

func findKthLargest(nums []int, k int) int {
    // The index of the kth largest element in an ascending array
    index := len(nums) - k
    lo, hi := 0, len(nums)-1
    for {
        idx := quickSort(nums, lo, hi) // partition returns pivot index
        if index == idx {
            // Pivot is the kth largest element
            return nums[idx]
        } else if index < idx {
            // Search left sub‑array
            hi = idx - 1
        } else {
            // Search right sub‑array
            lo = idx + 1
        }
    }
    return 0 // unreachable
}

// quickSort partitions the sub‑array [lo, hi] around the pivot nums[lo]
func quickSort(nums []int, lo, hi int) int {
    v := nums[lo] // pivot value
    left := lo + 1
    right := hi
    for left <= right {
        for left <= right && v > nums[left] {
            left++
        }
        for left <= right && v <= nums[right] {
            right--
        }
        if left > right {
            break
        }
        // Swap elements that violate the left‑small, right‑large rule
        nums[left], nums[right] = nums[right], nums[left]
    }
    // Place pivot in its final position
    nums[lo], nums[right] = nums[right], nums[lo]
    return right
}