CareerCup

Hint : Merge method of Merge sort !!!

<pre lang="python" line="1" title="CodeMonkey82035" class="run-this">def pair(l):
for x in xrange(len(l)):
a = l[x]
for b in l[x:]:
if a > b:
print (a,b)

if __name__ == '__main__':
pair([8,3,6,10,5])</pre>

Here is pseudocode:

var sortedArray = new Array();
var count = 0;

foreach b in array
{
// insert b in already sorted array and get position (staring from 1)
// running time is log(sortedArray.length)
// can be implemented like binary-search

var pos = insert(sortedArray, b);

// all the elements in sortedArray located after pos are > b
// so those elements can appear in pair with b

count += sortedArray.length - pos;
}

print(count);

// total running time is about NlogN

Read the input from left to right, and keep inserting numbers in a ht balanced binary tree....O(nlog(n))
Now while doing insertions, every time you go left(i.e. number to be inserted is less than the current number/node) increment a global counter...
Return the global counter

Good Work SE. Nice question and good soution..

Suppose the Array = {N+1, N, N-1, ..., 10, 9 , 8, 7, 6, 5, 4, 3, 2, 1}
there are N(N+1)/2 array. to print these array need O(N^2);
So, the worst case to find these pairs is still equal to O(N^2).

Not sure if i got it correctly.
Lets take an example {3, 2, 1}
3 GC=0, IC (3)=0
3, 2 GC=1 IC(3)=0, IC(2)=0
3, 2, 1 GC=2, IC(3)=0, IC(2)=0, IC(1)=0

Ans =GC=2, but it is incorrect..answer should be 3 and the pairs would be {3,2}, {3,1}, {2,1}

Did i interpret the solution incorrectly?

I don't understand why people LIKE to think a simple problem in complicated manner, like RB tree/other balanced tree which is pretty hard to implement for such simple problem!

It's a simple merging technique (like merge sort as pointed out by someone on June 20 post). This problem is taken from Cormen exercise (2-4).

An illustrative solution is given here:
geeksforgeeks.org/?p=3968

Cant we solve it this way:
Begin creating a tree. In the beginning, count is zero. Every time a left path is chosen, increase the count and that becomes the answer.

Cant we solve it this way:
Begin creating a BST tree. In the beginning, count is zero. Every time a left path is chosen, increase the count and that becomes the answer.

1. RB tree is simple in Java.
2. only the number of pair is required

my solution in java is simple. O(nlgn) for sorting.

public void treeSolution(int[] orig) {
        TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
        int[] pos = new int[orig.length];
        for (int i = 0; i < orig.length; i++){
            tree.put(orig[i], i);
        }
        int i = 0;
        for (Map.Entry<Integer, Integer> entry : tree.entrySet()) {
            pos[i++] = entry.getValue();
        }

        int count = 0;
        for (int j : pos){
            if (pos[j] > j) {
                count += pos[j] - j;
            }
        }
        System.out.println("total count: " + count);

    }

The count is nothing but called conversion is an array. Consider them the number of pairs which needs to be swapped to make the array sorted. There is a modified version of merge sort to do this in O (nlogn) time.Its one of the back problem of Cormen. We did it in our algo class.

You can use the dayastructure called Binary Index Tree
It has a very simple 6 line implementation in C/C++.
And this problem in counting the number of inversions.

Just sort the array in increasing order and then binary search for each element. This way you could find the number of element greater than a given element in logn time. Do this for all n elements.
So sorting takes O(nlogn) time
n binary search takes O(nlogn) time
so overall time complexity is O(nlogn)

Just count the number of inversions.. there's a O(nlogn) solution for that, using divide and conquer.

mergesort is ok~~~

hi I think its a variation of longest in/decreasing subsequence....

No it is not a variation of longest increasing subsequence instead as pointed out earlier, this requires just a slight modification of the merge method in merge sort.

Our purpose when we compare now is to see what elements are "out of order" so to speak and output them.. we dont want to sort them. This will take nlogn.