Java: Interleaving multiple arrays into a single array

Question

I found similar question about interleaving two arraylists into one, but its in PHP. I was asked this question in interview as well but could'nt solve it, came back to SO to look if it was addressed already, but i could only find this paper

So any pointers to pseudo code or method definition ?

Big(O) restrictions : O(n) - time cost and O(1) - space cost

Example:
a[]= a1, a2, ..., an
b[]= b1, b2, ..., bn
Rearrange the arraylist to a1, b1, a2, b2, ..., an, bn

Editv1.0 : Arraylists a[] and b[] are of same size

Editv2.0 : What if the question is extended to rearrange in one of given two arrays, but not create a new array ?

Answer 1

For simplicity, assume that the arrays are the same length, and are int arrays.

int[] merge(int[] a, int[] b)
{
    assert (a.length == b.length);

    int[] result = new int[a.length + b.length];

    for (int i=0; i<a.length; i++)
    {
        result[i*2] = a[i];
        result[i*2+1] = b[i];
    }

    return result;
}

Answer 2

I think this is not doable with your given constraints (O(n) time and O(1) space, i.e. no additional space) for an array or array-based list. (Assuming of course, that we can't simply create a new List object delegating to the original ones.)

If you have two linked lists, this is doable - if we assume the garbage collector is fast enough, i.e. deleting an element from one list and adding it to another list does not violate the space limitation.

public <X> void interleaveLists(List<X> first, List<X> second)
{
    ListIterator<X> firstIt = first.listIterator();
    ListIterator<X> secondIt = second.listIterator();
    while(secondIt.hasNext()) {
        fistIt.next();
        firstIt.add(secondIt.next());
        secondIt.remove();
    }
}

This method works for any pair of lists, but is only O(n) for linked lists.

For a custom linked list where we can modify the pointers, we don't have to rely on the garbage collector, we would simply change the nodes. Here for a singly-linked list:

public void interleaveLinkedLists(Node<X> firstList, Node<X> secondList) {
    while(secondList != null) {
        Node<X> nextFirst = firstList.next;
        Node<X> nextSecond = secondList.next;
        firstList.next = secondList;
        secondList.next = nextFirst;
        firstList = nextFirst;
        secondList = nextSecond;
    }
}

For a doubly-linked list, we would also have to adapt the prev-pointers.

Here the wrapping variant mentioned in the first paragraph:

public List<X> interleaveLists(final List<X> first, final List<X> second)
{
   if (first.size() != second.size())
      throw new IllegalArgumentException();
   return new AbstractList<X>() {
      public int size() {
         return 2 * first.size();
      }
      public X get(int index) {
         return index % 2 == 0 ? first.get(index / 2) : second.get(index / 2);
      }
      // if necessary, add a similar set() method.  add/remove are not sensible here.
   };
}

This is actually O(1) in time, too.

Answer 3

I've done up a small solution going on the assumption that you are talking about using the ArrayList (see my comment on the question). I may be oversimplifying the problem based on some of the responses here, but here goes anyway.

The below example takes a and b both of type ArrayList<Integer> and interleaves them by inserting b[0] after a[0], b[1] after a[1] etc. This snippet of course naively assumes that a and b are of the same size as per your Edit v1.0. It also does not create a new ArrayList as per your Edit v2.0.

//a and b are of type ArrayList<Integer>
for (int i = a.size(); i > 0; i--)
{
    a.add(i, b.get(i - 1));
}

No matter what happens if you are combining the ArrayLists you're going to have twice the size.

Answer 4

I believe the mod (%) operations in Matt's answer are incorrect. Under the same assumption (that the arrays are the same length), I'd propose the following solution instead:

static int[] merge(final int[] a, final int[] b)
{
    final int[] result = new int[a.length * 2];

    for (int i=0; i < a.length; i++)
    {
        result[i << 1] = a[i];
        result[(i << 1) + 1] = b[i];
    }

    return result;
}

I tested (very briefly), and it appears to work, but of course makes no attempt to handle error conditions such as null arguments or input arrays mismatched in size.

Answer 5

in the meantime lambda was introduced
O(n) time complexity
O(1) space complexity

int[] merge(int[] a, int[] b) {
    return( IntStream.range( 0, a.length ).flatMap(
        n -> IntStream.of( a[n], b[n] ) ).toArray() );
}

Answer 6

The lists don't have to be the same size:

public class InterleaveTwoLists<X> {

    public List<X> interleaveLists(final List<X> first, final List<X> second) {

        return new AbstractList<X>() {
            private int minSize;
            private int combinedMinSize;
            private int size;
            private List<X>largerList;
            {{
                minSize = Math.min(first.size(), second.size());
                combinedMinSize = minSize*2;
                size = first.size() + second.size();
                largerList = first.size() > minSize ? first : second;
            }}

            public int size() {
                return size;
            }

            public X get(int index) {
                if (index < combinedMinSize) {
                    return index % 2 == 0 
                        ? first.get(index / 2) 
                        : second.get(index / 2);
                }
                else { 
                    return largerList.get(index-minSize);
                }
            }
        };
    }
}

To test this:

public class InterleaveTwoListsTest {

    private static final Logger log = 
        LoggerFactory.getLogger(InterleaveTwoListsTest.class);

    List<String> first = new ArrayList<String>() {
    { 
        add("one"); add("three"); add("five"); 
        add("seven"); add("eight"); add("nine");
    }};

    List<String> second = new ArrayList<String>() {
    { 
        add("two"); add("four"); add("six"); 
    }};


    private InterleaveTwoLists<String> interleaveTwoLists;

    @Before
    public void setUp() throws Exception {
        interleaveTwoLists = new InterleaveTwoLists<>();
    }

    @Test
    public void test() {
        List<String> combinedList = interleaveTwoLists.interleaveLists(first, second);
        for( int i = 0; i < first.size() + second.size(); i++) { 
            log.debug("{}: {}", i, combinedList.get(i));
        }
    }
}