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

Answer 2

It seems that you cannot jump over nlogn so basic version would be just:

def naive(arr)
  res = Array.new(arr.size,0)
  for i in 0..arr.length-1
    for j in i+1..arr.length-1
      res[i] += 1 if arr[i] >= arr[j]
    end
  end
  res
end

However depending on your data sets you can do some optimizations. For example in your example there are repetitions - we can use that fact to avoid traversing array for same number twice. In such case instead of searching for numbers lesser than current - you can do addition to every number larger than current (from right to left) and ignore numbers that already has been used:

def rightleft(arr)
  ignore = {}
  res = Array.new(arr.size,0)
  (arr.size-1).downto(0) do |i|
    current = arr[i]
    next if ignore[current]
    additor = 1
    (i-1).downto(0) do |j|
      if arr[i] <= arr[j]
        res[j] += additor
          if arr[i] == arr[j]
          additor += 1
          ignore[current] = true
        end
      end
    end
  end
  res
end

Let us take some example with lot of repetitions:

A = %W{1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 3 5 4 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 12 14 5 6 4 3 1 7 8 9 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 10 2 11 12 4 13 1 2 2 3 3 5 4 6 5 7 8 9 10 11 12 14 5 6 4 3 1 7 8 9 1 10 2 11 12 4 13 14 6 15 12 16 17 18 19}.map(&:to_i)

Now benchmark

puts "NAIVE 100 times:"
puts time_elapsed{
  100.times do
    naive(A)
  end
}

puts "rl 100 times"
puts time_elapsed{
  100.times do
    rightleft(A)
  end
}

Result:

NAIVE 100 times:
[14, 30, 29, 53,...., 0, 0]
Time elapsed 485.935997 milliseconds

rl 100 times
[14, 30, 29, 53,...., 0, 0]
Time elapsed 81.735048 milliseconds

But when you have no repetitions - this optimization will make it slightly slower. Here are results for numbers 1,2,3...,99,100 shuffled:

NAIVE 100 times:
[70, 7,... 1, 0]
Time elapsed 99.58762899999999 milliseconds

rl 100 times
[70, 7, ... 1, 0]
Time elapsed 113.186392 milliseconds

Answer 3

No, it is not possible to do it in O(n) time. The best you can do is O(n log n).

Here is the proof. Suppose the original array has n distinct elements. Let's work out how many possibilities there are for the first array you wanted (the proof for the other one is similar). There is 1 possibility for the first number (0). There are 2 possibilities for the 2nd number (0 or 1). There are 3 possibilities for the 3rd number (0, 1 or 2), and so on. It follows that there at most 1 * 2 * 3 * ... * n = n! possible answers. In fact it is easy to see that for each of these possible answers there is at least one array of distinct numbers that produces it (Work from left to right. If answer[i] is to be 0, set original[i] to be smaller than all previously chosen numbers. If answer[i] is to be i, set original[i] to be greater than all previously chosen numbers. Otherwise, set original[i] to be a number between the i-th smallest and the (i+1)-th smallest number already chosen). Any algorithm must identify which of the n! possible answers is the right one. If we can always finish the algorithm with f(n) comparisons it follows that 2^f(n) >= n! (each comparison has only 2 possible results as the original numbers were all distinct). Taking logs (base 2) of both sides we get f(n) >= log(n!). Using Stirling's approximation for log(n!) we see that we can't do better than O(n log n) comparisons.

It is possible to do it in O(n log n) time. The following Java method (which does not run in O(n log n) time) returns the first array you require (the second one can be done similarly). Arrays.sort() uses TimSort which is O(n log n). However, in order to make the whole method run in O(n log n) time, you have to replace ArrayList with an implementation of List where the methods add(Object object), remove(int index) and lastIndexOf(Object object) all run in O(log n) time. According to http://www.nayuki.io/page/avl-tree-list, AvlTreeList does add() and remove() in O(log n) time, and it is possible to "augment" an AvlTreeList so that searches are O(log n) too. This proves that your arrays can be found in O(n log n) time.

public static int[] firstArray(int[] arr) {
    int[] copy = arr.clone();
    Arrays.sort(copy);
    List<Integer> list = new ArrayList<>();
    for (int a : copy)
        list.add(a);
    int length = arr.length;        
    int[] temp = new int[length];
    for (int i = length - 1; i >= 0; i--) {
        int j = list.lastIndexOf(arr[i]);
        temp[i] = j;
        list.remove(j);
    }
    return temp;
}

Answer 4

I shall simplify @pbabcdefp's answer using something called a balanced binary tree with rank field (see Knuth 6.2.3, Linear list representation). Consider a balanced tree (the implementation doesn't matter, so either red-black or AVL will do fine) yet we have an additional field called the rank which will store the size of the left subtree, numbers will be inserted into our tree in smallest to largest order, the rank field for each affected node is updated after each insertion/rotation. We will allow duplicate elements in our balanced tree.

Algorithm A:

1. Set head to the root node. Set v to the value we are searching for. Let i be the index in the list for v, this will be our return value.
2. If head is null/empty, return successfully with index i.
3. If v < head.value, then head <- head.left, otherwise i <- i + head.rank + 1 and head <- head.right.
4. Go back to 2.

Original Algorithm:

For each element in the array: use Algorithm A described above to find the number of elements (that are in the tree and thus came before the current element) less than or equal to it, then add it to our tree using the modified insertion. This gives the first array. Repeat once more, this time walking over the array backwards instead of forwards, to get the second array.