How to reorder a char array using an int array as the order without any extra space in O(n)?

Question

This is a phone interview question:

Rearrange charArray in place such that it matches the order of intArray.

example:

input:

intArray: {4,2,3,0,1}
charArray:{'A','B','C','D','E'}

expected:

code should change charArray to

{'E','C','D','A','B'}

explanation:

charArray = [charArray [4] ='E',charArray [2]='C',charArray [3]='D',charArray [0]='A',charArray [1]='B'];


[E, C, D, A, B]

You cannot use mapping or any other extra space. You can only make change in place.

Ilya Kharlamov · Answer 1 · 2021-04-10T08:54:04.510

2

Another option is to use the intArray as extra storage: O(N)

for(int i=0; i<intArray.length; i++) {
    intArray[i] = (int) charArray[intArray[i]];
}
for(int i=0; i<intArray.length; i++) {
    charArray[i] = (char) intArray[i];
}

For arrays smaller than 2^16 it's possible to restore the original int array by storing the char in the upper 16 bits:

int[] intArray = new int[]{4,2,3,0,1};
char[] charArray = new char[]{'A','B','C','D','E'};
for(int i=0; i<intArray.length; i++) {
    intArray[i] |= (charArray[intArray[i]] << 16);
}
for(int i=0; i<intArray.length; i++) {
    charArray[i] = (char) (intArray[i] >> 16);
    intArray[i] &= 0xFFFF;
}

edited Apr 10 '21 at 08:54

answered Apr 10 '21 at 07:38

Ilya Kharlamov

3,698
1
31
33

Very good solution by reusing the input space. – Thiyanesh Apr 10 '21 at 19:24
It looks good. However, an interviewer told me that never change the input in your solution during another interview. – Paul Apr 11 '21 at 05:21

score 1 · Accepted Answer · answered Apr 10 '21 at 06:04

1

One solution is to solve this recursively. Though it doesn't allocate an explicit new array, it uses a stack for recursion and hence it uses implicit space.

public static void main(String[] args) {
    int[] a = {4, 2, 3, 0, 1};
    char[] c = {'A', 'B', 'C', 'D', 'E'};
    System.out.println(c); //ABCDE
    solve(a, c, 0, c[a[0]]);
    System.out.println(c); //ECDAB
}

private static void solve(int[] a, char[] c, int i, char charValue) {
    if (i + 1 < c.length) {
        solve(a, c, i + 1, c[a[i + 1]]);
    }
    c[i] = charValue;

}

answered Apr 10 '21 at 06:04

Thiyagu

17,362
5
42
79

Although, it seems recursion is using O(1) extra space. Actually, this recursion solution is using O(N) extra space since it will repeat N times. Not sure if it is what the interviewer expected. – Paul Apr 11 '21 at 05:18
Yes, that is right. Refer to the linked dupe post – Thiyagu Apr 11 '21 at 05:50

score 0 · Answer 3 · answered Apr 10 '21 at 06:42

Similar to user7's approach, but using a loop to find position of character every time:

public class Solution {
    public static void main(String[] args) {
        char ch[] = new char[] { 'A', 'B', 'C', 'D', 'E' };
        arrange(new int[] { 1, 3, 2, 0, 4 }, ch);
        System.out.print(ch); // EDCAB
        
    }

    private static void arrange(int[] inArr, char[] chrArr) {
        arrange(inArr, chrArr, 0, 0);
    }

    private static void arrange(int[] inArr, char[] chrArr, int index, int count) {
        if (count == inArr.length)
            // seen all elements
            return;
        char c = chrArr[index];
        int t = -1;
        /*
         * Find what place, say, t, does c belong to. Then, 
         * recursively find which place
         * does the element at t belong to.
         * 
         * Continue till you have seen all the elements (count == arrays' length)
         */

        for (int i = 0; i < inArr.length; i++) {
            if (inArr[i] == index) {
                t = i;
                break;
            }
        }
        arrange(inArr, chrArr, t, count + 1);
        chrArr[t] = c;
    }
}

How to reorder a char array using an int array as the order without any extra space in O(n)?

3 Answers3