We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Merge Sort: Counting Inversions
  2. Discussions

Merge Sort: Counting Inversions

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 474 Discussions, By:

votes

Please Login in order to post a comment

  • RachelAF
    5 years ago+ 20 comments

    Make sure that you use a long to track the swaps! If you use an int, you'll get the wrong answer due to integer overflow in the last third or so of the cases.

    306|
    Permalink
    View more Comments..
  • djv
    6 years ago+ 43 comments

    In case you're struggling with Python timing out on the last 3 test cases. Just switch to PyPy as the language, you can use the same code but it runs faster. Assuming you've implemented the O(n Log n) algorithm then all the tests will pass.

    196|
    Permalink
    View more Comments..
  • andras_igneczi
    6 years ago+ 11 comments

    I don't realy understand the example. Why do we have to do 4 swaps in case of this array: 2 1 3 1 2? If we swap

    a[0] <-> a[3] ==> 1 1 3 2 2, and

    a[2] <-> a[4] ==> 1 1 2 2 3,

    we can get the sorted array.

    72|
    Permalink
    View more Comments..
  • hotshot47
    5 years ago+ 3 comments

    I don't understand how this problem is a mergesort. It is more of a bubblesort, as it is doing adjacent element swaps if not in order. For mergesort, while merging two halves, we compare the numbers at any given index and pick the lowest number to reconstruct the array. Which is not a swap operation explained in the problem statement. I understand mergesort has better runtime but the problem is confusing and conflicting.

    58|
    Permalink
  • weeebox
    6 years ago+ 6 comments

    A great explanation by Tim Roughgarden can be found on Coursera: https://www.coursera.org/learn/algorithm-design-analysis

    Check: Week 1, O(n log n) Algorithm for Counting Inversions I, II

    We can avoid allocating and copying multiple arrays by using a single aux array of size n (where n is the size of the original array). Both arrays are switched on each recursive call.

    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class Solution {
    
        private static long countInversions(int[] arr) {
            int[] aux = arr.clone();
            return countInversions(arr, 0, arr.length - 1, aux);
        }
    
        private static long countInversions(int[] arr, int lo, int hi, int[] aux) {
            if (lo >= hi) return 0;
    
            int mid = lo + (hi - lo) / 2;
    
            long count = 0;
            count += countInversions(aux, lo, mid, arr);
            count += countInversions(aux, mid + 1, hi, arr);
            count += merge(arr, lo, mid, hi, aux);
    
            return count;
        }
    
        private static long merge(int[] arr, int lo, int mid, int hi, int[] aux) {
            long count = 0;
            int i = lo, j = mid + 1, k = lo;
            while (i <= mid || j <= hi) {
                if (i > mid) {
                    arr[k++] = aux[j++];
                } else if (j > hi) {
                    arr[k++] = aux[i++];
                } else if (aux[i] <= aux[j]) {
                    arr[k++] = aux[i++];
                } else {
                    arr[k++] = aux[j++];
                    count += mid + 1 - i;
                }
            }
    
            return count;
        }
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int t = in.nextInt();
            for(int a0 = 0; a0 < t; a0++){
                int n = in.nextInt();
                int arr[] = new int[n];
                for(int arr_i=0; arr_i < n; arr_i++){
                    arr[arr_i] = in.nextInt();
                }
                System.out.println(countInversions(arr));
            }
        }
    }
    
    30|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature