CareerCup

Merge sort with tweak will do it;

Assume we have the following numbers, for each number we also define a "value" which is the number of items greater than me with a bigger index, this value is initialized to zero
16, 17, 9, 0, 19, 24, 3, 8,

Now I explain the last step of the merge sort, here's what I have

{number=0 value=0 },{number=9 value=0 },{number=16 value=1 },{number=17 value=0 }
{number=3 value=1 },{number=8 value=0 },{number=19 value=1 },{number=24 value=0 }

- Pick "0": 0 is less than 3, so it's less than 4 elements in the second half, so it's value is insreased by 4
- Pick "3": it's from the second half, do nothing
- Pick "8": it's from the second half, do nothing
- Pick "9": 9 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "16": 16 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "17": 17 is smallet than 2 elements in the second half, so it's value is insreased by 2
- Pick "19": it's from the second half, do nothing
- Pick "24": it's from the second half, do nothing

Here is the final result
(0 , 4)
(3 , 1)
(8 , 0)
(9 , 2)
(16 , 3)
(17 , 2)
(19 , 1)
(24 , 0)

Here's the code

struct number_t
{
   int number;
   int value;
};

std::vector<number_t> temp_array;

void MergeSort( std::vector<number_t>* input, int start, int end )
{
   if ( start == end )
   {
      return;
   }

   int middle = floor((double)(start+end)/2);

   MergeSort( input, start, middle );
   MergeSort( input, middle+1, end );
   
   temp_array.clear();
   int i = start;
   int j = middle+1;
   
   while ( ( i <= middle ) && ( j <= end ) )
   {
      if ( input->at(i).number < input->at(j).number )
      {
         input->at(i).value += ( end - j + 1 ); // this is MAGIC line added to merge sort
         temp_array.push_back( input->at(i) );
         i++;
      }
      else
      {
         temp_array.push_back( input->at(j) );
         j++;
      }
   }

   //copying the rest
   while ( i <= middle )
   {
      temp_array.push_back( input->at(i) );
      i++;
   }

   while ( j <= end )
   {
      temp_array.push_back( input->at(j) );
      j++;
   }

   //Now copy on the input array
   for ( i = start ; i <= end ; i++ )
   {
      input->at(i) = temp_array[ i - start];
   }
}

One way to solve this with time complexity less than O(n^2) is to use a self balancing BST. AVL, Redblack etc.., can be used to get the solution in O(n Log n) time complexity

Initially we traverse the given array from right to left and insert all elements one by one in an AVL tree. While inserting a new key in an AVL tree, we first compare the key with root. We add it to the left / right accordingly and count the number of elements that are greater. We recursively follow the same approach for all nodes down the root.

#include <stdio.h>
#include <stdlib.h>

struct node {
    int key;
    struct node *left;
    struct node *right;
    int height;
    int size;
};

int min(int a, int b);

int height(struct node *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

int size(struct node *N) {
    if (N == NULL)
        return 0;
    return N->size;
}

int min(int a, int b) {
    return (a < b)? a : b;
}

struct node* newNode(int key) {
    struct node* node = (struct node*)
    malloc(sizeof(struct node));
    node->key   = key;
    node->left   = NULL;
    node->right  = NULL;
    node->height = 1;
    node->size = 1;
    return(node);
}

struct node *rightRotate(struct node *y) {
    struct node *x = y->left;
    struct node *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = min(height(y->left), height(y->right))+1;
    x->height = min(height(x->left), height(x->right))+1;

    y->size = size(y->left) + size(y->right) + 1;
    x->size = size(x->left) + size(x->right) + 1;

    return x;
}

struct node *leftRotate(struct node *x) {
    struct node *y = x->right;
    struct node *T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = min(height(x->left), height(x->right))+1;
    y->height = min(height(y->left), height(y->right))+1;

    x->size = size(x->left) + size(x->right) + 1;
    y->size = size(y->left) + size(y->right) + 1;

    return y;
}

int getBalance(struct node *N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

struct node* insert(struct node* node, int key, int *count) {
    if (node == NULL)
        return(newNode(key));

    if (key > node->key)
        node->left  = insert(node->left, key, count);
    else
    {
        node->right = insert(node->right, key, count);
        *count = *count + size(node->left) + 1;
    }

    node->height = min(height(node->left), height(node->right)) + 1;
    node->size   = size(node->left) + size(node->right) + 1;

    int balance = getBalance(node);

    if (balance > 1 && key > node->left->key)
        return rightRotate(node);

    if (balance < -1 && key < node->right->key)
        return leftRotate(node);

    if (balance > 1 && key < node->left->key)
    {
        node->left =  leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && key > node->right->key)
    {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

void constructHigherArray (int arr[], int countHigherElements[], int n) {
  int i, j;
  struct node *root = NULL;

  for  (i = 0; i < n; i++)
   countHigherElements[i] = 0;

    for (i = n-1; i >= 0; i--)
    {
       root = insert(root, arr[i], &countHigherElements[i]);
    }
}

void printArray(int arr[], int size) {
  int i;
  printf("\n");
  for (i=0; i < size; i++)
    printf("%d ", arr[i]);
}

int main() {
    // int arr[] = {3,4,5,9,2,1,3};
    int arr[] = {10, 6, 15, 20, 30, 5, 7, 3, 4, 5, 9, 2, 1, 3};
    int n = sizeof(arr)/sizeof(arr[0]);

    int *low = (int *)malloc(sizeof(int)*n);

    constructHigherArray(arr, low, n);

    printf("Following is the constructed larger count array");
    printArray(low, n);
    return 0;
}

inline void update(int u)
{
while(u<=n)
{
val[u]++;
u+=(u&-u);
}
}
inline int sum(int u)
{
int ret = 0;
while(u>0) {
ret += val[u]; u-=(u&-u);
}
return ret;
}
first step is using map change (a[1],a[2],.....,a[n]) to any permutation of (1,2,....n).
second step. According to below source code.
for(int i=n; i>0; i--) {
/* Binary Indexed Tree */
update(a[i]);
int cnt = sum(a[i]); // cnt is number of less than a[i].
answer is print("%d ",n-i+1-cnt);
}

Time limit is n * (log(n) + log(n));

Hello. Did you try to iterate from the last element to the first and keep track elements in stack?

input: int[] arr;

1. int[] sorted=Sort(arr)  -> o(n log (n))
2. Foreach i                -> o(n)
	out[i]=arr.length-1-findIndex(sorted, arr[i])   -> o(log (n))
3. return out;

The findIndex method must return the biggest index in the array that has the value.

c++, implementation, O(n^2)
Loop: O(n), distance: O(n). This is not fast solution.

vector<int> remainGreaterCount(vector<int>& arr) {
	multiset<int> s;
	multiset<int>::iterator it;
	vector<int> result;
	int i, j;

	result.assign(arr.size(), 0);
	for (i = arr.size() - 1; i >= 0; i--) {
		s.insert(arr[i]);
		it = s.upper_bound(arr[i]);
		result[i] = distance(it, s.end());
	}

	return result;
}

public class Node
{
	int value;
	int count;
	Node left;
	Node right;
	Node(int v,int c)
	{
		value=v;
		count=c;
	}
}

public Node insert(int v,Node n)
{
	if(n==null)
	{
		n=new Node(v,1);
		return n;
	}
	Node rt=n;
	Node p=rt;
	while(n!=null)
	{
		if(v<=n.value)
		{
			p=n;
			n=n.left;
			
		}
		else
		{
			n.count++;
			p=n;
			n=n.right;
		}
	
	}
	if(v>p.value)
	{
		p.right=new Node(v,1);
	}else
	{
		p.left=new Node(v,1);
	}
	return rt;
	
}

public int getCount(Node n, int v)
{
	while(n!=null && n.value<=v)
	{
		n=n.right;
	}
	if(n==null)
	{
		return 0;
	}
	if(n.value>v)
	{
		return n.count;
	}
}

public int[] getCounts(int[] a)throws NullPointerException
{
	if(a==null)
	{
		throw new NullPointerException();
	}
	Node rt=null;
	for(int i=a.length-1;i>=0;i--)
	{
		int count=getCount(rt,a[i]);
		rt=insert(a[i],rt);
		a[i]=count;
	}
	return a;
}
//Uses a BST. O(n log n) running time with O(n) space.

My O(nlogn) solution using TreeSet and custom comparator

import java.util.Arrays;
import java.util.Comparator;
import java.util.TreeSet;

/**
 * Created by rshrivastava on 10/27/15.
 */
public class CountLargerElements {

    private static class Node {
        int val;
        int count;
        int index;

        public Node(int v, int i) {
            val = v;
            index = i;
        }

        @Override
        public boolean equals(Object obj) {
            Node other = (Node) obj;
            return other.val == val && other.index == index;
        }

        @Override
        public int hashCode() {
            return val + index;
        }
    }

    public static int[] countGreater(int[] input) {
        Comparator<Node> treeComparator = (first, second) -> {
            if (first.equals(second)) return 0;
            if (first.val < second.val) {
                first.count = second.count + 1;
                return -1;
            } else {
                return 1;
            }
        };

        TreeSet<Node> treeSet = new TreeSet<>(treeComparator);
        for (int i = input.length - 1; i >= 0; --i) {
            Node node = new Node(input[i], i);
            treeSet.add(node);
        }

        int[] result = new int[input.length];
        treeSet.stream().forEach(node -> result[node.index] = node.count);
        return result;
    }

    public static void main(String[] args) {
        int[] input = new int[]{3, 4, 5, 9, 2, 1, 3};
        System.out.println(Arrays.toString(countGreater(input)));
    }
}

O(n log n) Java solution with TreeSet.tailSet():

public static List<Integer> solution(int[] nums) {
        LinkedList<Integer> result = new LinkedList<Integer>();
        TreeSet<Integer> set = new TreeSet<Integer>();
        for(int i=nums.length-1; i >= 0; i--) {
            Set<Integer> larger = set.tailSet(nums[i], false);
            result.addFirst(larger.size());
            set.add(nums[i]);
        }
        return result;
    }

1. In naive way, it would take O(n^2) and additional array of size n.
alternate means is
--------------------------
steps:-
1. iterate each element and create binary tree, (right greater than root and left smaller than root).
2. Upon encountering duplicate , skip that node and proceed to insert as thou duplicate element is lesser than element already present.
3. traverse the constructed binary tree, for each element find number of nodes till leaf . That would provide the count of number of larger numbers for that elements.
4. repeat for remaining elements.

1. In naive way, it would take O(n^2) and additional array of size n.
alternate means is
--------------------------
steps:-
1. iterate each element and create binary tree, (right greater than root and left smaller than root).
2. Upon encountering duplicate , skip that node and proceed to insert as thou duplicate element is lesser than element already present.
3. traverse the constructed binary tree, for each element find number of nodes till leaf . That would provide the count of number of larger numbers for that elements.
4. repeat for remaining elements.

void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void numGreater(int a[], int b[], int n)
{
if (n <= 1)
{
return;
}

b[n-1] = 0;
for(int i = n - 2; i >= 0; i--)
{
b[i] = (n - 1) - i;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[i+j] >= a[i+1+j])
{
swap(&a[i+j], &a[i+1+j]);
b[i] --;
}
else
{
break;
}
}
}
}

int main(int argc, char* argv[])
{
int a[] = {3, 4, 5, 9, 2, 1, 3};
int b[] = {0, 0, 0, 0, 0, 0, 0};

numGreater(a, b, 7);

return 0;
}

void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void numGreater(int a[], int b[], int n)
{
if (n <= 1)
{
return;
}

b[n-1] = 0;
for(int i = n - 2; i >= 0; i--)
{
b[i] = (n - 1) - i;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[i+j] >= a[i+1+j])
{
swap(&a[i+j], &a[i+1+j]);
b[i] --;
}
else
{
break;
}
}
}
}

int main(int argc, char* argv[])
{
int a[] = {3, 4, 5, 9, 2, 1, 3};
int b[] = {0, 0, 0, 0, 0, 0, 0};

numGreater(a, b, 7);

return 0;
}

void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}

void numGreater(int a[], int b[], int n)
{
if (n <= 1)
{
return;
}

b[n-1] = 0;
for(int i = n - 2; i >= 0; i--)
{
b[i] = (n - 1) - i;
for (int j = 0; j < n - 1 - i; j++)
{
if (a[i+j] >= a[i+1+j])
{
swap(&a[i+j], &a[i+1+j]);
b[i] --;
}
else
{
break;
}
}
}
}

int main(int argc, char* argv[])
{
int a[] = {3, 4, 5, 9, 2, 1, 3};
int b[] = {0, 0, 0, 0, 0, 0, 0};

numGreater(a, b, 7);

return 0;
}

void swap(int *a, int *b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void numGreater(int a[], int b[], int n)
{
	if (n <= 1)
	{
		return;
	}

	b[n-1] = 0;
	for(int i = n - 2; i >= 0; i--)
	{
		b[i] = (n - 1) - i;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[i+j] >= a[i+1+j])
			{
				swap(&a[i+j], &a[i+1+j]);
				b[i] --;
			}
			else
			{
				break;
			}
		}
	}
}

int main(int argc, char* argv[])
{
	int a[] = {3, 4, 5, 9, 2, 1, 3};	
	int b[] = {0, 0, 0, 0, 0, 0, 0};

	numGreater(a, b, 7);

	return 0;
}

Here is C++ solution running in O(N log N) using merge sort.

#include <vector>
#include <iostream>

using namespace std;


struct node {
  int value;
  int count;
  int pos;
  node(int v, int p):value(v), count(0), pos(p){}
};

vector<node*> merge_sort(vector<node *>& input, int s, int e)
{
  vector<node*> temp;

  if (s == e)
  {
    temp.push_back(input[s]);
    return temp;
  }

  int half = s+ (e-s)/2;

  vector<node*> left = merge_sort(input, s, half);
  vector<node*> right = merge_sort(input, half+1, e);
  int lpos = 0, rpos = 0;
  while (lpos < left.size() && rpos<right.size())
  {
    if (left[lpos]->value < right[rpos]->value)
    {
      left[lpos]->count += (right[rpos]->count + 1);
      temp.push_back(left[lpos++]);
    } else {
      temp.push_back(right[rpos++]);
    }
  }

  if (lpos < left.size())
    temp.insert(temp.end(), left.begin()+lpos, left.end());
  else if (rpos < right.size())
    temp.insert(temp.end(), right.begin()+rpos, right.end());
  return temp;
}

void count_larger_numbers_in_rest(int* input, int len)
{
  vector<node*>list;
  for (int i = 0; i < len; i++)
  {
    list.push_back(new node(input[i], i));
  }

  vector<node*> result = merge_sort(list, 0, len-1);
  int* counts = new int[len];
  for (int i = 0; i < len; i++)
    counts[result[i]->pos]= result[i]->count;
  for (int i = 0; i < len; i++)
    cout<<counts[i]<<", ";
}

int main()
{
  int input[7] = {3,4,5,9,2,1,3};

  count_larger_numbers_in_rest(input, 7);
  return 1;
}

Here is C++ version of the solution running in O (n log n) using merge sort.

#include <vector>
#include <iostream>

using namespace std;

struct node {
  int value;
  int count;
  int pos;
  node(int v, int p):value(v), count(0), pos(p){}
};

vector<node*> merge_sort(vector<node *>& input, int s, int e)
{
  vector<node*> temp;

  if (s == e)
  {
    temp.push_back(input[s]);
    return temp;
  }

  int half = s+ (e-s)/2;

  vector<node*> left = merge_sort(input, s, half);
  vector<node*> right = merge_sort(input, half+1, e);
  int lpos = 0, rpos = 0;
  while (lpos < left.size() && rpos<right.size())
  {
    if (left[lpos]->value < right[rpos]->value)
    {
      left[lpos]->count += (right[rpos]->count + 1);
      temp.push_back(left[lpos++]);
    } else {
      temp.push_back(right[rpos++]);
    }
  }

  if (lpos < left.size())
    temp.insert(temp.end(), left.begin()+lpos, left.end());
  else if (rpos < right.size())
    temp.insert(temp.end(), right.begin()+rpos, right.end());
  return temp;
}

void count_larger_numbers_in_rest(int* input, int len)
{
  vector<node*>list;
  for (int i = 0; i < len; i++)
  {
    list.push_back(new node(input[i], i));
  }

  vector<node*> result = merge_sort(list, 0, len-1);
  int* counts = new int[len];
  for (int i = 0; i < len; i++)
    counts[result[i]->pos]= result[i]->count;
  for (int i = 0; i < len; i++)
    cout<<counts[i]<<", ";
}

int main()
{
  int input[7] = {3,4,5,9,2,1,3};

  count_larger_numbers_in_rest(input, 7);
  return 1;
}

// O(N*log(N))
void count_greater(const int* in, const size_t num, int* out) {
	std::multiset<int> seen;
	for (int i=(num-1); i>=0; --i) {
		out[i] = seen.size() - std::distance(seen.cbegin(), seen.upper_bound(in[i]));
		seen.insert(in[i]);
	}
}

To solve this problem a merge sort approach must be used, if we use recursion by far the implementation is clean, The idea is to split the list and in the merge process in the second list locate the first occurrence of a greater value and use its current count, a helper array is used to store the counts.

The tricky part is that the original list must be split in a pow of two in order to get a correct result.

public int[] FindValues(int[] values)
{
	if (values == null || values.Length == 0)
		return new int[0];

	int[] result = new int[values.Length];

	int n = 1;
	while (n < values.Length)
		n *= 2;

	MergeSort(values, result, 0, n);
	return result;
}

private void MergeSort(int[] values, int[] result, int startIndex, int n)
{
	if (n == 1)
		return;

	int middle = n / 2;
	MergeSort(values, result, startIndex, middle);
	MergeSort(values, result, startIndex + middle, middle);

	MergeLists(values, result, startIndex, startIndex + middle);
}

private void MergeLists(int[] values, int[] result, int index1, int index2)
{
	int n = index2 - index1;
	Debug.Assert(n > 0);
	if (index2 + n >= values.Length)
		n = values.Length - index2;

	while (index1 < index2)
	{
		for (int i = 0; i < n; i++)
			if (values[index1] < values[index2 + i])
			{
				result[index1] += (result[index2 + i] + 1);
				break;
			}

		index1++;
	}
}

Can be done in O(nlogn) using the below algo

> Prepare binary search tree from the area (takes O(nlogn)
>> While preparing, maintain its original index and value that represents how many values going towards its right (greater values)
> Once binary search tree is done, traverse the tree and prepare output array using the original index saved and the value which represent number of greater values. (any traversal takes O(n) )
Overall algo should be O(nlogn).

def greater(mas):
    gr=[]
    for i in range(len(mas)):
        s=0
        for j in range(i,len(mas)):
            if mas[j]>mas[i]:
                s+=1
        gr.append(s)
    return gr
print(greater([3,4,5,9,2,1,3]))

output:

[3, 2, 1, 0, 1, 1, 0]

There is my solution.

The idea is to start from the right hand side of array to the left hand side and use insertion sort.
- Initialize a sorted data like std::set as sortedArray
- Initialize a linked list to take the result, result
- Take the element, x, from the array in the reverse order
- Find the number of larger value in sortedArray than x, as n
- Push n into the front of result
- Insert x into sortedArray
- Loop the above 4 steps until exhaust the whole array
- Return result

Implementation: cpluspluslearning-petert.blogspot.co.uk/2015/11/insertion-sort-find-number-of-larger.html

Test

void TestFindTheNumberOfLargerValuesInTheRemainingArray()
{
    {
        std::vector<int> input;
        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(output.empty() == true);

        input.push_back(0);
        output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(output.size() == 1);
        assert(output[0] == 0);
    }

    {
        std::vector<int> input = { 3, 4, 5, 9, 2, 1, 3 };
        const std::vector<int> result = { 3, 2, 1, 0, 1, 1, 0 };
        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(result == output);
    }

    {
        std::vector<int> input = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        const std::vector<int> result = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(result == output);
    }

    {
        std::vector<int> input = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        const std::vector<int> result = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        std::vector<int> output = FindTheNumberOfLargerValuesInTheRemainingArray(input);
        assert(result == output);
    }
}

Let's think about sorting in descending order for just a second. Intuitively, exchanging elements while sorting contains the required information already. If we move some element forward, we incrementing the counter for all elements, that we have "outruned" in the array.

So, we need only to modify some existing sorting algorithm witn O(nlogn) complexity in order to store the required information. Let's take Merge sort and make two modifications.
1. Let's preserve the source array by introducing the array of indices ( int[] arrindices ), where arrindices[i] shows which element of the source array stays at position i at the moment.

2. we introduce int[] resarray to store the number of elements, greater than that element remaining in the array.

Let's consider the DoMerge part of the algorithms, where we are merging two sorted subarrays. If we take the element from the second array (else clause), it is by default greater then all remaining elements from the first array. So, we have to increment the resulting array for all such elements by one. To avoid introducing another loops in code, we'll introduce the counter of the elements, that had been moved from the second array, and will add this counter to resarray for each element of the first array, when it is taken to the resulting array.

Complete code here:

public class MergeSortModified
{
    public void DoMerge(int[] arr, int[] arrindices, int[] resarray, int start, int middle, int end)
    {
        // create temp array to store sorted subarray
        int[] temp = new int[end - start + 1];
        int l = start;
        int m = middle + 1;

        int k = 0;

        // store the amount 
        int gr = 0;

        // run a marker until at least one source subarrays is not empty
        while (l <= middle && m <= end)
        {
            if (arr[arrindices[l]] >= arr[arrindices[m]])
            {
                temp[k] = arrindices[l];

                // increment the result array by the number of already found greater elements
                resarray[arrindices[l]] += gr;
                l++;
                k++;
            }
            else
            {
                // increment the amount of "greater" elements
                gr++;
                temp[k] = arrindices[m];
                m++;
                k++;
            }
        }

        // take the remaining elements from the first subarray is any
        while (l <= middle)
        {
            temp[k] = arrindices[l];

            // increment the result array by the number of already found greater elements
            resarray[arrindices[l]] += gr;
            k++;
            l++;
        }

        // take the remaining elements from the second subarray is any
        while (m <= end)
        {
            temp[k++] = arrindices[m++];
        }

        // copy sorted subarray of indices back to the indices array
        for (int pos = 0; pos < end - start + 1; pos++)
            arrindices[start + pos] = temp[pos];

    }

    public void Merge(int[] arr, int[] arrindices, int[] resarray, int start, int end)
    {
        // if array is long enough
        if (start < end)
        {  
            // divide array into two parts
            int m = (start + end) / 2;

            // sort the first half
            Merge(arr, arrindices, resarray, start, m);

            // sort the second half
            Merge(arr, arrindices, resarray, m + 1, end);

            // Merge sorted subarrays
            DoMerge(arr, arrindices, resarray, start, m, end);
        }
    }
}

1. Traverse the array and store a count array.
2. Traverse the array again and for each element x, add the values in count_array[x:9]. This is the value we need
3. count_array[x]--

Complexity: O(n) + O(n)*[0-9] = O(n)

How come this question was asked in the phone interview? I'm wondering how many people can write the running code in phone interview. This is for on-site.

Divide and Conquer.

Follow an approach similar to finding number of inversions using a modification of merge sort (nlogn).