# Finding common strings among 2 arrays of strings of length 1, sorted alphabetically in O(n) time complexity

The problem:

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.

commonTwo({"a", "c", "x"}, {"b", "c", "d", "x"})2

commonTwo({"a", "c", "x"}, {"a", "b", "c", "x", "z"})3

commonTwo({"a", "b", "c"}, {"a", "b", "c"})3

I tried to solve the problem with $O(n)$ time complexity:

    public  int commonTwo(String[] a, String[] b) {
int result=0;
String prev="";
for(int i=0,j=0;(i<a.length)&&(j<b.length);)
{
if(a[i].charAt(0)<b[j].charAt(0))
{
i++;
continue;
}
if(a[i].charAt(0)==b[j].charAt(0))
{
if(!(a[i].equals(prev)))
result++;
prev=a[i];
i++; j++;
continue;
}
j++;

}

return result;

}


It seems to be working but the code looks somewhat ugly. Please feel free to review or if you have any other elegant solution would appreciate you include it in the review.

• Would {"a", "a"}, {"a"} be expected to return 1 or 2? What about {"a", "a"}, {"a", "a"}? – Ben Aaronson Jul 14 '14 at 15:43
• Should return 1 in these cases. – Anirudh Jul 14 '14 at 15:45
• Do you have only letters or this is just an example ? Can you have words in your array ? – csblo Jul 14 '14 at 20:00
• Only letters sire.. – Anirudh Jul 15 '14 at 2:54

Java is not my strong-point, but there are a few things that stand out.

• Spacing is non-standard.
• There are unnecessary parentheses, e.g. in

(i<a.length)&&(j<b.length)


and

if(!(a[i].equals(prev)))

• Optional braces should always be included, e.g. in

if(!(a[i].equals(prev)))
result++;

• Statements should always be on separate lines, e.g. don't do

i++; j++;


There is a more elegant solution using a HashSet<String>, which I believe has the same time complexity.

public int commonTwo(String[] a, String[] b) {
Set<String> common = new HashSet<>(Arrays.asList(a));
common.retainAll(new HashSet<>(Arrays.asList(b)));
return common.size();
}

• I think retainAll has complexity $O(n^2)$ – Anirudh Jul 15 '14 at 9:08
• @Anirudh as both collections are hash sets, contains and remove are $O(1)$, so retainAll should be $O(n)$. – mjolka Jul 15 '14 at 9:31
• Humm yeah I stand corrected. – Anirudh Jul 15 '14 at 9:34
• BTW what about the space complexity here? – Anirudh Jul 15 '14 at 9:37
• @Anirudh $O(n + m)$ auxiliary space, so worse than your $O(1)$ solution. – mjolka Jul 15 '14 at 10:02