Odtnhj

Below is my code:

/**
 * @param string strs
 * @return string
 */
var longestCommonPrefix = function(strs) 
 if(strs.length ===0) return '';
 let prefix = strs[0];
 for(let i=0; i< strs.length; i++) 
 while(strs[i].indexOf(prefix) !=0) 
 prefix = prefix.substring(0, prefix.length -1);
 if(!prefix) return '';
 
 

 return prefix;
;

Here for loop runs O(n) times and while loop within checks whether prefix matches the elements in for loop iteration - is the while loop O(n) times too? Please provide insight

Let n be the number of strings in strs, and let the average (or longest) string length be m. Your algorithm with line numbers is as follows.

1. var longestCommonPrefix = function(strs) 
2. if(strs.length ===0) return '';
3. let prefix = strs[0];
4. for(let i=0; i< strs.length; i++) 
5. while(strs[i].indexOf(prefix) !=0) 
6. prefix = prefix.substring(0, prefix.length - 1);
7. if(!prefix) return '';
8. 
9. 
10. return prefix;
11. ;

We only need estimate the number of times the for loop (line 4) and the while loop (line 5) are executed. As you noted that the for loop is executed n times, since n = strs.length. However, you do have a return statement within the while loop, so execution might never reach line 10.

Now, for the while loop. As described, this loop is executed the size of the prefix (m) and in each iteration the indexOf operation takes O(m^2) in the worst case (see next paragraph). Thus, the time complexity of your algorithm as a function of the number of strings (n) is O(nm^2).

We could also look at the time complexity as a function of m, the number of characters in each string. How long does it take to compare two strings? Java's implementation in this case will take O(mk), where m and k are the lengths of the two strings respectively (see this answer to this question) and the String class code for details.