Merge Sort: Counting Inversions HackerRank Solution

Merge Sort: Counting Inversions HackerRank Solution
Source : https://www.hackerrank.com/challenges/ctci-merge-sort

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

2  5  1 1 1 2 2  5  2 1 3 1 2

Sample Output

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.

We performed a total of swaps to correct inversions.

Source : https://www.hackerrank.com/challenges/ctci-merge-sort

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	import java.util.Arrays;
	// We basically implement MergeSort and
	// 1) Add "swaps" counter and 1 line of code to count swaps when merging
	// 2) Use "long" instead of "int" to avoid integer overflow
	// Time Complexity: O(n log n)
	// Space Complexity: O(n)
	public class Solution {
	public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	int testcases = scan.nextInt();
	while (testcases-- > 0) {
	int n = scan.nextInt();
	int [] array = new int[n];
	for (int i = 0; i < n; i++) {
	array[i] = scan.nextInt();
	}
	MergeSort ms = new MergeSort();
	System.out.println(ms.mergeSort(array));
	}
	scan.close();
	}
	private static class MergeSort {
	/* Our array has up to n = 100,000 elements. That means there may be O(n^2) swaps.
	n^2 is 10,000,000,000. A Java int has max value 2,147,483,647 so we use a long
	to avoid integer overflow */
	private long swaps = 0;
	public long mergeSort(int [] array) {
	int [] helper = new int[array.length];
	mergeSort(array, helper, 0, array.length - 1);
	return swaps;
	}
	private void mergeSort(int [] array, int [] helper, int start, int end) {
	if (start < end) {
	int mid = (start + end) / 2;
	mergeSort(array, helper, start, mid);
	mergeSort(array, helper, mid + 1, end);
	merge(array, helper, start, mid, end);
	}
	}
	private void merge(int [] array, int [] helper, int start, int mid, int end) {
	/* Fill helper array with same elements as original array */
	for (int i = start; i <= end; i++) { // notice "i" goes from "start" to "end", not "0" to "array.length"
	helper[i] = array[i];
	}
	int curr = start;
	int left = start;
	int right = mid + 1;
	/* Loop through helper[] left and right halves and continuously copy smaller element to array[] */
	while (left <= mid && right <= end) {
	if (helper[left] <= helper[right]) {
	array[curr++] = helper[left++];
	} else {
	/* Each time we choose element from right side, we count up how many elements
	it is less than from left side. This is equivalent to counting swaps. */
	swaps += mid + 1 - left;
	array[curr++] = helper[right++];
	}
	}
	/* Copy remaining elements of left half. Right half elements are already in proper place */
	while (left <= mid) {
	array[curr++] = helper[left++];
	}
	}
	}
	}