# Finding number of smaller elements for each element in an array efficiently

I am stuck on this problem:

Given an array $A$ of the first $n$ natural numbers randomly permuted, an array $B$ is constructed, such that $B(k)$ is the number of elements from $A(1)$ to $A(k-1)$ which are smaller than $A(k)$.

i) Given $A$ can you find $B$ in $O(n)$ time?
ii) Given $B$ can you find $A$ in $O(n)$ time?

Here, $B(1) = 0$. For a concrete example: $$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$$

Can anyone help me? Thanks.

-
What have you tried? [Hint for part (ii): start from the back.] –  Merbs Nov 26 '12 at 0:31
I found this: Computing permutation encodings which gives $\mathcal O(n \log n)$ algorithms for these problems. At least I think they are the same problems. –  Realz Slaw Nov 26 '12 at 0:39
@Merbs does that Hint you gave mean that you have a solution ? –  AJed Nov 26 '12 at 3:22
@AJed, it means I have an algorithm, though it takes $O(n^2)$ for the simple algorithm without space and $O(n\log n)$ if we are allowed space. At the moment, I'm leaning towards neither being not possible in $O(n)$ and both being the same algorithm. –  Merbs Nov 26 '12 at 3:38
This paper also gives a $\mathcal O(n \log n)$ algorithm. Are you sure there exists an $\mathcal O(n)$ algorithm for this? –  Realz Slaw Nov 26 '12 at 12:46

The naive algorithm for determining $B$ from $A$:

For $k=1,\dots,n$, determine the value of $B(k)$ by comparing each $A(i)$ to $A(k)$ for $i=1,\dots,k$ and counting those that satisfy $A(i)<A(k)$.

This algorithm compares $A(1)$ to all others ($n-1$ times), $A(2)$ to $n-2$ others, etc. so the total number of comparisons is $\frac{(n-1)(n-2)}{2}$. But that's not the best we can do. For example, looking at $B(n)$, we don't have to do any comparisons! $B(n)=A(n)-1$ because it's the first $n$ natural numbers, and it’s guaranteed (regardless of the permutation) that the $n-1$ lower natural numbers will be there. What about $B(n-1)$? Instead of checking $A(1)$ through $A(n-2)$, we could just check $A(n)$. That is:

For $k=1, \dots,\frac{n}{2}$, use the algorithm above; for $k=\frac{n}{2},\dots,n$ use the reverse algorithm: determine $B(k)$ by setting it initially to $A(n)-1$ and then subtracting $1$ for each entry $A(i)$ for $i=k+1,\dots,n$ that is less than $A(k)$.

This would take $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ steps, which is still $O(n^2)$. Note also that in constructing $A$ from $B$, if $B(n)=A(n)-1$ then $A(n)=B(n)+1$.

But now for more finesse. If we’re allowed some additional space or sort in-place, we can sort the numbers as we’re comparing them. For example: $$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$$

Instead of checking all of them (or checking them in order), we could use binary search to determine each $B(k)$. However, the sorting still takes time $O(n\log n)$.

-
This was just my first idea; though I realize the problem is more interesting than I originally gave it credit. And I haven't had an opportunity yet to read Realz Slaw's findings, so the algorithm may be off. –  Merbs Nov 27 '12 at 1:44

Rather than determining each $B(k)$ one at a time, we can be forward looking and only go through each number in $A$ once! But we'll use $n$ space:

$$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$$

We could save even more time by not updating those that have already been determined (that is, there is no point in updating $8$ after the first step), but in the worst case, we still have to update $\frac{(n)(n+2)}{2}$ times

-