title: Construct count array in better than O(n^2) time complexity
body: <p>Given an array <code>A[]</code> of size <code>n</code>, construct two arrays <code>C_min[]</code> and <code>C_max[]</code> such that<br>
  <code>C_min[i]</code> represents number of elements smaller than <code>A[i]</code> in <code>A[0 to i]</code> and<br>
  <code>C_max[i]</code> represents number of elements greater than <code>A[i]</code> in <code>A[i to n-1]</code> </p>
  
  <p>For example <code>A[5] = {1,2,4,3,6}</code> then <code>C_min[]</code> and <code>C_max[]</code> would be<br>
  <code>C_min[5] = {0,1,2,2,4}</code><br>
  <code>C_max[5] = {4,3,1,1,0}</code></p>
  
  <p>I am not able to think of an algorithm better than O(n^2) but <a href="http://www.geeksforgeeks.org/counting-inversions/" rel="nofollow">this post</a> motivates me to think of some better way of doing this, but am not able to able apply similar kind of logic(which is mentioned in the post) here. </p>
  
  <p>In the given post, problem given is to find no of inversion in an array. if array[i] > array[j] and j>i then it forms a inversion. for example The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).<br>
  idea used to solve this problem is a merge sort algorithm.<br></p>
  
  <blockquote>
    <p>In merge process, let i is used for indexing left sub-array(L[]) and j
    for right sub-array(R[]). At any step in merge(), if L[i] is greater
    than R[j], then there are (mid – i+1) inversions,where mid is the
    middle index passed to the merge function of merge sort. because left
    and right subarrays are sorted, so all the remaining elements in
    left-subarray (L[i+1], L[i+2] … L[mid]) will be greater than R[j]</p>
  </blockquote>
  
  <p>code for this logic is given below:</p>
  
  <pre><code>#include &lt;bits/stdc++.h&gt;
  
  int  _mergeSort(int arr[], int temp[], int left, int right);
  int merge(int arr[], int temp[], int left, int mid, int right);
  
  /* This function sorts the input array and returns the
     number of inversions in the array */
  int mergeSort(int arr[], int array_size)
  {
      int *temp = (int *)malloc(sizeof(int)*array_size);
      return _mergeSort(arr, temp, 0, array_size - 1);
  }
  
  /* An auxiliary recursive function that sorts the input array and
    returns the number of inversions in the array. */
  int _mergeSort(int arr[], int temp[], int left, int right)
  {
    int mid, inv_count = 0;
    if (right &gt; left)
    {
      /* Divide the array into two parts and call _mergeSortAndCountInv()
         for each of the parts */
      mid = (right + left)/2;
  
      /* Inversion count will be sum of inversions in left-part, right-part
        and number of inversions in merging */
      inv_count  = _mergeSort(arr, temp, left, mid);
      inv_count += _mergeSort(arr, temp, mid+1, right);
  
      /*Merge the two parts*/
      inv_count += merge(arr, temp, left, mid+1, right);
    }
    return inv_count;
  }
  
  /* This funt merges two sorted arrays and returns inversion count in
     the arrays.*/
  int merge(int arr[], int temp[], int left, int mid, int right)
  {
    int i, j, k;
    int inv_count = 0;
  
    i = left; /* i is index for left subarray*/
    j = mid;  /* i is index for right subarray*/
    k = left; /* i is index for resultant merged subarray*/
    while ((i &lt;= mid - 1) &amp;&amp; (j &lt;= right))
    {
      if (arr[i] &lt;= arr[j])
      {
        temp[k++] = arr[i++];
      }
      else
      {
        temp[k++] = arr[j++];
  
       /*this is tricky -- see above explanation/diagram for merge()*/
        inv_count = inv_count + (mid - i);
      }
    }
  
    /* Copy the remaining elements of left subarray
     (if there are any) to temp*/
    while (i &lt;= mid - 1)
      temp[k++] = arr[i++];
  
    /* Copy the remaining elements of right subarray
     (if there are any) to temp*/
    while (j &lt;= right)
      temp[k++] = arr[j++];
  
    /*Copy back the merged elements to original array*/
    for (i=left; i &lt;= right; i++)
      arr[i] = temp[i];
  
    return inv_count;
  }
  
  /* Driver progra to test above functions */
  int main(int argv, char** args)
  {
    int arr[] = {1, 20, 6, 4, 5};
    printf(" Number of inversions are %d \n", mergeSort(arr, 5));
    getchar();
    return 0;
  }
  </code></pre>
  
  <p>so can this count array problem be done on similar lines.</p>
  
  <blockquote>
    <p>Is it possible to construct count array in better than O(n^2)-time?</p>
  </blockquote>