1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\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 '18 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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