Im trying to find an algorithm which returns array elements that a[i] > 2a[j] with i < j in O(nlogn). I can think how to implement this algorithm using double for but i cant implement it in O(nlogn). Does anyone have an idea about how to implement that?


Hint: First, try to come up with an algorithm which counts number of inversions in a given array. There is a classical well-known algorithm for such problem.

| cite | improve this answer | |
  • $\begingroup$ Can i implement that using merge sort algorithm? $\endgroup$ – Lee Yaan Apr 18 at 1:29
  • $\begingroup$ Yes, it is a usual way of solving such problems. $\endgroup$ – Vladislav Bezhentsev Apr 18 at 1:31

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.