Count Inversions

Posted: 10 Jan, 2017
Difficulty: Moderate


Try Problem

For a given integer array/list 'ARR' of size 'N', find the total number of 'Inversions' that may exist.

An inversion is defined for a pair of integers in the array/list when the following two conditions are met.

A pair ('ARR[i]', 'ARR[j]') is said to be an inversion when:

1. 'ARR[i] > 'ARR[j]' 
2. 'i' < 'j'

Where 'i' and 'j' denote the indices ranging from [0, 'N').
Input format :
The first line of input contains an integer 'N', denoting the size of the array.

The second line of input contains 'N' integers separated by a single space, denoting the elements of the array 'ARR'.
Output format :
Print a single line containing a single integer that denotes the total count of inversions in the input array.
You are not required to print anything, it has been already taken care of. Just implement the given function.  
Constraints :
1 <= N <= 10^5 
1 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the array element at 'ith' index.

Time Limit: 1 sec
Approach 1

The steps are as follows:


  1. Initialize a ‘COUNT’ with 0 to keep track of the number of inversions
  2. Iterate over every element in the array in a linear fashion starting from 0.
  3. For every element, check all the elements ahead of the current element and check the condition.
    1. If the condition satisfies, increase the ‘COUNT’ by 1.
    2. Otherwise, move to the next iteration.
  4. Return the ‘COUNT’.
Try Problem