Friday, December 16, 2011

How to: array inversion count

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum. 

Formal solution to solve is:
Given is an array A of N integers. Inversion is a pair of indexes (P, Q) such that P < Q and A[Q] < A[P].

Write a function

class Solution { public int array_inversion_count(int[] A); }

which computes the number of inversions in A, or returns -1 if such number exceeds 1,000,000,000.

Assume that:

        N is an integer within the range [0..100,000];
        each element of array A is an integer within the range [-2,147,483,648..2,147,483,647].

For example, in the following array

    A[0] = -1 A[1] = 6 A[2] = 3
    A[3] =  4 A[4] = 7 A[5] = 4

there are four inversions:

      (1,2)  (1,3)  (1,5)  (4,5)

so the function should return 4.


        expected worst-case time complexity is O(N*log(N));
        expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

import java.math.*;
class Solution {
public int array_inversion_count ( int[] A ) {
// write your code here

int n = A.length;
int counter = 0;
for(int p = 0; p < n - 1; p++) 

      for(int q = p+1; q < n; q++) 
         if( A[p] > A[q] ) counter++;
   return counter;


  1. can you convert this to either Javascript, Python or Objective-c?

    1. No problem, javascript code should look very similar. I will assign it. Regarding Python, I do not know it, sorry. I can also post C/C++ code if it can help you, I don't know if Objective-c has much different syntax :)

  2. Here, worst case of time complexity is O(n^2).
    you code is good.

  3. Code you have posted has running time of O(n^2) not O(n.logn)