Kth Smallest Element in an Array

Clarify whether kth smallest counts duplicate values separately; that is the usual contract. Sorting gives a correct O(n log n) baseline. For a predictable non-mutating approach, keep a max-heap of at most k elements: insert each number and remove the heap maximum when size exceeds k. The root then is the kth smallest, using O(n log k) time and O(k) space. For one in-memory query, quickselect is often better: partition around a randomized pivot, then continue only on the side containing index k-1 in ascending order. Its invariant is that every value left of the pivot is no larger and every value right is no smaller, with careful handling of equals. Expected time is O(n), worst case O(n^2), and it mutates the array unless copied. Test k=1, k=n, negative values, all-equal arrays, and invalid k if it is not guaranteed.