Kth Largest Element in an Unsorted Array

Because the input is unsorted, a linear scan alone cannot identify the kth largest without retaining ranking information. A robust approach keeps a min-heap of the k largest values seen: every value enters, and if the heap grows beyond k, remove its smallest. The remaining root is the kth largest, with O(n log k) time and O(k) space. For expected O(n) one-shot selection, use randomized quickselect. Partition so values below and above a pivot are separated, determine the pivot's final rank, and iterate only on the relevant side. A three-way partition is particularly helpful when many values equal the pivot, because it can finish immediately when k falls inside the equal region. Clarify whether duplicates count and whether mutating the input is allowed. Test extreme k values, all equal values, negative numbers, and arrays of one element. Sorting is acceptable as a simpler O(n log n) baseline but is not necessary.