# Counting Inversions Challenge

**Problem Statement**

In an array, , the elements at indices and (where ) form an inversion if . In other words, inverted elements and are considered to be “out of order”. To correct an inversion, we can swap adjacent elements.

For example, consider the dataset . It has two inversions: and . To sort the array, we must perform the following two swaps to correct the inversions:

Given datasets, print the number of inversions that must be swapped to sort each dataset on a new line.

**Function Description**

Complete the function `countInversions`

in the editor below. It must return an integer representing the number of inversions required to sort the array.

`countInversions`

has the following parameter(s):

* `arr`

: an array of integers to sort.

**Input Format**

The first line contains an integer, , the number of datasets.

Each of the next pairs of lines is as follows:

1. The first line contains an integer, , the number of elements in .

- The second line contains space-separated integers, .

**Constraints**

*

*

*

**Output Format**

For each of the datasets, return the number of inversions that must be swapped to sort the dataset.

**Sample Input 1**

1 2 3 4 5 6 |
2 5 1 1 1 2 2 5 2 1 3 1 2 |

**Sample Output 1**

1 2 3 |
0 4 |

**Explanation**

We sort the following datasets:

1. is already sorted, so there are no inversions for us to correct. Thus, we print on a new line.

2.

We performed a total of swaps to correct inversions.

**Sample Input 2**

1 2 3 4 |
1 5 2 1 0 3 0 |

**Sample Output 2**

1 2 |
6 |

**Solution**

I will use Sample Input 2 as my solution sample input. The solution can be found in time.

The way I approach this problem is by first implementing the Merge Sort algorithm to sort the input array. The recursion tree for looks as follows:

Starting from the bottom of the tree, once the array can no longer be split, the arrays (left and right in red color) will be merged at each level of the tree:

Comparing each of the left and right sorted array (red) at each level we can see that the number of swaps we need to make is:

“the sum of counts of right items that are smaller than the current left item for each left item”. For example, comparing and we count for left item since . We also count for left item since . This is because we need to swap those pairs in order to sort the array. We do this at all levels to calculate the number of total swaps.

We can do this count during the merging of or left and right array. What we do is follows:

1. Once we stumble upon a left item that is larger than our right item, we set a flag that we need to start counting.

2. If the left item is again less than or equal to a right item and we started our count earlier, then the number of items smaller than our previous left (the one were we started our count) must be equal to the current `rightCursor`

in the right array. The later is because we know the left/right arrays are sorted and any left item will also be . The same goes for any subsequent left item that is (See comparison and ).

Finally, for any items left in the left array, we need to add , since each one of these left items is greater than all items in the right array.

**Code**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 |
package problems; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.*; public class NumberOfInversions { static long count = 0; static void merge(int[] arr, int low, int mid, int high) { int leftArraySize = mid - low + 1; int rightArraySize = high - mid; int[] left = Arrays.copyOfRange(arr, low, mid + 1); int[] right = Arrays.copyOfRange(arr, mid + 1, high + 1); int cursorLeft = 0; int cursorRight = 0; int arrCursor = low; boolean isCounting = false; int lastLeftItemForWhichWeCounted = -1; while (cursorLeft < leftArraySize && cursorRight < rightArraySize) { if (left[cursorLeft] <= right[cursorRight]) { if (isCounting || (lastLeftItemForWhichWeCounted != -1 && left[cursorLeft] >= lastLeftItemForWhichWeCounted)) { count += cursorRight; isCounting = false; } arr[arrCursor] = left[cursorLeft]; cursorLeft++; } else { arr[arrCursor] = right[cursorRight]; if (!isCounting) { isCounting = true; lastLeftItemForWhichWeCounted = left[cursorLeft]; } cursorRight++; } arrCursor++; } while (cursorLeft < leftArraySize) { arr[arrCursor] = left[cursorLeft]; count += rightArraySize; cursorLeft++; arrCursor++; } while (cursorRight < rightArraySize) { arr[arrCursor] = right[cursorRight]; cursorRight++; arrCursor++; } } static void mergeSort(int[] arr, int low, int high) { if (low < high) { int mid = (low + high) / 2; mergeSort(arr, low, mid); mergeSort(arr, mid + 1, high); merge(arr, low, mid, high); } } static long countInversions(int[] arr) { count = 0; mergeSort(arr, 0, arr.length - 1); return count; } public static void main(String[] args) throws FileNotFoundException { long startTime = System.currentTimeMillis(); System.setIn(new FileInputStream(System.getProperty("user.home") + "/" + "in4.txt")); Scanner scanner = new Scanner(System.in); int d = scanner.nextInt(); long[] answers = new long[d]; for (int i = 0; i < d; i++) { int n = scanner.nextInt(); int[] arr = new int[n]; for (int j = 0; j < n; j++) { arr[j] = scanner.nextInt(); } long ans = countInversions(arr); answers[i] = ans; } long endTime = System.currentTimeMillis(); System.out.println("Took " + (endTime - startTime) + " ms"); /* Verify Results */ Scanner resultScanner = new Scanner(new FileInputStream(System.getProperty("user.home") + "/" + "expected4.txt")); int cursor = 0; boolean correct = true; for (int i = 0; i < d; i++) { long expected = resultScanner.nextLong(); if (expected != answers[i]) { System.out.println("Expected " + expected + " got " + answers[i]); correct = false; break; } } if (correct) { System.out.println("Correct"); } else { System.out.println("Error"); } } } |