CODEWITHSUNDEEP
algorithm
abc
abc

Reputation: 2381

Inversion distance

First of all let's recall definition of inversion.

Inversion of some sequence S which contains numbers is situation when S[i] > S[j] and i < j or frankly speaking it's situation when we have disordered elements. For instance for sequence:

1 4 3 7 5 6 2

We have following inversions (4,3), (4,2), (3,2), (7,5), etc.

We state problem as follows: distance of inversion is maximum (in terms of indexing) distance between two values that are inversion. For out example we can perform human-brain searching that gives us pair (4,2) <=> (S[1], S[6]) and there for index distance is 6-1 = 5 which is maximum possible for this case.

This problem can be solved trivial way in O(n^2) by finding all inversions and keeping max distance (or updated if we find better option) We can also perform better inversion searching using merge sort and therefore do the same in O(nlogn). Is there any possibility for existence of O(n) algorithm? Take in mind that we just want maximum distance, we don't want to find all inversions. Elaborate please.

Upvotes: 2

Views: 949

Answers (2)

Obaida.Opu
Obaida.Opu

Reputation: 464

Maybe my idea is the same as @Evgeny. Here is the explanation:

make a strictly increasing array from the beginning we call it array1
make a strictly decreasing array from the ending which is array2 (But keep the values in increasing order)

***Keep track of original indexes of the values of both arrays.

Now start from the beginning of both arrays.

Do this loop following untill array1 or array2 checking is complete

    While( array1[index] > arry2[index] )
    {
        check the original distance between array1 index and arry2 index.
        Update result accordingly.
        increase array2 index.
    }
    increase both array index

Continue with the loop

At the end of this process you will have the maximum result. Proof of this solution is not that complex, you can try it yourself.

Upvotes: 1

Evgeny Kluev
Evgeny Kluev

Reputation: 24677

Yes, O(n) algorithm is possible.

We could extract strictly increasing subsequence with greedy algorithm:

source:                          1 4 3 7 5 6 2
strictly increasing subsequence: 1 4   7

Then we could extract strictly decreasing subsequence going backwards:

source:                          1 4 3 7 5 6 2
strictly decreasing subsequence: 1           2

Note that after this strictly decreasing subsequence is found we could interpret it as increasing sequence (in normal direction).

For each element of these subsequences we need to store their index in source sequence.

Now "inversion distance" could be found by merging these two subsequences (similar to merge sort mentioned in OP, but only one merge pass is needed):

merge 1 & 1 ... no inversion, advance both indices
merge 4 & 2 ... inversion found, distance=5, should advance second index,
                but here is end of subsequence, so we are done, max distance = 5

Upvotes: 1

Related Questions