Programming Interview Questions 9: Convert Array

Given an array:

[a_1, a_2, ..., a_N, b_1, b_2, ..., b_N, c_1, c_2, ..., c_N ]

convert it to:

[a_1, b_1, c_1, a_2, b_2, c_2, ..., a_N, b_N, c_N]

in-place using constant extra space.

This is a tricky question because we could solve it pretty easily if were allowed to construct a new array. The element at the ith position in the final array is at position (i%3)*N + i/3 in the original array. So, the code is simply:

def getIndex(currentIndex, N):
    return (currentIndex%3)*N + (currentIndex/3)
 
def convertArray_extraSpace(arr):
    N=len(arr)/3
    return [arr[getIndex(i, N)] for i in range(len(arr))]

The getIndex function takes an index from the final array, and returns the index of the element in the original array that should appear at that position. However, we aren’t allowed use extra space, we should instead modify the array in-place. We could use a similar approach though, at each iteration we can put the ith element to its final location using the getIndex function above and swap elements. The algorithm works as follows, at each iteration (currentIndex) we get the index of the item that should appear at that location (swapIndex) by calling the getIndex function. The element at swapIndex is the final element to appear at currentIndex. So we swap the elements at currentIndex and swapIndex, if swapIndex>=currentIndex. But if swapIndex<currentIndex then it means that the element at swapIndex was replaced with another element at previous iterations. Now it’s somewhere else and we should keep looking for that element. We again call getIndex with swapIndex as new input to find the element it was replaced with. If the new swapIndex>=currentIndex, we swap the elements as before. Otherwise, we repeat this procedure until swapIndex>=currentIndex, which is we find the final element that’s supposed to appear at currentIndex. The code will make everything clear:

def convertArray(arr):
    N=len(arr)/3
    for currentIndex in range(len(arr)):
        swapIndex=getIndex(currentIndex, N)
        while swapIndex<currentIndex:
            swapIndex=getIndex(swapIndex, N)
        arr[currentIndex], arr[swapIndex] = arr[swapIndex], arr[currentIndex]

The algorithm is pretty simple and in-place without using extra space. Let’s work through an example to clarify, here is the program flow for an array of size 15. Swap index is calculated multiple times for some elements until swapIndex>=currentIndex as explained above.

currentIdx=0, swapIdx=0, swapIdx>=currentIdx, swap arr[0] arr[0]
currentIdx=1, swapIdx=5, swapIdx>=currentIdx, swap arr[1] arr[5]
currentIdx=2, swapIdx=10, swapIdx>=currentIdx, swap arr[2] arr[10]
currentIdx=3, swapIdx=1, swapIdx<currentIdx, no swap
  swapIdx=1, newSwapIdx=5, newSwapIdx>=currentIdx, swap arr[3] arr[5]
currentIdx=4, swapIdx=6, swapIdx>=currentIdx, swap arr[4] arr[6]
currentIdx=5, swapIdx=11, swapIdx>=currentIdx, swap arr[5] arr[11]
currentIdx=6, swapIdx=2, swapIdx<currentIdx, no swap
  swapIdx=2, newSwapIdx=10, newSwapIdx>=currentIdx, swap arr[6] arr[10]
currentIdx=7, swapIdx=7, swapIdx>=currentIdx, swap arr[7] arr[7]
currentIdx=8, swapIdx=12, swapIdx>=currentIdx, swap arr[8] arr[12]
currentIdx=9, swapIdx=3, swapIdx<currentIdx, no swap
  swapIdx=3, newSwapIdx=1, newSwapIdx<currentIdx, no swap
  swapIdx=1, newSwapIdx=5, newSwapIdx<currentIdx, no swap
  swapIdx=5, newSwapIdx=11, newSwapIdx>=currentIdx, swap arr[9] arr[11]
currentIdx=10, swapIdx=8, swapIdx<currentIdx, no swap
  swapIdx=8, newSwapIdx=12, newSwapIdx>=currentIdx, swap arr[10] arr[12]
currentIdx=11, swapIdx=13, swapIdx>=currentIdx, swap arr[11] arr[13]
currentIdx=12, swapIdx=4, swapIdx<currentIdx, no swap
  swapIdx=4, newSwapIdx=6, newSwapIdx<currentIdx, no swap
  swapIdx=6, newSwapIdx=2, newSwapIdx<currentIdx, no swap
  swapIdx=2, newSwapIdx=10, newSwapIdx<currentIdx, no swap
  swapIdx=10, newSwapIdx=8, newSwapIdx<currentIdx, no swap  
  swapIdx=8, newSwapIdx=12, newSwapIdx>=currentIdx, swap arr[12] arr[12]
currentIdx=13, swapIdx=9, swapIdx<currentIdx, no swap
  swapIdx=9, newSwapIdx=3, newSwapIdx<currentIdx, no swap
  swapIdx=3, newSwapIdx=1, newSwapIdx<currentIdx, no swap
  swapIdx=1, newSwapIdx=5, newSwapIdx<currentIdx, no swap
  swapIdx=5, newSwapIdx=11, newSwapIdx<currentIdx, no swap
  swapIdx=13, newSwapIdx=13, newSwapIdx>=currentIdx, swap arr[13] arr[13]
currentIdx=14, swapIdx=14, currentIdx>=swapIdx, swap arr[14] arr[14]

The time complexity of this algorithm depends on the number of times getIndex function is called. It’s not linear because for some indexes the getIndex function is called multiple times, it’s not quadratic as well because not for every element the getIndex is called repetitively. We can see both of the cases above. So, the complexity is between linear and quadratic, which is sometimes called as super-linear. To be precise, the complexity is approximately O(N^1.3) as we can see from the figure below:

Here is the code to generate the plot, assuming that we changed the function convertArray to also count and return the number of calls made to getIndex function:

def complexityAnalysis():
    x=range(3, 1000, 3)
    y=[convertArray(range(num)) for num in x]
    pylab.plot(x, sorted(y), label='convertArray')
    pylab.plot(x, map(lambda num: num**1.2, x), label='x^1.2')
    pylab.plot(x, map(lambda num: num**1.3, x), label='x^1.3')
    pylab.legend(loc='upper left')
    pylab.title('Complexity of convertArray')
    pylab.xlabel('array length')
    pylab.ylabel('number of getIndex calls')
    pylab.show()
VN:F [1.9.22_1171]
Rating: 7.1/10 (15 votes cast)
Programming Interview Questions 9: Convert Array, 7.1 out of 10 based on 15 ratings

This entry was posted in Programming Interview. Bookmark the permalink.
  • Ori

    Isn’t the index you use for swapIndex takes extra space? why not use XOR swap?

    • Arden

      Yes you’re right, I didn’t do XOR swap to keep the algorithm simple. Using a single extra variable should be fine, but I’ll modify the question definition to ‘constant extra space’ to avoid further confusion.

  • ANONYMOUS

    another solution:
    divide the original array’s a[1..n] as items in group of size 3, that is [a1, a2, a3] [a4, a5, a6] … you can manual swap [a1, a2, a3] [b1, b2, b3], [c1, c2, c3] into [a1, b1, c1, a2, b2,c2, a3, b3,c3]. then repeat the same steps for group 2, that is [a4, a5, a6],[b4, b5, b6], [c4,c5,c6] can get result [a1, b1, c1, a2, b2,c2, a3, b3,c3, a4, b4, c4, a5, b5,c5, a6,b6,c6].

    • ANONYMOUS

      the constant extra space is 9

    • ANONYMOUS

      ooopse, it seems not going to work…

  • Aditya

    Another solution:


    def convert(a, N, i):
    r = i % (N/3)
    d = int(i / (N/3))
    n = r * 3 + d
    if a[n] == None:
    a[n] = a[i]
    return
    t = a[i]; a[i] = None
    convert(a, N, n)
    a[n] = t
    return a

    convert([1,2,3,4,5,6,11,22,33,44,55,66,111,222,333,444,555,666], 18, 1)

    At each stage, starting with 2nd position, the element is placed at its correct location. Is some other element is present, the function is called recursively. This should be a linear time solution since at the entire list is traversed once.

    • Glenn C

      Please name your variables so that they assist in understanding your intent/algorithm.

      That or name your function c(…) to be consistent with your naming scheme -_-

  • Jaan Pakodi

    The code won’t work for cases when N=4 i.e. input = {a1,a2,a3,a4,b1,b2,b3,b4,c1,c2,c3,c4}

    • Arden

      Why not? I get the correct result:
      >>> convertArray(range(12))
      [0, 4, 8, 1, 5, 9, 2, 6, 10, 3, 7, 11]

      • Aditya

        Ah.. I see..
        @Jaan: This can be resolved by a minor tweek of calling convert again with last parameter as 2.

  • http://skyline skyline

    There is a recursive approach:
    [a_1, a_2, ..., a_N, b_1, b_2, ..., b_N, c_1, c_2, ..., c_N ]
    we move it manually to
    [(a_1, a_2, ..., a_N-1, b_1, b_2, ..., b_N-1, c_1, c_2, ..., c_N-1), a_N, b_N, c_N ]
    the left part is a recursive part.
    it is resolved into
    [(a_1, b_1, c_1, a_2, b_2, c_2... a_N-1,b_N-1 c_N-1), a_N, b_N, c_N ]

  • NG

    There is an O(n) and O(1) space algorithm. I will leave you to sweat it out.

    When you give up, search for inshuffle algorithm on the web.

  • http://web.iiit.ac.in/~avinash.jain/ Avinash Jain

    Can any buddy please explain how i’th index in the final array mapped to (i%3)*N + i/3

    • Sorrowfull Blinger

      (i%3) – tells you if its a , b or c that is chosen
      (i%3 )*N – moves the pointer to the start of that elements series in original array.
      i/3 -will give index of that element in an array having only that type.

      Analogous to Page table lookup in OS

      i%3 *N – Tells you the Page no
      adding i/3 – tells you the offset in the page

  • rainyvale

    I came up with a solution:

    Convert [a1,a2,a3,b1,b2,b3,c1,c2,c3] to [a1,b1,c1,a2,b2,c2,a3,b3,c3], which takes three swaps. Repeat this for every set of 9 elements.

    Then, take [a1,b1,c1] as one unit and do the same procedure,
    and you will get [a1,b1,c1,... a9,b9,c9], which takes 3×3=9 swaps. Repeat this for every set of 27 elements.

    Then, take [a1,b1,c1,... a9,b9,c9] as one unit and do the same procedure,
    and you will get [a1,b1,c1,... a27,b27,c27], which takes 3×9=27 swaps. Repeat this for every set of 81 elements.

    (In practice we need take care of the case N%3!=0.)

    Complexity looks like N (swaps/stage) x log_3 N stages = N log_3 N swaps. But, it would be fast in practice by using memcpy() for later stages rather than swap().

    Does it sound right?

  • drjerry

    I’m loving these comments! Evidently no one here has spent anytime doing linear algebra in a language like Fortran or C. (Maybe that’s a good thing.)

    All matrices (Matlab, NumPy, etc.) are implemented as 1-dimensional arrays and use index arithmetic to access elements. For instance, “a(i, j)” is a[i * N + j] for a M-by-N matrix in row major form. The array given in the statement is just a 3-by-N matrix in row major form. The problem is to build the transpose of that matrix. This can be done in place and requires only one element of swap space. (Or use XOR swap, as pointed out elsewhere.)

    • Picked Name

      Please, englighten us.

  • Jun Yu

    I think this can be done in O(n). Correct me if I am wrong.

    The idea is that each element in the original array, we find the position in the output array. Note that the ith element in the original array will be swapped to another position k where k % 3 == i % 3. For example, the first element in the original array will be swapped to a position whose index mod 3 is zero. Every swap makes one element in the right postion in the output array. Here is the code for this:

    public static int convertArrayHelper(int i, int n) {
    int index = i / n + i % n * 3;
    return index;
    }

    public static int[] convertArray(int[] arr, int n) {
    for (int i = 0; i < 3; i++) {
    int index = convertArrayHelper(i,n);
    while (index != i) {
    int tmp = arr[index];
    arr[index] = arr[i];
    arr[i] = tmp;

    index = convertArrayHelper(index,n);
    }
    }
    return arr;
    }

  • foo

    Why not?

    def foo(l):
    return zip(l[0:len(l)/3],l[len(l)/3:2*len(l)/3],l[2*len(l)/3:])

    • foo

      this is probably more attuned with the expected result:

      def foo(l):
      return[j for i in zip(l[0:len(l)/3],l[len(l)/3:2*len(l)/3],l[2*len(l)/3:]) for j in i]

  • indulge

    Solution coded in java, for symmetric input, where number of elements in set is equal to number of sets within array, there is a optimization we can do (see convertArraySymm function), in this case, we always have swap in pairs, so any swap will put both elements in correct position, so, once we have swapped half the elements we can be sure that it’s done.

    package sg.problems.blog1;

    import java.util.Arrays;

    public class ConvertArray {

    private int numOfSets;
    private int lengthOfSet;

    private void swap(int[] arr, int prevpos, int newpos) {
    int temp = arr[prevpos];
    arr[prevpos] = arr[newpos];
    arr[newpos] = temp;
    }

    private int getNewPos(int index) {
    int newpos = (index%numOfSets) * lengthOfSet + (index/numOfSets);
    return newpos;
    }

    public int[] convertArraySymm(int[] arr) {
    // System.out.println(“number of sets: “+numOfSets+” lengthOfSet: “+lengthOfSet);

    for (int i = 0; i < lengthOfSet; i++) {
    for (int j = i; j < numOfSets; j++) {
    int prevpos = i * numOfSets + j;
    int newpos = getNewPos(prevpos);
    swap(arr, prevpos, newpos);
    }
    }

    return arr;
    }

    public int[] convertArray(int[] arr, int lengthOfSet) {

    this.numOfSets = arr.length/lengthOfSet;
    this.lengthOfSet = lengthOfSet;
    if (this.numOfSets == this.lengthOfSet) {
    System.out.println("[symmetric input] ");
    return convertArraySymm(arr);
    }
    // System.out.println("number of sets: "+numOfSets+" lengthOfSet: "+lengthOfSet);

    for (int i = 0; i < lengthOfSet; i++) {
    for (int j = 0; j < numOfSets; j++) {

    int prevpos = i * numOfSets + j;
    int newpos = getNewPos(prevpos);

    // int newpos = getNewPosForElem(i, j, lengthOfSet);
    // int newpos = i + lengthOfSet * j;
    int k = 0;
    while (newpos “);
    k++;
    }
    newpos = getNewPos(newpos);
    // System.out.print(“(“+newpos+”) –>”);
    }
    // System.out.println(” prevpos: “+prevpos + ” newpos: ” + newpos);

    swap(arr, prevpos, newpos);
    // System.out.println(Arrays.toString(arr));

    }
    }

    return arr;
    }

    public void test(int lengthOfSet, int numSets) {
    System.out.println(“”);
    System.out.println(“lengthOfSet: “+ lengthOfSet + ” numSets: “+numSets);
    int length = lengthOfSet * numSets;
    int[] arr = new int[length];
    for (int i = 0; i < numSets; i++) {
    for (int j = 0; j < lengthOfSet; j++) {
    //arr[i * lengthOfSet + j] = j;
    arr[i * lengthOfSet + j] = i * lengthOfSet + j;
    }
    }
    System.out.println(Arrays.toString(arr));
    convertArray(arr, lengthOfSet);
    System.out.println(Arrays.toString(arr));
    System.out.println("");
    }
    public static void main(String[] args) {
    ConvertArray test = new ConvertArray();

    int lengthOfSet = 4;
    int numSets = 3;
    test.test(lengthOfSet, numSets);

    lengthOfSet = 3;
    numSets = 3;
    test.test(lengthOfSet, numSets);

    lengthOfSet = 2;
    numSets = 4;
    test.test(lengthOfSet, numSets);

    }
    }

  • Sorrowfull Blinger

    is there a proof for the complexity not going beyond O(n^1.3) … wont there be any worst case which would require more swaps than just 1 in each iteration??

    • vickychijwani

      That’s what I thought.