Count Inversions
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'

Question

Count Inversions

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').

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

Accepted Answer

First I gave a Brute force solution using two nested Loops and trying out all pairs, which Interviewer asked me to optimize.
I asked about the constraints of elements occurring in the array , it was given that each arr[i]<=10^5
Step 1 -> Declare a Binary Indexed Tree of size equal to maximum element occurring in array
Step 2- > Traverse array from end till start (N-1 index till 0) and at each step if the element currently is x , find prefix sum of BIT Tree till index x which will tell the number of smaller elements smaller than arr[i] in the right of it ( which exactly is the meaning of inversions).
Step 3 -> return the count of inversions at end.

Another Solution when arr[i]<=10^9
Using Merge Sort to count Inversions

Accepted Answer

Brute Force Approach

The steps are as follows:

Initialize a ‘COUNT’ with 0 to keep track of the number of inversions
Iterate over every element in the array in a linear fashion starting from 0.
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.
Return the ‘COUNT’.

Space Complexity: O(1)Explanation:

O(1).

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

Time Complexity: O(n^2)Explanation:

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).

Accepted Answer

Merge Sort Approach

The steps are as follows:

The idea is similar to merge sort, divide the array from the middle to two parts, say, left sub-array and right sub-array.
Write a logic that counts the number of inversions when the arrays, namely, left sub-array and right sub-array are merged. The idea is to have two indices or pointers. One of the pointers will refer to the left sub-array and the other one will point to the right sub-array. Let’s call them ‘LEFTINDEX’ and ‘RIGHTINDEX’ such that:
- ‘LEFTINDEX' < ‘RIGHTINDEX’ and
- 'LEFTSUBARRAY[LEFTINDEX]' > 'RIGHTSUBARRAY[RIGHTINDEX]'
We can deduce major information from this configuration. We can say, there would be ('MID' - ‘LEFTINDEX’) inversions, where ‘MID’ is the index from where the array has been split into two. (We can say so because all the remaining elements in the left-subarray ('LEFTSUBARRAY[LEFTINDEX+ 1]', ‘LEFTSUBARRAY[LEFTINDEX+ 2]’ ….. ‘LEFTSUBARRAY[MID]’) will be greater than ‘RIGHTSUBARRAY[RIGHTINDEX]’)
Extend the same idea to calculate the number of inversions in the left sub-array and right sub-array.

Space Complexity: O(n)Explanation:

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

Since we are using a temporary array of size N at each of the merge of two subarray. Thus the space complexity will be O(N).

Time Complexity: O(nlogn)Explanation:

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

Since at each level one full array traversal is needed and there are log(N) levels as we are making each of the subarray half. Thus the time complexity will be O(N * log(N)).

Accepted Answer

Fenwick Tree

In this approach, we will create a Fenwick tree with every element having value 0 and map the given array to get the position of every element according to sorted order and then iterate through the positions and update the Fenwick tree to 1 for every element.

The steps are as follows:

In the Main Function:
- Create an array “mask” in which we will store every element in the form of permutation of numbers from 1 to n having the same relative order of every element as of the original array.
- For example, if your original array is {3, 22, 11, 5} then your “masked” array must be like {1, 4, 3, 2}.
- Create an array “fenwick” of size ‘n’ and initialize it to zero. Denoting that we have not encountered any element from the array and as we encounter that element we will update it to 1 by “fenwickUpdate” function.
- Take a variable “answer” to store the final answer.
- Now iterate through the array “mask” from 0 to n-1(say iterator be i):
  - Call the function “fenwickSum(mask[i], fenwick)” and add the value returned by this function to “answer”.
  - Now call the function “fenwickUpdate(mask[i], mask.size(), fenwick).
- Return “answer”.
In the “fenwickSum” function:
- This function will help us to sum all the elements which are greater than the current element but have an index lower than the current index.
- Take a variable “answer” in which we will keep count of those elements.
- “Index” will be the value that was passed to this function in our case it is “mask[i]”.
- While “index” is greater than 0:
  - Add “fenwick[index]” to “answer”.
  - Update “index” to “index” - (“index” & (- “index”)).
- Return “Sum”.
In the “fenwickUpdate” function:
- In this function, we will update the values of elements that have been visited to be 1.
- Take a while loop till “index” is less than size of array:
  - Update “fenwick[index]” = 1.
  - Update “index” to “index” + (“index” & (- “index”)).

Space Complexity: O(n)Explanation:

O( N ), where N is the size of the array.

As we are taking an array “fenwick” of size N.

Hence the total Space complexity is O( N )

Time Complexity: O(nlogn)Explanation:

O( N * log( N ) ), where N is the size of the array.

Since we are using a Fenwick tree that updates or queries in log( N ).

Hence the total time complexity is O( N * log( N ) )

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.

Input format :

Output format :

Note:

Constraints :

Top Amazon Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Amazon Software Developer