Implement quickselect to return the kth smallest element (k is 1-indexed) of an integer array using Lomuto partitioning.

Examples

Example 1:

Input: nums = [3, 1, 4, 1, 5, 9, 2, 6], k = 3
Output: 2
Explanation: Sorted view is [1, 1, 2, 3, 4, 5, 6, 9]. The 3rd smallest (1-indexed) is 2. Quickselect partitions around a (preferably random) pivot and recurses only into the side containing index k - 1. Expected O(n).

What is quickselect's expected time complexity, and why does it average O(n) instead of O(n log n) like quicksort?

Compare quickselect to a min-heap / max-heap approach for finding the kth smallest. When is the heap approach preferable?

A naive implementation always picks the last element as the pivot. Construct an input that forces O(n^2) time and explain why.