Counting duplicate elements in two sorted arrays

Question

I've been working on an assignment that involves optimizing a duplicate finding algorithm for sorted arrays, and I'd like to get your thoughts on the implementation. Here's the code I've come up with:

private static int findDuplicatesFinalVersion(int[] arr1, int[] arr2) {
    int count = 0;
    int index1 = 0;
    int index2 = 0;

    while (index1 < arr1.length && index2 < arr2.length) {
        if (arr1[index1] < arr2[index2]) {
            index1++;
        } else if (arr1[index1] == arr2[index2]) {
            count++;
            index1++;
            index2++;
        } else {
            index2++;
        }
    }
    return count;
}

The assignment:

Keep track of the next element in the first array. If the next element in the second array is smaller than the next in the first, then move forward in the second array. If it is equal (and then we found a duplicate) or greater, then we move forward in the first array. Assume that the two arrays themselves do not contain any duplicates (use the generator in the previous example). Run some benchmarks and compare the execution time with the run time using: unsorted arrays, binary search, and your final version.

This implementation is meant to find duplicates efficiently in two sorted arrays as per the assignment requirements. It keeps track of two indices, one for each array, and advances them intelligently based on the comparison of elements.

Before arriving at this solution, I also experimented with an unsorted array and implemented binary search, which significantly improved performance. However, for this assignment, I'm tasked with working on sorted arrays.

If you have experience with sorting and searching algorithms or if you've encountered similar assignments, I would greatly appreciate it if you could review this code. Do you think this implementation is correct and efficient for finding duplicates in sorted arrays as per the context of my assignment? Additionally, if you have any suggestions for further improvements or insights, please feel free to share.

Thank you!

Answer 1

Looks good and correct, I'd have only two suggestions:

1. Your function is called _find_Duplicates but it actually counts them, so countDuplicates seems more appropriate and tells the caller what to expect. From a "find" function I'd expect to get a list of found duplicates returned.
2. Not as relevant for your assignment but to keep in mind for later: Your implementation assumes certain things (i.e. both arrays are sorted and do not contain duplicates themselves) and only works correctly if those assumptions are met. Therefore, you should make those assumptions as clear as possible in the code, e.g. by accompanying Javadoc.

Answer 2

The first thing I notice about the single function presented is the lack of a doc comment.
Then again it is private, and readable enough I think I get what it does, so not documenting it may not be a major problem here.

I think int duplicateCount(int[] ascending1, int[] ascending2) a slight improvement in naming, a moderate one in not needing explicit documentation.

You can avoid the repeated index2++;:

        } else {
            index2++;
            if (ascending1[index1] == ascending2[index2-1]) {
                count++;
                index1++;
            }
        }

incrementing index2 before the if-statement so if smaller immediately jump to the top of the loop.
(A moot point, almost, as the increment could be place "at the top of the loop" for same number of jumps inside the loop.)
Can be written nicer

        } else if (ascending1[index1] == ascending2[index2++]) {
            count++;
            index1++;
        }

– while readability depends on reader and I'd be tempted to code it thus, I think this blows readability.

You report to have experienced significantly improved performance from binary search.
Something similar can be applied here: Exponential search - relative performance depending on data.
An exercise in avoiding code duplication:

/** @param offset all elements in <code>ascending</code> at smaller indexes <br/>
 *                are assured to be smaller than <code>target</code> by caller
 *  @return the index of the smallest item in <code>ascending</code>
 *  no smaller than <code>target</code>.
 *  @throws <code>NoSuchElementException</code> when all elements
 *          in <code>ascending</code> are smaller than <code>target</code>
 */
static int noSmallerAt(int target, int offset, int[] ascending) {
    // ToDo: implement exponential search, e.g. Fibonacci
    throw new NoSuchElementException();
}

static int duplicateCount(int[] ascending1, int[] ascending2) {
    int count = 0,
        index[] = { 0, 0 },
        ascending[][] = { ascending1, ascending2 };

    try {
        for (int one = 0, other = 1 ; ; one = other, other ^= 1) {
            int value = ascending[other][index[other]];
            index[one] = noSmallerAt(value, index[one], ascending[one]);
            if (value == ascending[one][index[one]]) {
                count++;
                index[0]++;
                index[1]++;
            }
        }
    } catch (NoSuchElementException nse) {
        return count;
    }
    // ToDo: decide what to do when the infinite loop was terminate by something else
}

(- as this is untested as of now, I can only hope I didn't mix up one and the other or otherwise messed it up).