I spent almost 6 hours trying to code this myself and still couldnt figure it out...lol

Got asked this in apple today

it hurt me when you said "the edge cases will trip you up if you are a beginner" 😢 They made me go crazy and I have been practicing a lot!

Here are some optimization recommendations: Adding to a string in Python, will always create a new string, which is not optimal. We dont even have to store any information. We can just return the slice up to index i (exclusive), as soon as any two characters are not equal or any index is out of bounds. def longestCommonPrefix(self, strs: List[str]) -> str: for i in range(len(strs[0])): for j in range(1, len(strs)): if i == len(strs[j]) or strs[0][i] != strs[j][i]: return strs[j][:i] return strs[0]

I started out by trying to find the shortest string in the list and assigning that as prefix and then it was a disaster one after the other 😂

This is an amazing solution - looping over the same character index of every string at once. Another solution I came up with that was intuitive to me: 1. Find the shortest string (since the prefix can't be longer than the shortest string) - O(n) 2. Set the prefix to this shortest string (in theory the entire shortest string can be the prefix) 3. compare shortest string with every other string character by character - O(n) 4. at the first character mismatch, if we haven't looped over the entire short string (prefix), update prefix to this shortened version There are two passes, but the time complexity is still O(n) # set prefix to first str by default prefix = strs[0] # prefix can't be longer than the shortest str, so we need to find it for s in strs: # O(n) prefix = prefix if len(prefix) < len(s) else s for s in strs: iP, iS = 0, 0 # index of prefix, index of current string while iP < len(prefix) and iS < len(s): # make sure neither index is out of bounds if prefix[iP] == s[iS]: # match? simply increment both indices iP+=1 iS+=1 else: # first mismatch if len(prefix[0:iP]) < len(prefix): prefix = prefix[0:iP] # set prefix to the shorter of two iP = len(prefix) # exit while loop return prefix

Such a clean and concise solution..Thanks a ton

The best explanations. !!!

How about a prefix tree solution?

had concept in mind. just needed a small simple how. saw your loop Nd i did it. thanks

Incredible! Thank you!

thanks for the code i was trying to do this but wasn't able to

i did if the length of the set of the indexed letters is equal to 1, then append that to out and keep going until there are multiple letters in the set - this beat 80 or so percent

Isn't adding string to already contructed string bad practice? What if we keep letters in list/array , than we can join them together? Instead of s = s + new_letter, we could do [ ... ] .append(new_letter) and finally return "".join( [ ... ] )

Thank you so much!

Awesome explanation

isn't it a O(n^2) solution?

Hello neetcode could please make a video on task scheduler problem(greedy).It is in blind 75 list. It would be me a lot if you do that because i have seen many discussions and videos regarding this and couldn't understand any approach

hey can u do the kmp algorithm sometime, it uses the lps concept, i have tried watching sooo many tutorials for it but i've never understood, it would be great if u'd consider, thanksss

damn, you made it look so simple

Hopefully this is a pretty straight forward solution (6 lines of code and nothing fancy): prefix = min(strs, key=len) strs.remove() for s in strs: while prefix and s.find(prefix) != 0: prefix = prefix[:-1] return prefix

could you reiterate concept of inbound and outbound?

Thanks for the video))

c++ version: class Solution { public: string longestCommonPrefix(vector& strs) { string rsl = ""; for (int i = 0; i < strs[0].size(); i++) { for (auto& s : strs) { if (i == s.size() || s[i] != strs[0][i]) { return rsl; } } rsl += strs[0][i]; } return rsl; } };

I came up with a solution, but with more optimization. Let me explain: Time complexity O(2n) Space Complexity O(1) 1. First, we find the shortest string in the array and store it in a variable called 'ans.' We then remove this shortest string from the array. 2. Next, we iterate through all the remaining strings one by one. For each string, we check if the last character of 'ans' matches the character at the same index in the current string. 3. If there is a match, we move on to the next iteration. 4. If there is no match, we remove the character from our 'ans' variable and enter a loop. In this loop, we continue checking the second-to-last character of 'ans' and so on, until 'ans' becomes empty."

We can just sort the list of string first then can use the for loop it will be more easy

How about this: def longestCommonPrefix(self, strs: List[str]) -> str: chars = zip(*strs) res = "" for c in chars: if len(set(c)) == 1: res += c[0] else: break return res

I thought this was asking longest common substring this whole time.... i need to sleep

now i understand my mistake. i was comparing with the "i" in range, so 0,1,2,3 with the length, so len() which gives out 4. with the understanding they should be the same, forgot that len() gives the amount, not like an index.. damn im a noob

How did it not hit me in my head that I needed to use 2D way of locating a character within a string withing an array of strings. It's so simple that if you don't know, makes the problem look a lot more complicated. Me brain dumb.

why is it strs[0] ? what if there is another string that is bigger ? or shorter ?

plz add typescript support in neetcode

does there exist a linear solution?

res='' for i in range(0,len(strs[0])): for s in range(len(strs)): if i==len(strs[s]) or strs[s][i]!= strs[0][i]: return res res= res+strs[s][i] return res This code looks more readable and understandable

If anyone confused by why he puts range(len(strs[0])) instead of the length of the shortest string, you can change your code to this one below so it fits the logic we'll iterate through the shortest string #Find shortest string length n = min(strs,key=len) res = "" for i in range(len(n)): for char in strs: if char[i] != strs[0][i]: return res res += strs[0][i] return res

my soln: def longestCommonPrefix(self, strs: List[str]) -> str: longest = "" for letter in strs[0]: if all([word.startswith(longest + letter) for word in strs]): longest += letter return longest

Why isn't the time complexity O(n^2)? There's a nested for loop

BEAUTIFUL

we are using for loop inside another for loop. isnt the time complexity n2? Exponential

Aren't these two for loops nested, hence o(n^2)?

why did you wrote != strs[0][i] ?

Why don't use sorted like others: class Solution: def longestCommonPrefix(self, v: List[str]) -> str: ans="" v=sorted(v) first=v[0] last=v[-1] for i in range(min(len(first),len(last))): if(first[i]!=last[i]): return ans ans+=first[i] return ans

would it be more efficient to sort the list and compare the first and the last element in the sorted list, instead of comparing every single element to the s[0]? sorting would be O(n logn) and comparing the first and the last element would be O(n), i believe. idk if I'm missing somethign. class Solution(object): def longestCommonPrefix(self, strs): sorted_strs = sorted(strs) res = '' i = 0 f_str = sorted_strs[0] l_str = sorted_strs[-1] while i < len(f_str) and i < len(l_str): if f_str[i] == l_str[i]: res += f_str[i] i+=1 else: return res return res

im not sure how you added I == Len(s) *what purpose it serves

Hi what's the time & space complexities for the solution? I believe space complexity is O(n) where n is prefix stored in string variable 'res'. However I am unsure about time. Would it be O(n+m) where 'n' is the character size of strs[0] & 'm' is number of words in strs? Thanks.

a bit late but i just wanna post my solution using typescript/javascript function longestCommonPrefix(strs: string[]): string { // take the first string as comparison let out=strs[0] // traverse the list for(let i=1;i

Thanks!

x = ["flower", "flosing", "flowing"] prefix = "" for i in range(len(x[0])): flag = 0 temp = x[0][i] for j in range(1, len(x)): if not x[j][i] == temp: flag = 0 break else: flag = 1 if flag ==1: prefix+=temp else: pass print(prefix)

class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: ''' Use the first string as the basis. Compare each string, increment i when characters match, and update the basis. ''' # Use the first string as the basis basis = strs[0] # Iterate over each string for s in strs: i = 0 # Increment i as long as characters match while i < len(basis) and i < len(s) and s[i] == basis[i]: i += 1 basis = s[:i] # Update the basis (it will get shorter) return basis

What if we sort the list, this way it will automatically have common prefixes arranged and we can just check the first and last one

The time complexity of the solution in this video is: O(m * n + m^2) where n = len(strs) & m = len(strs[0]) The key thing to understand here is that the following line of code: res += strs[0][i] is an O(m) operation. (Where m = len(strs[0]) ) because `res` in the worst case scenario gets built up to the length of strs[0] and we cannot simply append a character to the end of a string like we can with a list. We have to create an entire copy of the string. I have an unlisted youtube video that shows a coaching call I had with a student that goes over why the time complexity of this solution is O(m*n + m^2), and I also mention at the end of the video how you can optimize the algorithm to be O(m*n). Or we can say O(n) if we say n = all characters of all strings within `strs`. Here's the unlisted video: kzfaq.info/get/bejne/m7KYaMaL1rTRZ5c.html

Did it work? Yes. Did it make sense? No.

You sound like jeany collects

how can you say its O(n) when you have nested loops lol. Its O(n*m)

I believe it would be faster by sorting an array and grabbing first and last words only for prefix comparison

I copied the exact same code and still it's not working😭. I have spent my whole night into this. If someone succeed pls comment down the code.

This should be your style~~ prefix = strs[0] for i in range(1, len(strs)): while not strs[i].startswith(prefix): prefix = prefix[0:-1] return prefix

Love your content

I did not understand the code

can anyone provide a c++ solution for this? thanks

Nice video. But i believe it would be better to teach an O(n) solution instead of O(n^2).

U a God- My implementation with a Trie in Python: class TrieNode: def __init__(self): self.child = {} self.count = 1 class Solution(object): def __init__(self): self.root = TrieNode() def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ for word in strs: self.insert(word) # create the Trie total_strs = len(strs) # {'fl': 3} ans = [] word = strs[0] # use to find the common prefix in the Trie curr = self.root for ch in word: if ch in curr.child and curr.child[ch].count == total_strs: ans.append(ch) curr = curr.child[ch] else: break # no common prefix among the input strings return "".join(ans) def insert(self, word): curr = self.root for ch in word: if ch not in curr.child: curr.child[ch] = TrieNode() else: curr.child[ch].count += 1 curr = curr.child[ch]

isnt this brute force approach with time complextiy of O(n2) ? How is this optimal ?

If you sort the strings first using quicksort (or TimSort with TypeScript's Array.sort function) you get an O(nlogn) Time Complexity and then just have to compare the first and last strings (time complexity=O(m), m = length of shortest string in the list), so you get a total time complexity of O(nlogn + m) => O(nlogn) :)

is this Easy problem?

I don't understand how res+ = strs[0][i] would only contain what is common to all the strings. For example, when i = 2, won't res = res+strs[0][2] which is "fl"+"o". *consider the {"flower","flow","flight"} example. Some help pls

🎉

I was hoping for a TRIE solution explanation..

I still dont understand this man :(

my interview question🥲

Thank you so much!