Quickselect and Kth Element
Partition-based selection: kth smallest in expected `O(n)`, worst case `O(n^2)`, plus when to prefer a heap-based approach.
Question Bank
Medium
Python
4 questions
quickselect
partitioning
algorithms
quiz
334 views
4
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).def quickselect(nums, k):
# TODO: return the k-th smallest (k is 1-indexed)
passWhat 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.