# Counting Inversions Coding Problem

May 19, 2019

** Inversion There is an array(a) and two indexes i and j. Inversion is the element for whom i < j and a[i] > a[j]

Example:

``````2 6 5 4 8

# Inversion pairs
(6, 5) (6, 4) (5, 4)

# Total inversion = 3``````

## Counting Inversion Algorithm - Brute Force - O(n^2)

Lets look at simple brute force algorithm:

``````public void calculate_bad(int[] arr) {
int count = 0;
for (int i=0; i<arr.length-1; i++) {
for (int j=i+1; j<arr.length; j++) {
if (arr[i] > arr[j]) {
count ++;
System.out.println(arr[i] + " " + arr[j]);
}
}
}
System.out.println("Total inversions: " + count);
}``````

Above is a simple algorithm. Lets think about optimizing this.

## Thoughts about Optimizing Algorithm

Next better number than O(n^2) is O(n log n) Can we do it in O(n log n)? Can we apply divide and conquer algorithm in this? If somehow, we can think what we will achieve by dividing the input array?

Hint Can we use Merge Sort? Yes

How In function where we merge two sorted sub-problems. Before sorting, their positions are actually relatively left and right which we want. The advantage of using merge sort is that, we know each of left and right array is sorted.

So, while comparing, one thing is for sure. For every element in left array, the index-i is always lesser than the index from right sorted sub-array. If we know, that one element in left sub-array which is greater than an element from right array.

In above image, we know in left array that index=4 element is greater than element in right array at index=2 WHat it means, we found one inversion pair. In addition to that, we know every element in left array from index=4 onwards will be greater than element in right array where we found at index=2 Which means, in above example, we found total 3 inversion pairs for this condition.

And, we keep on continuing like this.

## The code of algorithm taking O(n log n)

``````private void calculate_good_recursive(int[] arr, int l, int m, int r) {
int l1 = m-l+1;
int l2 = r-m;

int[] left = new int[l1];
for (int i=0; i<l1; i++) {
left[i] = arr[l+i];
}

int[] right = new int[l2];
for (int i=0; i<l2; i++) {
right[i] = arr[m+i+1];
}

int lindex = 0;
int rindex = 0;
while (lindex < l1 && rindex < l2) {
if (right[rindex] < left[lindex]) {
for (int jj=lindex; jj<l1; jj++) {
System.out.println(left[jj] + " " + right[rindex]);
}
}

if (left[lindex] <= right[rindex]) {
arr[l] = left[lindex];
lindex ++;
}
else {
arr[l] = right[rindex];
rindex ++;
}

l++;
}
while (lindex < l1) {
arr[l] = left[lindex];
l++; lindex ++;
}
while (rindex < l2) {
arr[l] = right[rindex];
l++; rindex ++;
}
}

public void inversions_merge_sort_method(int[] arr, int l, int r) {
if (l < r) {
int m = (l+r)/2;
inversions_merge_sort_method(arr, l, m);
inversions_merge_sort_method(arr, m+1, r);

calculate_good_recursive(arr, l, m, r);
}
}``````

## Similar Posts

### Leetcode - Split a String Into the Max Number of Unique Substrings

Problem Statement Given a string s, return the maximum number of unique…

### Reverse digits of a signed integer - Leet Code Solution

Problem Statement Given a signed integer, reverse digits of an integer. Return…

### What FAANG companies expect in their interview from candidates

Its every software engineer’s dream to work with the big FAANG companies…

### Convert String to Integer - atoi - Leet Code Solution

Problem Statement Implement atoi which converts a string to an integer…

### Two Sum Problem - Leet Code Solution

Problem Statement Given an array of integers, return indices of the two numbers…

### Longest Common Prefix - Leet Code Solution

Problem Statement Write a function to find the longest common prefix string…

## Latest Posts

### Jenkins Pipeline with Jenkinsfile - How To Schedule Job on Cron and Not on Code Commit

Introduction In this post we will see following: How to schedule a job on cron…

### How to Git Clone Another Repository from Jenkin Pipeline in Jenkinsfile

Introduction There are some cases, where I need another git repository while…

### How to Fetch Multiple Credentials and Expose them in Environment using Jenkinsfile pipeline

Introduction In this post, we will see how to fetch multiple credentials and…

### Jenkins Pipeline - How to run Automation on Different Environment (Dev/Stage/Prod), with Credentials

Introduction I have an automation script, that I want to run on different…

### Jenkinsfile - How to Create UI Form Text fields, Drop-down and Run for Different Conditions

Introduction I had to write a CICD system for one of our project. I had to…

### Java Log4j Logger - Programmatically Initialize JSON logger with customized keys in json logs

Introduction Java log4j has many ways to initialize and append the desired…
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}