Finding common elements, ignoring duplicates, in two given string arrays

Question

I am going through the CodingBat exercises for Java. Here is the one I have just completed:

Start with two arrays of strings, a and b, each in alphabetical order, possibly with duplicates. Return the count of the number of strings which appear in both arrays. The best "linear" solution makes a single pass over both arrays, taking advantage of the fact that they are in alphabetical order.

Here is my code:

public int commonTwo(String[] a, String[] b){

    String[] shortArray;
    String[] longArray;

    if (a.length != b.length) {
        shortArray = a.length < b. length ? a : b;
        longArray = a.length > b. length ? a : b;
    } else {
        shortArray = a;
        longArray = b;
    }

    int count = 0;
    String letterToAvoid = "";

    for (int i = 0; i < shortArray.length; i++) {
        for (int j = 0; j < longArray.length; j++) {
            if (shortArray[i] == longArray[j] && longArray[j] != letterToAvoid){
                count++;
                letterToAvoid = longArray[j];
            }
        }
    }
    return count;
}

My questions are:

1. Is there a better - or more efficient - way to find the longest and shortest array lengths (and subsequently assign them separately if the lengths are equal)?
2. Is my letterToAvoid idea, used to 'skip' certain array elements, good for this kind of exercise?
3. How could I make this code more efficient?

Answer 1

There is one major flaw in your code: Testing strings for value equality must be done with .equals() not with ==. For example, for

commonTwo(new String[]{new String("a"),"b","c"},
          new String[]{"a","b","c"})

your code returns 2 instead of 3. (Compare How do I compare strings in Java?.)

Your computation of the larger/shorter array can be simplified to

shortArray = a.length < b.length ? a : b;
longArray = a.length >= b.length ? a : b;

But actually your code does not take advantage of the fact that one array is shorter than the other, so you might as well loop over a and b directly.

Your letterToAvoid idea works (almost) to skip duplicate elements, but I would call the variable differently, perhaps lastDuplicate. And you could early-return from the inner loop if a duplicate is found. Your idea does not work if the string arrays contain empty strings as well which should also be counted.

Your solution is not efficient. It does not take advantage of the fact that both arrays are sorted. Instead of a nested loop you can perform a parallel single iteration over both arrays:

• If current left element is smaller than current right element, advance left position by one.
• If current right element is smaller, advance right position.
• If current left and right elements are equal, we have found a duplicate. Skip following equal elements in both arrays.

Possible implementation:

public int commonTwo(String[] a, String[] b){

    int count = 0;

    int i = 0;  // Index into a
    int j = 0;  // Index into b

    while (i < a.length && j < b.length) {
        int cmp = a[i].compareTo(b[j]);
        if (cmp < 0) {
            // a[i] is smaller
            i++;
        } else if (cmp > 0) {
            // b[j] is smaller
            j++;
        } else {
            // a[i] == b[j] 
            // Increment count and skip duplicates
            count++;
            String lastDuplicate = a[i];
            i++;
            j++;
            while (i < a.length && a[i].equals(lastDuplicate)) { i++; }
            while (j < b.length && b[j].equals(lastDuplicate)) { j++; }
        }
    }

    return count;
}