CODEWITHSUNDEEP
javaarrayssortingmerge
Luiz Gabriel Ferreira
Luiz Gabriel Ferreira

Reputation: 61

How can i merge three ordered arrays in one ordered array? In O(n)

My code should pick three arrays and return a combination of the three, the arrays can have different length. The code should do the combination in O(n).

Example: a[] = {1,2} b[] = {1,4,5} c[] = {2,4,5,6}

My result should be: d[] = {1,1,2,2,4,4,5,5,6}

Upvotes: 0

Views: 49

Answers (2)

Muhammed Imran Hussain
Muhammed Imran Hussain

Reputation: 2125

[Answered before O(n) constraint added in question edit.]

Add all arrays to list and sort again. An example would be:

Integer[] a = {1, 2};
Integer[] b = {1, 4, 5};
Integer[] c = {2, 4, 5, 6};

List<Integer> lists = new ArrayList<>();
lists.addAll(Arrays.asList(a));
lists.addAll(Arrays.asList(b));
lists.addAll(Arrays.asList(c));

//print
lists
  .stream()
  .sorted()
  .forEach(System.out::println);

Upvotes: 2

Jason
Jason

Reputation: 11832

One approach (and I am sure there are many others) would be:

Create the output array based on the sum of the input array lengths:

int[] output = new int[a.length + b.length + c.length];

Create an index pointer for each of the input arrays:

int aIndex = 0;
int bIndex = 0;
int cIndex = 0;

Loop once for each position in the output array, and fill it with the lowest value at the current index of each input array (checking that we haven't used that array up):

for(int outputIndex = 0; outputIndex < output.length; outputIndex++) {
    if (aIndex < a.length
            && (bIndex >= b.length || a[aIndex] <= b[bIndex])
            && (cIndex >= c.length || a[aIndex] <= c[cIndex])) {
        output[outputIndex] = a[aIndex];
        aIndex++;
    } else if (bIndex < b.length
            && (aIndex >= a.length || b[bIndex] <= a[aIndex])
            && (cIndex >= c.length || b[bIndex] <= c[cIndex])) {
        output[outputIndex] = b[bIndex];
        bIndex++;
    } else {
        output[outputIndex] =  c[cIndex];
        cIndex++;
    }
}

Edit: Here's my compiled and tested code:

public class Join {

    public static void main(String[] args) {
        int[] a = {1, 2};
        int[] b = {1, 4, 5};
        int[] c = {2, 4, 5, 6};

        int[] output = new int[a.length + b.length + c.length];

        int aIndex = 0;
        int bIndex = 0;
        int cIndex = 0;

        for(int outputIndex = 0; outputIndex < output.length; outputIndex++) {
            if (aIndex < a.length
                    && (bIndex >= b.length || a[aIndex] <= b[bIndex])
                    && (cIndex >= c.length || a[aIndex] <= c[cIndex])) {
                output[outputIndex] = a[aIndex];
                aIndex++;
            } else if (bIndex < b.length
                    && (aIndex >= a.length || b[bIndex] <= a[aIndex])
                    && (cIndex >= c.length || b[bIndex] <= c[cIndex])) {
                output[outputIndex] = b[bIndex];
                bIndex++;
            } else {
                output[outputIndex] =  c[cIndex];
                cIndex++;
            }
        }
    }
}

Verified in debugger with a breakpoint at the end of the method.

Upvotes: 2

Related Questions