missing elements from two arrays in java

Question

How can we find out missing elements from two arrays ? Ex:

        int []array1 ={1,2,3,4,5};           
        int []array2 ={3,1,2};

From the above two arrays i want to find what are the missing elements in second array?

Answer 1

Convert them to Sets and use removeAll.

The first problem is how to convert a primitive int[] to a collection. With Guava you can use:

List<Integer> list1 = Ints.asList(array1);
List<Integer> list2 = Ints.asList(array2);

Apache commons (which I'm not familiar with) apparently has something similar.

Now convert to a set:

Set<Integer> set1 = new HashSet<Integer>(list1);

And compute the difference:

set1.removeAll(list2);

And convert the result back to an array:

return Ints.toArray(set1);

Answer 2

If you are allowed duplicates in the arrays, an efficient (O(n)) solution it to create a frequency table (Map) by iterating over the first array, and then use the map to match off any elements in the second array.

Map<Integer, Integer> freqMap = new HashMap<Integer, Integer>();

// Iterate over array1 and populate frequency map whereby
// the key is the integer and the value is the number of
// occurences.
for (int val1 : array1) {
  Integer freq = freqMap.get(val1);

  if (freq == null) {
    freqMap.put(val1, 1);
  } else {
    freqMap.put(val1, freq + 1);
  }
}

// Now read the second array, reducing the frequency for any value
// encountered that is also in array1.
for (int val2 : array2) {
  Integer freq = freqMap.get(val2);

  if (freq == null) {
    freqMap.remove(val2);
  } else {
    if (freq == 0) {
      freqMap.remove(val2);   
    } else {
      freqMap.put(freq - 1);
    }
  }
}

// Finally, iterate over map and build results.
List<Integer> result = new LinkedList<Integer>();

for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
  int remaining = entry.getValue();

  for (int i=0; i<remaining; ++i) {
    result.add(entry.getKey());
  }
}

// TODO: Convert to int[] using the util. method of your choosing.