Quickselect

Category: Searching

Difficulty: Hard

Description

Write a function that takes in an array of distinct integers as well as an integer k and that returns the kth smallest integer in that array.

The function should do this in linear time, on average.

Sample Input

array = [8, 5, 2, 9, 7, 6, 3]
k = 3

Sample Output

5

Optimal Space & Time Complexity

Best: O(n) time | O(1) space - where n is the length of the input array\nAverage: O(n) time | O(1) space - where n is the length of the input array\nWorst: O(n^2) time | O(1) space - where n is the length of the input array