How to Merge Sorted Integer Arrays (Without Duplicates) in Java

  • Home /
  • Blog Posts /
  • How to merge sorted integer arrays (without duplicates) in Java

The challenge

Write a function that merges two sorted arrays into a single one. The arrays only contain integers. Also, the final outcome must be sorted and not have any duplicate.

Test cases

import org.junit.Test;
import static org.junit.Assert.assertArrayEquals;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.function.Function;
import java.util.stream.IntStream;

public class SolutionTest {

  @Test
  public void fixedTest() {

    assertArrayEquals(new int[] { 1, 2, 3, 4, 5, 6 }, Merger.mergeArrays(new int[] { 1, 3, 5 }, new int[] { 2, 4, 6 }));
    assertArrayEquals(new int[] { 2, 4, 6, 8 }, Merger.mergeArrays(new int[] { 2, 4, 8 }, new int[] { 2, 4, 6 }));
    assertArrayEquals(new int[] { 1, 2, 3 }, Merger.mergeArrays(new int[] { 1, 2, 3 }, new int[] {}));
    assertArrayEquals(new int[0], Merger.mergeArrays(new int[0], new int[0]));

    assertArrayEquals(IntStream.rangeClosed(1, 15).toArray(), Merger.mergeArrays(IntStream.rangeClosed(1, 10).toArray(), IntStream.rangeClosed(5, 15).toArray()));
    assertArrayEquals(new int[] { 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15 }, Merger.mergeArrays(IntStream.rangeClosed(1, 5).toArray(), IntStream.rangeClosed(10, 15).toArray()));
    assertArrayEquals(IntStream.rangeClosed(-5, 20).toArray(), Merger.mergeArrays(IntStream.rangeClosed(-5, 10).toArray(), IntStream.rangeClosed(-2, 20).toArray()));
  }

  private static final Random rnd = new Random();

  @Test
  public void randomTest() {

    for (int i = 0; i < 100; ++i) {

      int[] source = IntStream.generate(() -> { return rnd.nextInt(200) - 100; }).limit(200).distinct().sorted().toArray();
      List<Integer> one = new ArrayList<>();
      List<Integer> two = new ArrayList<>();

      for (int num : source) {

        (rnd.nextBoolean() ? one : two).add(num);

        if (rnd.nextInt(10) < 2)
          (rnd.nextBoolean() ? one : two).add(num);

      }

      Function<List<Integer>, int[]> asPrimitive = array -> array.stream().mapToInt(n -> n.intValue()).toArray();
      assertArrayEquals(source, Merger.mergeArrays(asPrimitive.apply(one), asPrimitive.apply(two)));
    }
  }
}

The solution in Java

Option 1 (using streams):

import java.util.stream.*;

public class Merger {
	public static int[] mergeArrays(int[] first, int[] second) {
    int[] merged = IntStream
        .concat(IntStream.of(first), IntStream.of(second))
        .distinct()
        .sorted()
        .toArray();
    
		return merged;
	}
}

Option 2 (using TreeSet):

import java.util.TreeSet;

public class Merger {
  public static int[] mergeArrays(int[] first, int[] second) {
    TreeSet<Integer> set = new TreeSet<>();
        
    for (int x : first) set.add(x);
    for (int x : second) set.add(x);

    return set.stream().mapToInt(Integer::intValue).toArray();
  }
}