I am using one-based indexing when I discuss this problem, not zero-based indexing.
Suppose you are given two arrays, A and LOC, both of length n.
The array A contains elements in an order that is not necessarily sorted. For instance, we can have A = {40, 80, 30, 60, 10, 70, 20, 50}.
On the other hand, LOC[i] represents the index of the ith smallest element of A. In this case, we'd have LOC = {5, 7, 3, 1, 8, 4, 6, 2}. For instance, LOC[1] = 5. This means that 5 is the index of the 1st smallest element (which is true because A[5] = 10, and 10 is the smallest element).
PROBLEM: Given the array A and LOC, construct a new array ANS such that ANS[i] is the rank of the ith element in A. You may not modify the original array ANS, and you can only use an extra n bits along with a constant amount of memory (that is, you can only use n + O(log n) extra bits of memory). The answer you return must be LOC modified. So you cannot create a new array ANS to return the value. It needs to be in-place.
For our example, we are given A = {40, 80, 30, 60, 10, 70, 20, 50} and LOC = {5, 7, 3, 1, 8, 4, 6, 2}. The expected output would be ANS = {4, 8, 3, 6, 1, 7, 2, 5}. For example, ANS[2] is the rank of the 2nd element in ANS. The 2nd element in ANS is 80 (which is the max value), so it has rank 8.
This problem can supposedly be solved in linear time, but I can only come up with the bruteforce n^2 algorithm. What am I missing? How can this be done?
Thanks
Can't you just do for (int i = 1; i <= n; ++i) ANS[LOC[i]] = i; ?
for every element LOC[i] = j make ANS[j] = i
What is the problem source?
Let's rephrase the problem. We need to convert a permutation in place into its inverse permutation $$$I$$$ and we have a comparison oracle (the array $$$A$$$) that tells us for any $$$i$$$ and $$$j$$$ if $$$I_i \lt I_j$$$.
A permutation graph with edges $$$i \rightarrow P_i$$$ is a set of cycles. In the inverse permutation, the edges are reversed. We just need to walk along all cycles and reverse the edges; when we're at an index $$$b$$$ and in the original graph, there was an edge $$$a \rightarrow b$$$ that we just reversed and an edge $$$b \rightarrow c$$$ that we haven't reversed ($$$c = P_b$$$ originally but we need to remember it in an extra variable), then this part of the graph looks like $$$a \leftarrow b \rightarrow c \rightarrow P_c$$$. Let's reverse the edge between $$$b$$$ and $$$c$$$ (change the element at index $$$c$$$ to $$$b$$$), update the variable $$$c$$$ to $$$P_c$$$, $$$b$$$ to $$$c$$$ and continue until we reach the point where we started. The extra bits come into play because we need to remember which elements are in cycles we've already processed. Basically, we're walking along a cycle, setting LOC[LOC[i]] = i in a way that will break just one thing and remembering that thing.
Turns out this doesn't even need the oracle. I'm not sure if it's right, but seems so.