Is there an O(n) algorithm to generate a prefix-less array for an positive integer array?

Question

For array [4,3,5,1,2], we call prefix of 4 is NULL, prefix-less of 4 is 0; prefix of 3 is [4], prefix-less of 3 is 0, because none in prefix is less than 3; prefix of 5 is [4,3], prefix-less of 5 is 2, because 4 and 3 are both less than 5; prefix of 1 is [4,3,5], prefix-less of 1 is 0, because none in prefix is less than 1; prefix of 2 is [4,3,5,1], prefix-less of 2 is 1, because only 1 is less than 2

So for array [4, 3, 5, 1, 2], we get prefix-less arrary of [0,0, 2,0,1], Can we get an O(n) algorithm to get prefix-less array?

Answer 1

It can't be done in O(n) for the same reasons a comparison sort requires O(n log n) comparisons. The number of possible prefix-less arrays is n! so you need at least log2(n!) bits of information to identify the correct prefix-less array. log2(n!) is O(n log n), by Stirling's approximation.

Answer 2

Assuming that the input elements are always fixed-width integers you can use a technique based on radix sort to achieve linear time:

• L is the input array
• X is the list of indexes of L in focus for current pass
• n is the bit we are currently working on
• Count is the number of 0 bits at bit n left of current location
• Y is the list of indexs of a subsequence of L for recursion
• P is a zero initialized array that is the output (the prefixless array)

In pseudo-code...

Def PrefixLess(L, X, n)
    if (n == 0)
       return;

    // setup prefix less for bit n
    Count = 0

    For I in 1 to |X|
        P(I) += Count
        If (L(X(I))[n] == 0)
            Count++;

    // go through subsequence with bit n-1 with bit(n) = 1
    Y = []
    For I in 1 to |X|
        If (L(X(I))[n] == 1)
            Y.append(X(I))

    PrefixLess(L, Y, n-1)

    // go through subsequence on bit n-1 where bit(n) = 0
    Y = []
    For I in 1 to |X|
        If (L(X(I))[n] == 0)
            Y.append(X(I))

    PrefixLess(L, Y, n-1)

    return P

and then execute:

PrefixLess(L, 1..|L|, 32)