# Finding an element in an unsorted array equal to its rank in $O(n)$ time

I'm trying to figure out a way to think about this problem. Background: Given an unsorted array of distinct integers (can be positive or negative), I want to determine if there is an element in the array that is equal to its rank (i.e. if I do $S = Sort(Array)$, I want to find an element s.t. $S[i] = i$).

Some approaches I have thought about.

• Radix sort: But there's no guarantee on what is the largest/smallest element here

• Any comparison based sorting method: But that gets me at least $O(n \lg n)$ time.

So it seems that I am not supposed to sort before I figure out what the ranks of the elements in the array are. I also feel that it needs to be a selection type algorithm, but I am not sure how that can be applied here. Any ideas on where to go from here?

• What is $i$? Could you please formalize your background question? – xskxzr Feb 1 '18 at 3:15
• $i$ is just any integer representing the index. So I'm saying that in the resulting sorted array, the element at index $i$ is equal to $i$. – wieiooof Feb 1 '18 at 3:17

You can preprocess the array to transform all negative numbers to $0$, and to transform numbers greater than $n$ to $n+1$. This transformation does not change the result because negative numbers and numbers greater than $n$ is not able to equal to its rank. This transformation only costs $O(n)$ time.

Now you can do counting sorting with $O(n)$ time.

• What is the purpose of preprocess? Would the incorrect answer be returned if you left the array the way it was and just radix sorted? – rubyquartz Feb 3 '18 at 21:13