Algorithm Question By Google

github logo ・1 min read

QUESTION

We can determine how "out of order" an array A is by counting the number of inversions it has.

Two elements A[i] and A[j] form an inversion if A[i] > A[j] but i < j.
That is, a smaller element appears after a larger element.

CHALLENGE

Given an array, count the number of inversions it has. Do this faster than O(N2) time.

You may assume each element in the array is distinct.

For example, a sorted list has zero inversions.
The array [2, 4, 1, 3, 5] has three inversions: (2, 1), (4, 1), and (4, 3).
The array [5, 4, 3, 2, 1] has ten inversions: every distinct pair forms an inversion.

twitter logo DISCUSS (3)
markdown guide
 

Hi @theghostyced . so I decided to try and solve this on my own and I want to share my insights

my first solution was to write some logic google the question and I came across a solution that didn't satisfy the complexity

def getInvCount(arr, n): 

    inv_count = 0
    for i in range(n): 
        for j in range(i + 1, n): 
            if (arr[i] > arr[j]): 
                inv_count += 1

    return inv_count 

I then tried to rewrite this using list comprehension, you can see my effort here

def getInvCount(arr, n):
    return sum([1 if (arr[i] > arr[j]) else 0 for i in range(n) for j in range(i+1,n)]) 

but this also revealed the answers which you can use to solve this question.

 

Thanks @areahints but I think the time complexity still remains the same irrespective of the list comprehension.

 

yes, I mentioned that my list comprehension didn't satisfy the complexity.

consider this solution;

def getInvCount(arr,n):
    return mergeGetInvCount(arr)[1]

def mergeGetInvCount(arr):
    if len(arr) <= 1:
        return arr, 0
    middle = int(len(arr) / 2)
    left, a = mergeGetInvCount(arr[:middle])
    right, b = mergeGetInvCount(arr[middle:])
    result, c = mergeGetSplitInvCount(left, right)
    return result, (a + b + c)

def mergeGetSplitInvCount(left, right):
    result = []
    count = 0
    i,j = 0,0
    left_len = len(left)
    while i < left_len and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            count += left_len - i
            j += 1
    result += left[i:]
    result += right[j:]
    return result, count   

# Driver Code
arr = [1, 20, 6, 4, 5] 
n = len(arr) 
print("Number of inversions are", getInvCount(arr,n))

Output

Number of inversions are 5

that's an O(n log n) implementation that I mentioned has been revealed in the link. did you read through it?

Classic DEV Post from Jan 20

What do you do to practice new programming languages and/or frameworks?

What to do to practice and learn new technologies when you don't have any creativity for projects?

CED profile image
A software developer smashing keyboards at Andela. I read 📚 to know, I write ✍️ to recall.

A blogging community of over 100,000 software developers Join dev.to