How to find the kth smallest element within an interval of an array

Question

Suppose I have an unsorted integer array a[] with length N. Now I want to find the k-th smallest integer within a given interval a[i]-a[j] (1 <= i <= j <= N). Ex: I have an array a[10]={10,15,3,8,17,11,9,25,38,29}. Now I want to find the 3-rd smallest element within a[2]-a[7] interval. The answer is 9. I know this can be done by sorting that interval. But this costs O(Mlog(M)) (M = j - i + 1) time. Also, I know that, this can be done by segment tree, but I can't understand how to modify it to handle such query.

Answer 1

You can use Quickselect, a modification of Quicksort to find the k^th smallest/largest value in a list. Let's just assume that you're trying to do this for the entire array, for the sake of simplicity (note that there is no difference).

Essentially you use quicksort, but only use one recursive call instead of two. Once your pivot it placed, you only need to call quicksort for one of the partitions, depending on the placement of pivot. This is O(N²), but average case of O(N). If you use random pivots, it's pretty much always going to be O(N).