Remapping an array with O(1) space

Question

I'm sorry that I'm not sure what type is this problem called, let's just call it "Remapping", described as follows: Given a target char array, say A[], you have to manipulate A directly. And a remapping index array index[] containing indices where the value should be re-assigned. For example, given A[] = {a, b, c, d, e}, index[] = {2,4,3,0,1}. So index[0] = 2, which means after the manipulation, the value once in A[0] has to be A[2], A[1] is at A[4], etc. I know this problem is extremely easy if we have another array:

vector<char> myarr = vector<char>(A.size());
for (int i = 0; i < myarr.size(); i++)
    myarr[i] = A[index[i]];

// myarr is the answer.

But what should I do if I am only allowed O(1) space ? Thanks for sharing your opinion.

Oh btw, correct me if I have any grammar errors :"P

Well, a C++ array must have a constant size known at compile time. Any other array of the same size consequently has constant size, too. Which means you _are using_ O(1) memory. So... if you are being smart alec... :-) — Damon, Apr 12 '16 at 12:44
HINT: The problem that you have is what to do with the old value of `myArr[2]` (4) after doing `myArr[2] = 2`. Where would you write that 4 so it does not cost you extra space? Note that O(1) does not mean only one variable, you may have a constant number of variables. — SJuan76, Apr 12 '16 at 12:44
Sorry for the ambiguity, clarify it here: after the manipulation A[] should be {d, e, a, c, b}. I know what you mean, SJuan76, because the size of myarr is exactly same as given array A[]. But if we twice the size of A, so is myarr[]. so this method might have O(n) space complexity, cause the memory used would be in proportion to the given array, am I right ? — Shih-Chan Huang, Apr 12 '16 at 12:47
@Shih-ChanHuang What you are looking for is an algorithm that decomposes a permutation into transpositions. Since what you are trying to do can be achieved with a sequence of swapping. — freakish, Apr 12 '16 at 12:52
@Damon Algorithms are language independent and space complexity is always considered without the initial data: it's the amount of space the algorithm **itself** requires. The naive approach is `O(n)`. — freakish, Apr 12 '16 at 12:55
@freakish Thank you, you are absolutely right, what I'm expected for this problem is probably a sequence of swapping, but how ? — Shih-Chan Huang, Apr 12 '16 at 12:55
No, what I mean is that instead of iterating 0, 1, 2, ... you iterate `index[0], index[2], index[4]`, carrying on the value that was overwritten for the next replacement... the final solution is slightly more complicate because you have to take into account cycles (hint, once you have repositioned an item, put its value in the index array to `-1` to mark it). — SJuan76, Apr 12 '16 at 12:56
@SJuan76 Thank you, I am already working on the method you proposed, very very thanks. — Shih-Chan Huang, Apr 12 '16 at 13:13

score 3 · Accepted Answer · edited May 23 '17 at 11:45

3

The problem can be solved by swapping a pair of values with constant memory in order to generate the result in-place. Although not a direct duplicate, the problem is discussed in this question.

edited May 23 '17 at 11:45

Community

1
1

answered Apr 12 '16 at 12:46

Codor

17,447
9
29
56

thank you, sir. This is exact answer what I'm searching for, although the function of his indice array has a slight difference with mine. – Shih-Chan Huang Apr 12 '16 at 13:26

score 0 · Answer 2 · answered Apr 12 '16 at 13:42

you can do it using two variables; here is a rough sketch of the algorithm:

for i=0:n   
   t_index = i
   swap_index = index[t_index]   
   if index[i]!=-1:
       while t_index!=swap_index
          SWAP(index[t_index],index[swap_index])
          index[t_index] = -1
          t_index = getIndexOfValue(indexe, t_index)

The implementation of SWAP, which swaps two values and getIndexOfValue, which returns the index of a value from an array are not covered here; but they should be easy to figure out

The idea here is to keep track of the index of the value that has been swapped. After the first swap, the A[0] ends up in A[2], so you need to figure out where the value at index 0 in the original array needs to end up, ans swap it into position.....and so on.

Putting it on paper should help you see the full picture if you run into trouble

Remapping an array with O(1) space

2 Answers2