given an array, for each element, find out the total number of elements lesser than it, which appear to the right of it

Question

I had previously posted a question, Given an array, find out the next smaller element for each element now, i was trying to know , if there is any way to find out "given an array, for each element, find out the total number of elements lesser than it, which appear to the right of it" for example, the array [4 2 1 5 3] should yield [3 1 0 1 0]??

[EDIT] I have worked out a solution, please have a look at it, and let me know if there is any mistake.

1 Make a balanced BST inserting elements traversing the array from right to left

2 The BST is made in such a way that each element holds the size of the tree rooted at that element

3 Now while you search for the right position to insert any element, take account of the total size of the subtree rooted at left sibling + 1(for parent) if you move right Now since, the count is being calculated at the time of insertion of an element, and that we are moving from right to left, we get the exact count of elements lesser than the given element appearing after it.

Answer 1

It can be solved in O(n log n).

If in a BST you store the number of elements of the subtree rooted at that node when you search the node (reaching that from the root) you can count number of elements larger/smaller than that in the path:

int count_larger(node *T, int key, int current_larger){
    if (*T == nil)
        return -1;
    if (T->key == key)
        return current_larger + (T->right_child->size);
    if (T->key > key)
        return count_larger(T->left_child, key, current_larger + (T->right_child->size) + 1);
    return count_larger(T->right_child, key, current_larger)
}

** for example if this is our tree and we're searching for key 3, count_larger will be called for:

-> (node 2, 3, 0)
--> (node 4, 3, 0)
---> (node 3, 3, 2)

and the final answer would be 2 as expected.

Answer 2

Suppose the Array is 6,-1,5,10,12,4,1,3,7,50

Steps

1.We start building a BST from right end of the array.Since we are concerned with all the elements to right for any element.

2.Suppose we have formed the partial solution tree upto the 10.

3.Now when inserting 5 we do a tree traversal and insert to the right of 4. Notice that each time we traverse to the right of any node we increment by 1 and add the no. of elements in left subtree of that node. eg:
for 50 it is 0
for 7 it is 0
for 12 it is 1 right traversel + leftsubtree size of 7 = 1+3 =4
for 10 same as above.
for 4 it is 1+1 =2

While building bst we can easily maintain the left subtree size for each node by simply maintaining a variable corresponding to it and incrementing it by 1 each time a node traverses to the left by it.
Hence the Solution Average case O(nlogn).

We can use other optimizations such as predetermining whether array is sorted in decreasing order find groups of element in decreasing order treat them as single.

Answer 3

You can also use binary Index tree

int tree[1000005];
void update(int idx,int val)
{
   while(idx<=1000000)
   {
       tree[idx]+=val;
       idx+=(idx & -idx);
   }
}

int sum(int idx)
{
    int sm=0;
    while(idx>0)
    {
       sm+=tree[idx];
       idx-=(idx & -idx);
    }
    return sm;
}

int main()
{
    int a[]={4,2,1,5,3};
    int s=0,sz=6;
    int b[10];
    b[sz-1]=0;
    for(int i=sz-2;i>=0;i--)
    {
        if(a[i]!=0)
        {
            update(a[i],1);
            b[i]=sum(a[i]-1)+s;
        }
        else s++;
    }
    for(int i=0;i<sz-1;i++)
    {
       cout<<b[i]<<" ";
    }
   return 0;
}

Answer 4

I think is it possible to do it in O(nlog(n))with a modified version of quicksort. Basically each time you add an element to less, you check if this element rank in the original array was superior to the rank of the current pivot. It may look like

oldrank -> original positions 
count -> what you want
function quicksort('array')
  if length('array') ≤ 1
      return 'array'  // an array of zero or one elements is already sorted
  select and remove a pivot value 'pivot' from 'array'
  create empty lists 'less' and 'greater'
  for each 'x' in 'array'
      if 'x' ≤ 'pivot' 
         append 'x' to 'less'
         if oldrank(x) > = oldrank(pivot)  increment count(pivot)
      else 
         append 'x' to 'greater'
         if oldrank(x) <  oldrank(pivot)  increment count(x) //This was missing
  return concatenate(quicksort('less'), 'pivot', quicksort('greater')) // two recursive calls

EDIT:

Actually it can be done using any comparison based sorting algorithm . Every time you compare two elements such that the relative ordering between the two will change, you increment the counter of the bigger element.

Original pseudo-code in wikipedia.

Answer 5

Another approach without using the tree.

1. Construct another sorted array . For example for input array {12, 1, 2, 3, 0, 11, 4} it will be {0, 1, 2, 3, 4, 11, 12}
2. Now compare position of each element from input array with sorted array.For example 12 in first array is at 0 index while sorted array it’s as 6
3. Once comparison is done, remove element from both array

Answer 6

Other than using BST, we can also solve this problem optimally by doing some modification in merge sort algorithm (in O(n*logn) time).

If you observe this problem more carefully, you can say that in the problem we need to count the number of inversions required for each element to make the array sorted in ascending order, right?

So this problem can be solved using Divide and Conquer paradigm. Here you need to maintain an auxiliary array for storing the count of inversions required (i.e. elements smaller than it on the right side of it).

Below is a python program:

def mergeList(arr, pos, res, start, mid, end):
    temp = [0]*len(arr)
    for i in range(start, end+1):
        temp[i] = pos[i]

    cur = start
    leftcur = start
    rightcur = mid + 1

    while leftcur <= mid and rightcur <= end:

        if arr[temp[leftcur]] <= arr[temp[rightcur]]:
            pos[cur] = temp[leftcur]
            res[pos[cur]] += rightcur - mid - 1
            leftcur += 1
            cur += 1
        else:
            pos[cur] = temp[rightcur]
            cur += 1
            rightcur += 1

    while leftcur <= mid:
        pos[cur] = temp[leftcur]
        res[pos[cur]] += end - mid
        cur += 1
        leftcur += 1

    while rightcur <= end:
        pos[cur] = temp[rightcur]
        cur += 1
        rightcur += 1


def mergeSort(arr, pos, res, start, end):
    if start < end:
        mid = (start + end)/2
        mergeSort(arr, pos, res, start, mid)
        mergeSort(arr, pos, res, mid+1, end)
        mergeList(arr, pos, res, start, mid, end)


def printResult(arr, res):
    print
    for i in range(0, len(arr)):
        print arr[i], '->', res[i]


if __name__ == '__main__':
    inp = input('enter elements separated by ,\n')
    inp = list(inp)
    res = [0]*len(inp)
    pos = [ind for ind, v in enumerate(inp)]
    mergeSort(inp, pos, res, 0, len(inp)-1)
    printResult(inp, res)

Time : O(n*logn)

Space: O(n)

Answer 7

//some array called newarray
for(int x=0; x <=array.length;x++)
{
for(int y=x;y<array.length;y++)
{
if(array[y] < array[x])
{
newarray[x] = newarray[x]+1;
}
}
}

something like this,where array is your input array and newarray your output array make sure to initialize everything correctly(0 for the newarrays values)

Answer 8

You can also use an array instead of a binary search tree.

def count_next_smaller_elements(xs):
    # prepare list "ys" containing item's numeric order
    ys = sorted((x,i) for i,x in enumerate(xs))
    zs = [0] * len(ys)

    for i in range(1, len(ys)):
        zs[ys[i][1]] = zs[ys[i-1][1]]
        if ys[i][0] != ys[i-1][0]: zs[ys[i][1]] += 1

    # use list "ts" as binary search tree, every element keeps count of
    # number of children with value less than the current element's value
    ts = [0] * (zs[ys[-1][1]]+1)
    us = [0] * len(xs)

    for i in range(len(xs)-1,-1,-1):
        x = zs[i]+1
        while True:
            us[i] += ts[x-1]
            x -= (x & (-x))
            if x <= 0: break

        x = zs[i]+1
        while True:
            x += (x & (-x))
            if x > len(ts): break
            ts[x-1] += 1

    return us

print count_next_smaller_elements([40, 20, 10, 50, 20, 40, 30])
# outputs: [4, 1, 0, 2, 0, 1, 0]

Answer 9

Instead of BST, you can use stl map.

Start inserting from right. After inserting an element, find its iterator:

auto i = m.find(element);

Then subtract it from m.end(). That gives you the number of elements in map which are greater than current element.

map<int, bool> m;
for (int i = array.size() - 1; i >= 0; --i) {
  m[array[i]] = true;
  auto iter = m.find(array[i])
  greaterThan[i] = m.end() - iter;
}

Hope it helped.

Answer 10

Modified Merge sort: (Already tested code)

Takes O(nlogn) time.

public class MergeSort {
    static HashMap<Integer, Integer> valueToLowerCount = new HashMap<Integer, Integer>();

    public static void main(String[] args) {
        int []                 arr = new int[] {50, 33, 37, 26, 58, 36, 59};
        int [] lowerValuesOnRight  = new int[] {4,   1,  2,  0,  1,  0,  0};

        HashMap<Integer, Integer> expectedLowerCounts = new HashMap<Integer, Integer>();
        idx = 0;
        for (int x: arr) {
            expectedLowerCounts.put(x, lowerValuesOnRight[idx++]);
        }
        
        for (int x : arr) valueToLowerCount.put(x, 0);
        
        mergeSort(arr, 0, arr.length-1);
        
        //Testing       
        Assert.assertEquals("Count lower values on right side", expectedLowerCounts, valueToLowerCount);
    }
    public static void mergeSort(int []arr, int l, int r) {
        if (r <= l) return;
        int mid = (l+r)/2;
        mergeSort(arr, l, mid);
        mergeSort(arr, mid+1, r);
        mergeDecreasingOrder(arr, l, mid, r);
    }
    public static void mergeDecreasingOrder(int []arr, int l, int lr, int r) {
        int []leftArr = Arrays.copyOfRange(arr, l, lr+1);
        int []rightArr = Arrays.copyOfRange(arr, lr+1, r+1);
        int indexArr = l;
        int i = 0, j = 0;
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] > rightArr[j]) {
                valueToLowerCount.put(leftArr[i], valueToLowerCount.get(leftArr[i]) + rightArr.length - j);
                arr[indexArr++] = leftArr[i++];
            }else {
                arr[indexArr++] = rightArr[j++];
            }
        }
        while (i < leftArr.length)  { 
            arr[indexArr++] = leftArr[i++]; 
        }
        while (j < rightArr.length) {
            arr[indexArr++] = rightArr[j++];
        }
    }   
}

To find the total number of values on right-side which are greater than an array element, simply change single line of code:

if (leftArr[i] > rightArr[j])

to

if (leftArr[i] < rightArr[j])