Find 3rd smallest
Input
nums = [7, 10, 4, 3, 20, 15], k = 3
Output
7
Sorted order is [3,4,7,10,15,20]; the 3rd smallest is 7.
Full lesson preview
Find k-th smallest using quickselect
Select the k-th smallest element in unsorted arrays using the Quickselect algorithm.
Python practice30 minSearching & SortingAdvancedLast updated March 25, 2026
Problem statement
Given a list of integers nums and an integer k, return the k-th smallest element (1-indexed). If k is out of range (k < 1 or k > len(nums)), return None. Implement the Quickselect algorithm (randomized pivot is acceptable) to achieve expected linear time.
Task
Implement quickselect to find the k-th smallest element with average O(n) time and O(1) extra space (expected).
Examples
Input format
Function call: kth_smallest(nums, k) where nums is a list of integers and k is a 1-based index.
Output format
Return the k-th smallest integer, or None if k is out of range.
Constraints
- 1 <= len(nums) <= 10^6 (practical memory/time limits apply)
- k is 1-based
- Expected average time O(n) with randomized pivot
Samples
Sample 1
Input
kth_smallest([3, 1, 2, 4], 1)
Output
1
Smallest element is 1.