Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Counting Inversions Challenge

Sharing is caring!

Problem Statement
In an array, arr, the elements at indices i and j (where i < j) form an inversion if arr\left[i\right] < arr\left[j\right]. In other words, inverted elements arr\left[i\right] and arr\left[j\right] are considered to be “out of order”. To correct an inversion, we can swap adjacent elements.

For example, consider the dataset arr=\left[2,4,1\right]. It has two inversions: (4,1) and (2,1). To sort the array, we must perform the following two swaps to correct the inversions:

Given d 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, d, the number of datasets.

Each of the next d pairs of lines is as follows:
1. The first line contains an integer, n, the number of elements in arr.

  1. The second line contains n space-separated integers, arr\left[i\right].

Constraints
* 1 \le d \le 15
* 1 \le n \le 10^5
* 1 \le arr\left[i\right] \le 10^7

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

Sample Input 1

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

Sample Output 1

0  
4

Explanation
We sort the following d=2 datasets:
1. arr=\left[1,1,1,2,2\right] is already sorted, so there are no inversions for us to correct. Thus, we print 0 on a new line.
2. arr=\left[2,1,3,1,2\right] \rightarrow 1 swap \rightarrow arr=\left[1,2,3,1,2\right]\rightarrow 2 swaps\rightarrow arr=\left[1,1,2,3,2\right]\rightarrow 1 swap\rightarrow arr=\left[1,1,2,2,3\right]
We performed a total of 1+2+1=4 swaps to correct inversions.

Sample Input 2

1
5
2 1 0 3 0

Sample Output 2

6

Solution
I will use Sample Input 2 as my solution sample input. The solution can be found in \mathcal{O}(nlogn) time.

The way I approach this problem is by first implementing the Merge Sort algorithm to sort the input array. The recursion tree for arr=\left[2,1,0,3,0\right] 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 \left[0,1,2\right] and \left[0,3\right] we count 1 for left item 1 since 1 > 0. We also count 1 for left item 2 since 2 > 0. 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 left\left[leftCursor\right] > right\left[rightCursor\right] will also be left\left[leftCursor\right] > right\left[rightCursor-1\right] > right\left[rightCursor-2\right] > \dots > right\left[0\right]. The same goes for any subsequent left item that is left\left[leftCursor\right] > lastLeftItemForWhichWeCounted (See comparison \left[0,1,2\right] and \left[0,3\right]).

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

Code

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");
        }
    }
}