# 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"}? Jul 14, 2014 at 15:43
• Should return 1 in these cases. Jul 14, 2014 at 15:45
• Do you have only letters or this is just an example ? Can you have words in your array ? Jul 14, 2014 at 20:00
• Only letters sire.. Jul 15, 2014 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)$ Jul 15, 2014 at 9:08
• @Anirudh as both collections are hash sets, contains and remove are $O(1)$, so retainAll should be $O(n)$. Jul 15, 2014 at 9:31
• Humm yeah I stand corrected. Jul 15, 2014 at 9:34
• BTW what about the space complexity here? Jul 15, 2014 at 9:37
• @Anirudh $O(n + m)$ auxiliary space, so worse than your $O(1)$ solution. Jul 15, 2014 at 10:02