0

Possible Duplicate:
Counting inversions in an array

Given an unsorted array arr, how do you count all possible pairs of indices (i, j) such that arr[i] < arr[j] ? The complexity should be linear or close to linear (the O(n^2) solution is obvious).

Edit:

Sorry, I forgot to mention but i < j is the condition on the indices.

Community
  • 1
  • 1
Coder25
  • 311
  • 1
  • 4
  • 13

3 Answers3

2

Hint:

For each pairs of indices (i, j), one and only one of these statements is true:

(a[i]<a[j]) , (a[i]=a[j]) , (a[i]>a[j]).

You'll have to walk over the array and count the number of instances for each value in a[]

Then, it is just a question of combinatorics...

Lior Kogan
  • 19,919
  • 6
  • 53
  • 85
1

[IMPORTANT]: Below is answer for initial question, where there is no condition that i < j

You can sort in O(N * log(N)) and then find an answer in O(N), It will give you O(N * log(N)) in total. Below is code of second part (after array is sorted):

int count = 0;
int curBefore = 0;
for (int i = 1; i < sorted.Length; i++)
{
    if (sorted[i] > sorted[i - 1])
    {
        curBefore = i;
    }
    count += curBefore;
}

And yes, there is a linear (pseudo, because Dictionary operations are not linear in general case) solution too! But it needs additional memory and using of Dictionary-like data structure:

int res = sorted.Length * (sorted.Length - 1) / 2;
Dictionary<int, int> dict = new Dictionary<int, int>();
for (int i = 0; i < sorted.Length; i++)
{
    if (!dict.ContainsKey(sorted[i]))
    {
        dict.Add(sorted[i], 0);
    }
    dict[sorted[i]]++;
}
foreach (var pair in dict)
{
    res -= (pair.Value - 1) * pair.Value / 2;
}
SergeyS
  • 3,515
  • 18
  • 27
  • @irrelephant I didn't downvote, but I'm guessing it's because this algorithm only checks `j=i+1`, not _all_ `(i,j)` pairs. In fact, there's nothing even in the question about restricting to `j > i`. So this code is not general enough. – Matt Ball Dec 09 '12 at 20:51
  • @MattBall SergeyS points out that the array is sorted first, so checking just `j > i` or even `j = i + 1` should be ok, I think. – irrelephant Dec 09 '12 at 20:53
  • This code will work for sure, I have tested it thoroughly. Yes, Array need to be sorted prior that. – SergeyS Dec 09 '12 at 20:54
  • @SergeyS: No map (dictionary) structure would give you deterministic O(1) for both insertion and lookup. – Lior Kogan Dec 09 '12 at 21:23
  • I didn't vote either way, but I am not seeing how this could work. Consider the case when `arr` contains a permutation of the integers from `1` to `N`. Surely the first algorithm would always give the same answer, regardless of which permutation it is? What am I missing? – NPE Dec 09 '12 at 21:37
  • @NPE SergeyS posted this answer before the OP updated it with the condition that `i < j`. – irrelephant Dec 09 '12 at 21:42
  • @irrelephant: I see. Might be worth adding a note to that effect at the top of the answer. – NPE Dec 09 '12 at 21:47
  • @irrelephant - thanks for pointing this out, I did not noticed that OP added this condition. – SergeyS Dec 09 '12 at 21:48
  • Well, you can add a note, but you don't need to change your answer to fit OP's condition since OP asked it [here](http://stackoverflow.com/questions/13792147/count-total-number-pairs-of-indices-in-array-such-that-arri-arrj-and-i-j#13792147) – irrelephant Dec 09 '12 at 21:49
0

You can use a customized binary tree to calculate this count on the fly. So, each node will contain three values: (v, lc, ec) where v is the value on the node, lc the number of nodes on the left tree and ec the number of values that were found to be equal to v. As you can see, these counters can be updated as you insert new values into the tree.

The final answer will be kept in a global variable and updated each time a new value is inserted into the tree. The idea is that when a new value is inserted into the tree, it passes through a certain path, and the nodes along this path will know exactly how many values exist that are less than the value passing through, so at these nodes the final answer can be updated appropriately.

Note that the final answer will only be updated if the new value is greater than the value on the current node (i.e. when it forwards the new value to the right sub-tree) - this is because you have the additional constraint i < j.

Hope this helps!

Asiri Rathnayake
  • 1,138
  • 1
  • 11
  • 27