Count Inversions

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
693 upvotes
Asked in companies
AmazonMicrosoftInfosys

Problem statement

For a given integer array/list 'ARR' of size 'N' containing all distinct values, 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').
Detailed explanation ( Input/output format, Notes, Images )
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.
Note: 
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
Sample Input 1 :
3
3 2 1
Sample Output 1 :
3
Explanation of Sample Output 1:
We have a total of 3 pairs which satisfy the condition of inversion. (3, 2), (2, 1) and (3, 1).
Sample Input 2 :
5
2 5 1 3 4
Sample Output 2 :
4
Explanation of Sample Output 1:
We have a total of 4 pairs which satisfy the condition of inversion. (2, 1), (5, 1), (5, 3) and (5, 4).


Hints:
1. Start with the brute force approach.
2. Use a modified merge sort.
3. Iterate through the elements in sorted order and use a Fenwick tree to track the inversions.
Approaches (3)
Brute Force Approach

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’.
Time Complexity

O(N ^ 2), Where ‘N’ is the total number of elements in the array.

 

Since for every element, we iterate over the remaining elements on right side, which makes it polynomial time. Thus the time complexity will be O(N ^ 2).

Space Complexity

O(1).

 

Since constant space is used. Thus the space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Count Inversions
Full screen
Console