There are many strategies available for your task (if you don't focus on the self-balancing tree to begin with).

It's usually a tradeoff speed / memory. Most algorithms require either to modify the array in place or `O(N)`

additional storage.

The solution with self-balancing tree is in the latter category, but it's not the right choice here. The issue is that building the tree itself takes `O(N*log N)`

, which will dominate the later search term and give a final complexity of `O(N*log N)`

. Therefore you're not better than simply sorting the array and use a complex datastructure...

In general, the issue largely depends on the magnitude of `i`

related to `N`

. If you think for a minute, for `i == 1`

it's trivial right ? It's called finding the maximum.

Well, the same strategy obviously work for `i == 2`

(carrying the 2 maximum elements around) in linear time. And it's also trivially symmetric: ie if you need to find the N-1 th element, then just carry around the 2 minimum elements.

However, it loses efficiency when `i`

is about N/2 or N/4. Carrying the i maximum elements then mean sorting an array of size `i`

... and thus we fallback on the `N*log N`

wall.

Jerry Coffin pointed out a simple solution, which works well for this case. Here is the reference on Wikipedia. The full article also describes the Median of Median method: it's more reliable, but involves more work and is thus generally slower.