9

As mentioned in the question ,need to find total number of (i,j) pairs in array such that 

(1) **i<j** 
(2) **a[i]>a[j]**

where i and j are indices of the array . There are no space constraints .

My question is

 1) Is there any approach which takes less than O(N^2) time?
 2) if so what is least complexity ?
 3) How do we prove that ?

I hope i'm clear with the question .

My approach is as follows

One way of doing the question is using brute fore which takes O(N^2) time .

But I think that there should be a better optimised solution to this question at-least O(NlogN) sollution .The reason for my intuition is as follows

Intuition 1) For sorting an array in ascending order conditions we have are : for i<j , a[i]<a[j] which is similar to my question . I also read that sorting has lower bound of Omega(n log n) . So my question should also have Omega(n log n) . I may be completely wrong if so please correct me .

My second intuition is:

Suppose we have an array of elements as follows : 4,9,7,3,2,1,8,12

we calculate above condition i<j , a[i]>a[j] for element 4 ,as i=0 points to 4 ,the possible values for j are 3,4,5 .since a[0]>a[3],a[0]>a[4],a[0]>a[5] ,so my total no of (i,j) pairs for now is 3 . Next time when I increment i(index) to 1,the possibles values of j are 2,3,4,5,6 . But we should use the fact that when i=0 (when a[i]=4) we have computed 3 elements less than a[i=0] which is in turn less than a[i=1] , so i will not compare 9 with 3,2,1 (To remove unnecessary computations ).If we can remove unnecessary computations then we can reduce complexity to something less than O(N^2) or else no solution less than O(N^2) exists.But if solution exists then how do we do that.I tried making graph but my efforts are futile .

Approach 1)In-order to obtain O(nlogn) complexity I think we need to tweak around quick sort or merge sort to get solution but problem here is, if we sort the array we loose the actual positions of elements.

Approach 2)In-order to get solution in O(NlogN) time I think using tree we may get the optimised sollution . I didn't get any clue.

Approach 3)If there exists any O(N) time algorithm it should be with hashing . But in this case simple hashing doest work .

So please let me know which of the above intuitions or approaches are correct (If correct which approach will lead to optimised sollution and how).

Imposter
  • 2,666
  • 1
  • 21
  • 31

2 Answers2

13

You can count inverted pairs with the algorithm, similar to merge sort, as explained here.

The idea is to merge sort the array while counting, how many inversions were changed on each step.

A different approach is to use an order-statistics tree. You sequentially insert elements of the array into this tree, and after each insertion see, how many elements, preceding the inserted element, are larger than it.

An alternative to order-statistics tree is Indexable skiplist.

Both algorithms have O(N log N) time complexity.

To get approximate number of inversions, O(N) time complexity is possible with some limitations. We can modify Bucket sort in the same manner merge sort was modified.

On "scatter" phase of Bucket sort we should estimate number of elements in buckets for larger elements, while inserting element at the end of some bucket (elements in each bucket remain in original order).

On "sort" phase of Bucket sort we should modify (in the same way) sorting algorithm (insertion sort, most likely). While inserting the element into its proper place, we should count over how many other elements it jumped.

As for limitations, this algorithm works only with numbers (or with objects, easily convertible to numbers), and we should know in advance how these numbers are distributed. So, if we have an array of uniformly distributed integers, this algorithm should work properly.

Evgeny Kluev
  • 24,287
  • 7
  • 55
  • 98
  • The order-statistics tree sounds like a nice idea. Is it something like this: Binary search tree with the addition that each node keeps track of the number of children in its right subtree containing greater elements. Insertion will update this count as we traverse down the tree, and also counts the number of inversions which can be found from these counts as we go down the tree. Is that roughly correct? – Paresh Oct 31 '12 at 13:42
  • @Paresh: That's right. Except that each node keeps track of the number of nodes in the sub-tree, rooted by it. – Evgeny Kluev Oct 31 '12 at 13:48
  • @EvgenyKluev: good solution . I guess since its matter of counting a proper hash(double or more) function should do work in O(N) as there is no space requirement . – Imposter Oct 31 '12 at 14:20
  • 1
    @Imposter: I don't think hashing helps here. Right now I'm thinking about other O(N) solution. – Evgeny Kluev Oct 31 '12 at 14:23
  • I was asked this in an interview and got absolutely wrecked. Thanks for the resources. – RYS Mar 14 '18 at 02:20
6

Such pairs are called number of inversions in an array. It is one measure of how close the array is to being sorted. You can modify merge sort to efficiently count the number of inversions in O(nlogn) time. Refer to this for details.

Paresh
  • 542
  • 2
  • 6
  • 15
  • 1
    provided link gives 403 forbidden, so web-archive [https://web.archive.org/web/20170222074703/http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf](https://web.archive.org/web/20170222074703/http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec08-inversions.pdf) – BluePie Aug 01 '21 at 11:24