Category Archives: Merge sort

Counting the number of inversions in a list

Given an array of numbers, how do we count the number of inversions in it?

An inversion is an ordered pair if indices (i,j) such that i < j and A[i] > A[j] .

For example consider the array {3, 2, 1, 5, 4}
The inversions are {(0,1), (0,2), (1,2), (3,4)} totaling 4.

We can always use the brute force approach of comparing all possible pairs of numbers to check if each pair is an inversion or not. This takes O(n2) time.

How do we solve this efficiently?

We can modify the merge sort procedure to count the number of inversions also!

Please check out my earlier post on Merge sort to understand how it works.

Here are the steps.
  • First count the inversions in the left part
  • Count the inversions in the right part
  • Count the inversions if they are merged using modified merge procedure
  • Adding the three counts gives the actual result 
We need to change the merge procedure to count the inversions. The merge procedure works like the following.

We have two sorted arrays to merge into another array.

{1, 3, 5, 7} + {2, 4, 6, 8} = {1, 2, 3, 4, 5, 6, 7, 8}
  • Take two pointers to start of the two arrays.
  • Compare the two elements to see which element goes to the sorted list first.
  • Increment the corresponding index.
  • Repeat the above steps until we reach the end of either of them.
  • Add the remaining elements if any.
While comparing the two elements if the left element is lesser than right element, we simply proceed.
If the right element is lesser than left elements, then it is also lesser than all elements to the right of left element. So increment the inversion counter accordingly.
For example
{…. 5, 9, 12, 15, …}
3 Appears in the right and 5 appears in left. So we can count all the inversions (5,3), (9,3), (12,3)… in this step itself.
Here is the C++ code which implements the above algorithm. The time complexity of this implementation is O(n log n).

    Maximum number of overlapping intervals

    Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time.

    For example let us consider the following intervals.

    { (0,2), (3, 7), (4,6), (7,8), (1,5) }

    The maximum number of intervals overlapped is 3 during (4,5).

    This can be asked in many forms in a programming competition. This CodeChef problem is one such an example. Go and test your knowledge if you have some idea about how to solve this.

    Let us look at the solution approaches.

    We first consider all the start and end point as a single entity and sort them in ascending order according the following criteria.
    • If the times are different, just sort according to time.
    • If the times are equal, we first place the end of interval.
    Then we take a counter and a maximum counter. 
    Iterate through all the points
    • If the point is start of interval we increment the counter.
      • Keep track of maximum counter
    • Otherwise we decrement the counter
    At the end of this, we have the required result in maximum counter.

    Another alternative solution could be to use the merge procedure used in merge sort. The steps are similar to the merge procedure.

    • Sort all the starting points and ending points in ascending order
    • Try to merge them into a single list
    • Use two variables overlap, and max_overlap to keep track of the current overlap and maximum overlap we have seen so far.
    • As long as we take element from starting point of the interval, increment overlap and update max_overlap.
    • If we are taking en element from ending point of the interval, decrement overlap.
    At the end of this procedure, we have the answer in max_overlap.

    Below is the simple C++ implementation of the above algorithms.