CODEWITHSUNDEEP
javacollectionsset
ndsfd ddsfd
ndsfd ddsfd

Reputation: 235

finding the non common element between two arrays

In an interview it was asked 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 have answered to the question that 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 query is that is there any other better approach to achieve this

Upvotes: 6

Views: 4786

Answers (6)

Maria Sakharova
Maria Sakharova

Reputation: 1379

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

Upvotes: 0

Makoto
Makoto

Reputation: 106430

In effect, this expands upon Jon Skeet's answer, but does so using Java 8's streams.

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 (through the short-circuiting terminal operator noneMatch), checking if the element is equal to anything in that stream.
  • Collect the results to a 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 issue with the non-Set code as pointed out was that it is quadratic time in the worst case. This code here takes advantage of the constant access time to Set#contains, and should run in about linear time.

Upvotes: 5

aioobe
aioobe

Reputation: 420990

If [x,y], [x,z] should yield [y,z] here's 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's already present
        set.remove(s);  // remove it from the result
}

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

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

Upvotes: 6

Jon Skeet
Jon Skeet

Reputation: 1500555

I would handle this in three steps:

  • Find all elements in a but not b
  • Find all elements in b but not a
  • Add those 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);

(The stream code in Java 8 may well make this simpler too...)

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

Upvotes: 3

singhakash
singhakash

Reputation: 7919

You can shorten the code by

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

Demo

Upvotes: 6

Saurabh Jhunjhunwala
Saurabh Jhunjhunwala

Reputation: 2922

Try this:

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);

Upvotes: 2

Related Questions