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

Question

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.

• Ben Aaronson: Would {"a", "a"}, {"a"} be expected to return 1 or 2? What about {"a", "a"}, {"a", "a"}?
• Anirudh: Should return 1 in these cases.
• csblo: Do you have only letters or this is just an example ? Can you have words in your array ?
• Anirudh: Only letters sire..

Answer 1

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();
}

• Anirudh: I think retainAll has complexity \$ O(n^2) \$
• mjolka: @Anirudh as both collections are hash sets, contains and remove are \$O(1)\,ドル so retainAll should be \$O(n)\$.
• Anirudh: Humm yeah I stand corrected.
• Anirudh: BTW what about the space complexity here?
• mjolka: @Anirudh \$O(n + m)\$ auxiliary space, so worse than your \$O(1)\$ solution.