Finding a non-shared element between two arrays

Question

In an interview, it was suggested to find non-common elements between two string arrays.

Eg: String a[]={"a","b","c","d"}; String b[]={"b","c"}; O/p should be a,d 

I answered the question what in Java Set is implemented using HashTable. The code with Set is much simpler:

 String[] a = {"a","b","c","d"}; String[] b = {"b", "c"}; Set<String> set = new HashSet<>(a.length); for(String s : a){ set.add(s); } for(String s : b){ set.remove(s); } return set; 

now my request is that there is another better approach to achieve this

Answer 1

If [x,y], [x,z] should give [y,z] here what I suggest:

 String[] a = {"a","b","c","d"}; String[] b = {"b", "c", "x"}; Set<String> set = new HashSet<>(Arrays.asList(a)); for (String s : new HashSet<>(Arrays.asList(b)) { if (!set.add(s)) // if it already present set.remove(s); // remove it from the result } 

If, on the other hand, [x,y], [x,z] should give [y] , I would suggest

 Set<String> set = new HashSet<>(Arrays.asList(a)); set.removeAll(Arrays.asList(b)); 

Answer 2

You can shorten the code by

 TreeSet set = new TreeSet(Arrays.asList(a)); set.removeAll(Arrays.asList(b)); 

Demo

Answer 3

Essentially, this extends to John Skeet's answer, but does it using Java 8 threads.

 String[] result = Arrays.stream(a) .filter((s) -> Arrays.stream(b).noneMatch(s::equals)) .toArray(String[]::new); System.out.println(Arrays.toString(result)); 

The main tenants of the code are:

• Filter out any element contained in A if and only if it does not exist in B (via the noneMatch short-circuit terminator operator), checking whether this element is equal to anything in this stream.
• Collect the results in String[] .

Another approach using Set and again using streams:

 Set<String> setA = new HashSet<>(Arrays.asList(a)); Set<String> setB = new HashSet<>(Arrays.asList(b)); String[] setResult = setA.stream() .filter((s) -> !setB.contains(s)) .toArray(String[]::new); 

The main problem with the non-Set code, as indicated, is that it is the quadratic time in the worst case. This code here uses the constant access time to Set#contains and should work for approximately linear time.

Answer 4

I would handle this in three steps:

• Find all elements in a but not b
• Find all elements in b but not a
• Add these two sets together

So for example:

 Set<String> aSet = new HashSet<>(Arrays.asList(a)); Set<String> bSet = new HashSet<>(Arrays.asList(b)); Set<String> aNotB = new HashSet<>(aSet); aNotB.removeAll(bSet); Set<String> bNotA = new HashSet<>(bSet); bNotA.removeAll(aSet); Set<String> onlyOne = new HashSet<>(aNotB); onlyOne.addAll(bNotA); 

(Stream code in Java 8 can also make this easier ...)

The code can be made shorter if you don't mind changing aSet and bSet , but I find this version easier to read.

Answer 5

Try the following:

 String a[]={"a","b","c","d"}; String b[]={"b","c"}; List aLst = new ArrayList(Arrays.asList(a)); List bLst = new ArrayList(Arrays.asList(b)); aLst.removeAll(bLst); System.out.println(aLst); 

Answer 6

If the strings are only English letters (or over a small alphabet .. even ASCII), I would rather use the value boolean [] by char instead of HashSets, etc., to slightly improve performance.