Counting the pairs in a list such that their first index is less than the second but the first element is greater than the second

user_15594461 0
Viewed 540

I have the list [5,2,10,9,7].
I want to count all the pairs that satisfy the condition ( i<j and list[i]>list[j] )
For example, the index of 5 is less than the index of 2 but 5 is greater than 2 so increase the counter by 1 and the same for (10,9) and (10,7)and (9,7) so the value of the counter will be 4

I have solved the problem but with complexity O(n^2), but I want to find a solution with the lowest time complexity.

This is the code that runs on O(n^2)

 def ques(lista):
     b=0
     for i in range (len(lista)):
        for j in range (1,len(lista)):
            if i<j and lista[i]> lista[j] : 
                b+=1
     return b
time-complexity list python
2 Answers

Mergesort should be able to do this in O(nlogn). During the merge process, when we have to merge the left and the right array, we compare the first elements of both the arrays, if first element of the right array is less than the current first array of the left array, pop it, add it to a new temp array. Also increment the counter by the length of the left array (since all the elements in the left array are greater but have a smaller index).

def mergeSort(a):
    if len(a) >= 2:
        mid = len(a)//2
        left, right = mergeSort(a[:mid]), mergeSort(a[mid:])
        temp = []
        i, j = 0, 0
        for _ in range(len(a)):
            if i < len(left) and j < len(right):
                if  right[j] < left[i]:
                    temp.append(right[j])
                    # here we are counting are our pairs
                    counter[0] += len(left)-i
                    j += 1
                else:
                    temp.append(left[i])
                    i += 1
            elif i < len(left):
                temp.append(left[i])
                i += 1
            else:
                temp.append(right[j])
                j += 1
        return temp
    else:
        return a


counter = [0]
arr = [5, 2, 10, 9, 7]
mergeSort(arr)
print(counter[0])
user_110169870

I don't think it can be done in less than O(n^2):

The fact that each element should be compared with all the elements that come after it means that for the first element we'll need: n-1 comparisons, for the following element we'll need n-2 comparisons an so on.

(n-1) + (n-2) + (n-3) + ... + 2 + 1 => order of n^2
user_10574290
Related