Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
@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
2  
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

2 Answers 2

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

share|improve this answer
    
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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.