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?

  • $\begingroup$ What is $i$? Could you please formalize your background question? $\endgroup$
    – xskxzr
    Feb 1, 2018 at 3:15
  • $\begingroup$ $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$. $\endgroup$
    – wieiooof
    Feb 1, 2018 at 3:17

1 Answer 1


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.

  • $\begingroup$ 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? $\endgroup$
    – rubyquartz
    Feb 3, 2018 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.