Intersection of Arrays - Java

Question

public ArrayList<Integer> findIt (int[] a, int[] b){
    ArrayList<Integer> result = new ArrayList<Integer>();
    Arrays.sort(a);
    Arrays.sort(b);
    int i = 0;
    int j = 0;
    while(i < a.length && j < b.length){
        if(a[i]<b[j])
            ++i;
        else if (a[i] > b[j])
            ++j;
        else{
            if (!result.contains(a[i]))
                result.add(a[i]);
            ++i;
            ++j;
        }   
    }
    return result;
}

I would like any advice on how to improve the code above. To clarify what this code considers an intersection to be, the intersection of [3,3,4,6,7] and [3,3,3,6,7] is [3,6,7]. Any improvements should make the code more readable or perform faster.

Thank you for your advice.

Answer 1

Algorithm

You're using a O(n log(n)) algorithm here, which could be O(n²) for difficult cases since contains() is O(n) and is called in a loop. Instead, use the property of HashSet: access is O(1), which means you can achieve this in O(n) time. My algorithm below simply keeps track of what it can add to the result. I can add everything that exists in the first list, but I should not add an item I already added.

See my tested code for my implementation:

public static List<Integer> intersection(List<Integer> a, List<Integer> b){
    Set<Integer> canAdd = new HashSet<Integer>(a);
    List<Integer> result = new ArrayList<Integer>();

    for (int n: b) {
        if(first.contains(n)) {
            result.add(n);
            // we wish to add only one n
            canAdd.remove(n);
        }
    }

    return result;
}

Comments on your code

1. You should return a List, not an ArrayList since it's an implementation detail. Using an ArrayList is OK here since adding at the end of it has O(1) amortized complexity. Otherwise, lists should be LinkedList (when adding to the beginning, not to the end, as @Landei points out).
2. Be careful about the names you choose. findIt doesn't seem to be appropriate, but removeDuplicates or intersection describes what the code does.

Answer 2

What about ? It's clean.

public static List<Integer> intersection(List<Integer> a, List<Integer> b){
    List<Integer> result = new ArrayList<Integer>();

    for(int v : a) {
        if(b.contains(v) && !result.contains(v)) {
            result.add(v);
        }
    }

    // sort if you need
    Collections.sort(result); 

    return result;
}

Answer 3

@Cygal : Assuming that HashSet.contains() is really faster than the List one, this could be the ultimate code :-)

public static List<Integer> intersection(List<Integer> a, List<Integer> b) {
    Set<Integer> aSet = new HashSet<Integer>(a);
    Set<Integer> bSet = new HashSet<Integer>(b);

    for(Iterator<Integer> it = aSet.iterator(); it.hasNext();) {
        if(!bSet.contains(it.next())) it.remove();
    }

    return new ArrayList<Integer>(aSet);
}

Answer 4

You can use CollectionUtils utility in Apache Commons Collection. There is intersection method in this class. I will write my utility for your case in following:

public <T> Collection<T> intersection(T[] one, T[] two)
{
    List<T> list_one = Arrays.asList(one);
    List<T> list_two = Arrays.asList(two);

    List<T> intersection = (List<T>) org.apache.commons.collections
                                                       .CollectionUtils.intersection(list_one, list_two);

    return intersection;
}

I hope my answer will useful for you.