6
\$\begingroup\$

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.

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

1 Answer 1

6
\$\begingroup\$

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();
}
\$\endgroup\$
6
  • \$\begingroup\$ I think retainAll has complexity \$ O(n^2) \$ \$\endgroup\$
    – Anirudh
    Jul 15, 2014 at 9:08
  • 1
    \$\begingroup\$ @Anirudh as both collections are hash sets, contains and remove are \$O(1)\$, so retainAll should be \$O(n)\$. \$\endgroup\$
    – mjolka
    Jul 15, 2014 at 9:31
  • \$\begingroup\$ Humm yeah I stand corrected. \$\endgroup\$
    – Anirudh
    Jul 15, 2014 at 9:34
  • \$\begingroup\$ BTW what about the space complexity here? \$\endgroup\$
    – Anirudh
    Jul 15, 2014 at 9:37
  • 1
    \$\begingroup\$ @Anirudh \$O(n + m)\$ auxiliary space, so worse than your \$O(1)\$ solution. \$\endgroup\$
    – mjolka
    Jul 15, 2014 at 10:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.