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