Kth Smallest Element

Given a list of unsorted integers nums, and an integer k, return the kth (0-indexed) smallest element in the list.

This should be done in \(\mathcal{O}(n)\) time on average.

Constraints

• 0 ≤ k < n ≤ 100,000 where n is the length of nums

https://binarysearch.com/problems/Kth-Smallest-Element

Examples

Example 1

Input

• nums = [5, 3, 8, 2, 0]
• k = 2

Output

• answer = 3

Explanation

When sorted the numbers are [0, 2, 3, 5, 8] and index 2’s value is 3.

Solution