CODEWITHSUNDEEP
javaalgorithmtime-complexity
Atif Imran
Atif Imran

Reputation: 2049

Find unique items from two arrays

I was wondering what could be a better solution that could produce less complexity than O(n^2) when printing unique items from two arrays. Any ideas?

    int[] a = {1,2,4,5,8};
    int[] b = {3,2,5,7,8};

    ArrayList unMatch = new ArrayList() ;
    for(int i=0; i<a.length; i++){
        boolean contains = false;
        innerloop:
            for(int k =0; k<b.length; k++){
                if(a[i]==b[k]){
                    contains = true;
                    break innerloop;
                }
            }
        if(!contains){
            unMatch.add(a[i]);
        }

    }
    for(int i=0; i<b.length; i++){
        boolean contains = false;
        innerloop:
        for(int k =0; k<a.length; k++){
            if(b[i]==a[k]){
                contains = true;
                break innerloop;
            }
        }
        if(!contains){
            unMatch.add(b[i]);
        }
    }

Output: [1,4,3,7]

Upvotes: 3

Views: 3579

Answers (3)

karzler007
karzler007

Reputation: 111

Use of Set can reduce your complexity. Sets don't allow duplicates. Sets can be:

  1. HashSet - HashSet is implemented using a hash table. Elements are not ordered. The add, remove, and contains methods have constant time complexity O(1).
  2. LinkedHashSet - uses Trees (RB-Trees). Elements are not ordered. Complexity for the same methods is O(log n)
  3. TreeSet - uses a hash table with a linked list running through it. Elements are ordered. The time complexity of the same methods is O(1).

E.g.

    HashSet<Integer> set = new HashSet<>();
    for(int n : a) {
        set.add(n);
    }
    for (int n : b) {
        set.add(n);
    }

So, it provides a linear order here - O(n+m).

Upvotes: 0

Idos
Idos

Reputation: 15310

I think this sort of solution will be better, if you can use other data structures:

First we will fill up a HashMap<Integer, Integer> with the items and their frequencies:

public static Set<Entry<Integer, Integer>> fillMap(int[] a, int[] b) {
    HashMap<Integer, Integer> entries = new HashMap<>();    
    for (Integer i : a) 
        entries.put(i, entries.get(i) == null ? 1 : entries.get(i) + 1);

    for (Integer i : b) 
        entries.put(i, entries.get(i) == null ? 1 : entries.get(i) + 1);

    return entries.entrySet();
}

And then print the unique items (the ones with value = 1):

for (Entry<Integer, Integer> entry: fillMap(a, b)) 
    if (entry.getValue() == 1) 
        System.out.println("This value is unique: " + entry.getKey() );

If I'm not mistaken this should run in O(n+m) (or just O(n) if the arrays are the same length always).

Upvotes: 3

SmashCode
SmashCode

Reputation: 761

convert array to array list

List<Integer> c = Array.asList(a);
List<Integer> d = Array.asList<b>;
c.removeAll(d);
c.addAll(d);
c.froEach(System.out::println);

I did this in java using lambdas it is only O(n)

Hope this code answers your question

Upvotes: 0

Related Questions