0

I'm attempting to solve an algorithm question.

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

my first solution which doesn't satisfy O(N^2) uses nested loops:

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 

My attempt at converting to a list comprehension

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

I'm basing my solution on this link

I understand I'm not getting my syntax correctly, especially inv_count += 1 I have looked for examples where the nested loop needs to return a count and is written using list comprehension but I couldn't find any.

Ideally, the function should tell the number of inversions in an array like so;

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

#testdata

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

Output

Number of inversions are 5

with my current solution

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

#testdata

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

Output

Traceback (most recent call last):
  File "and.py", line 24, in <module>
    getInvCount(arr, n)) 
  File "and.py", line 16, in getInvCount
    inv_count += 1
TypeError: 'int' object is not iterable
6
  • 3
    Converting nested for loops to a comprehension with multiple fors won't improve this in terms of Big-O.
    – Mark
    Jun 5, 2019 at 22:56
  • 1
    Did you see this?
    – foxpal
    Jun 5, 2019 at 23:34
  • return sum([1 if (arr[i] > arr[j]) else 0 for i in range(n) for j in range(i+1,n)]) should work but won't be more efficient in terms of complexity Jun 6, 2019 at 1:56
  • thanks a lot @foxpal this helps me understand complexity very well.
    – Kenechukwu
    Jun 10, 2019 at 15:52
  • @MarkMeyer I didn't understand complexity very well, but Reddit has put me through ELI5 style, you are correct, it doesn't help since the goal is to reduce the for loops not add them to one line.
    – Kenechukwu
    Jun 10, 2019 at 15:54

1 Answer 1

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

should work as a list comprehension answer. I had referred this stackoverflow post a few months ago to do be able to do this.

In terms of time complexity, however, it won't be better than O(N^2).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.