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

Question

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.

• Realz Slaw: 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.
• AJed: @Merbs does that Hint you gave mean that you have a solution ?
• Merbs: @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.
• AJed: @Merbs. I feel your hint can lead to the right track. i m having one solution too (following your hint). I guess there is a trick in the analysis that makes it go to $O(n)$.. I think the trick is the knowledge that $A$ goes from 1:$n$ only.
• Realz Slaw: This paper also gives a $\mathcal O(n \log n)$ algorithm. Are you sure there exists an $\mathcal O(n)$ algorithm for this?

Answer 1

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)$.

• Merbs: 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.

Answer 2

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

Answer 3

both I and II are solvable using #next_greater_element that i explained here. but its a little harder than just the problem but before solution you need to learn next greater element:

1. consider we have a vector for every element of $A$ name it $S_i$ for element $i$. now once run the next greater algorithm starting from right to left but except setting element $i$ in $A$ its next greater element index , push in $S_i$ the elements that $i$ is their next greater element.then iterate over the array left to right and then $B[i]=\sum_{j=0}^x (S_i[j]+1)$ where $x$ is the size of vector $S_i$.and its $\Theta(n)$ because each the next greater algorithm is $\Theta(n)$ and also iterating is $\Theta(n)$

second part is also similar noting that we can get the value of the rightest element in $O(1)$ EDIT:my solution is wrong it seems that it dont have any$o(n)$ solution