Kth Smallest Element Using Randomized Selection
Problem Input - array A with n distinct numbers and a number i ∈ {1, 2, …, n} Output : ith order statistic i.e. ith smallest element of the input array Solution We have already seen multiple solutions here - Kth OR Nth Smallest Element in an Array. Here will focus on Linear time or O(n) solution. Finding the ith smallest element may seem difficult at first, but is it possible to find some O(n) or linear time solution. ...