Given array and key, find the number of elements smaller than or equal to itself in its left and right sub array?

Question

I have to find the number of elements smaller than or equal to i-th element of array in the left and right subarrays.

For example if my array is

A[]=4 3 5 2 2 5

My 2 arrays will be

0 0 2 0 0 5

And

3 2 3 1 1 0

The i-th element of 1st array denotes the number of elements smaller than or equal to i-th element to the left of the i-th element.

The i-th element of 2nd array denotes the number of elements smaller than or equal to i-th element to the right of the i-th element.

I can find these arrays in O(n²) using two loops.

Can this be done in O(n)?

Answer 1

You can do this in O(nlogm) (where n is the length of A, and m is the size of the largest element in the array) using a Fenwick Tree.

A Fenwick tree (also called binary indexed tree) allows you to add elements to an array and compute sums of consecutive elements in O(logn) time. There is a good tutorial on topcoder.

In this problem we can use the Fenwick tree to store a histogram of how many times we have seen each value. The histogram starts empty, and then we gradually insert elements into the histogram.

So we need to iterate through the array, each time first computing how many elements have value smaller than the current value, and then adding the current value to the array.

Python code:

def find_lower(A):
    """Return B where B[i] is the number of elements <= A[i] in A[0:i]"""
    top = max(A) + 1
    F = fenwick_new(top)
    left = []
    for a in A:
        left.append( fenwick_sum(F,a) )
        fenwick_increase(F,a,1)
    return left

A=[4, 3, 5, 2, 2, 5]
print find_lower(A)
print find_lower(A[::-1])[::-1]

This uses some standard Fenwick tree functions:

def fenwick_new(m):
    """Create empty fenwick tree with space for elements in range 0..m"""
    # tree[i] is sum of elements with indexes i&(i+1)..i inclusive
    return [0] * (m+1)

def fenwick_increase(tree,i,delta):
    """Increase value of i-th element in tree by delta"""
    while i < len(tree):
        tree[i] += delta
        i |= i + 1

def fenwick_sum(tree,i):
    """Return sum of elements 0..i inclusive in tree"""
    s = 0
    while i >= 0:
        s += tree[i]
        i &= i + 1
        i -= 1
    return s