Longest Common Prefix in an array of Strings Please be brutal, and treat this as if I was at an interview at a top 5 tech firm.


  Question: Write a function to find the longest common prefix string
  amongst an array of strings.


Time it took: 17 minutes

Worst case complexity analysis: n possible array elements, each can have length m that we are traversing, hence O(n*m); m could be a constant, since it's rare to find a string with length, so in a sense, I imagine this could be treated as O(n *constant length(m)) = O(n)?

Space complexity analysis: O(n)

public String longestCommonPrefix(String[] strs) {
    String longestPrefix = "";
    if(strs.length&gt;0){
        longestPrefix = strs[0];
    }
    for(int i=1; i&lt;strs.length; i++){
        String analyzing = strs[i];
        int j=0;
        for(; j&lt;Math.min(longestPrefix.length(), strs[i].length()); j++){
            if(longestPrefix.charAt(j) != analyzing.charAt(j)){
                break;
            }
        }
        longestPrefix = strs[i].substring(0, j);
    }
    return longestPrefix;
}
Pure functions should generally be declared static.

You shouldn't need to take substrings in a loop — that's inefficient.  Think of scanning a two-dimensional ragged array of characters.  Check that all of the first characters match, then that all of the second characters match, and so on until you find a mismatch, or one of the strings is too short.

public static String longestCommonPrefix(String[] strings) {
    if (strings.length == 0) {
        return "";   // Or maybe return null?
    }

    for (int prefixLen = 0; prefixLen &lt; strings[0].length(); prefixLen++) {
        char c = strings[0].charAt(prefixLen);
        for (int i = 1; i &lt; strings.length; i++) {
            if ( prefixLen &gt;= strings[i].length() ||
                 strings[i].charAt(prefixLen) != c ) {
                // Mismatch found
                return strings[i].substring(0, prefixLen);
            }
        }
    }
    return strings[0];
}


Space complexity: O(1).

Worst-case time complexity: O(n m) to scan every character in every string.