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

@hannanabdullah8842

2 жыл бұрын

lol, same

@anshumansharma1069

Жыл бұрын

That's me🥺

@adityasarve275

Жыл бұрын

My man 😂 me too

@JimZarasOfficial

Жыл бұрын

I’m also spending hours in understating his solution.

@nguyenkhoanam8930

Жыл бұрын

Thanks guy. I'm just thought I'm the most stupid guy in the world after many hours!

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]

@Rajmanov

Жыл бұрын

up!

@martinlacsamana7534

6 ай бұрын

exactly what I did

@vishaalkumaranandan2894

2 ай бұрын

But this is O(n2) time complexity right

Got asked this in apple today

@shivanidhyani8370

2 ай бұрын

Hey shivangi, I want to know more questions that are asked in Apple

@musasu

Ай бұрын

were you able to solve it?

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!

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 😂

@aperson4475

2 жыл бұрын

I started by assigning the first element of the array strs to the prefix and then deleting the characters that didn't match. turns out loop through a changing element is not a good idea, also in rust the delete character thing is a O(n) operation lol.

@davide816

Жыл бұрын

i thinked like you and i resolved it but it took 40 lines. Man those men are amazing in simplifying the problem.

@nikhil_a01

Жыл бұрын

You can totally do it that way! That's how I did it: class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: shortest = min(strs, key=len) for i, char in enumerate(shortest): if any(s[i] != char for s in strs): return shortest[:i] return shortest 1. First we find the shortest string 2. Then for every string s we make sure that shortest[i] == s[i]. I use any() but a for-loop also works 3. If we don't match all characters we return shortest[:i] which is just whatever we matched so far. For example if characters 0 and 1 matched but it failed for i=2, then we return shortest[:2]. 4. If we match all characters in shortest then obviously the longest common prefix is just shortest, so return that. It takes one extra pass over the array to get the shortest string, but it doesn't change the time complexity. And it removes the edge case of checking if i goes past the length of any string.

@selim7372

4 ай бұрын

​@@davide816 min_length = min(len(s) for s in strs) common = "" for i in range(min_length): for j in range(len(strs) - 1): if strs[j][i] != strs[-1][i]: return common common += strs[-1][i] return common I did it this way. Not selecting the shortest string but selecting the length of it.

@ielinDaisy

24 күн бұрын

Approached it the same way. Broke my head a few times but I somehow arrived at a solution 😭 class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: result = "" count = 0 strMin = min(strs, key=len) for i in range(len(strMin)): for j in range(len(strs)): if strMin[i] != strs[j][i]: return result else: count += 1 if count == len(strs): result += strMin[i] count = 0 return result

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) for s in strs: iP, iS = 0, 0 # index of prefix, index of current string while iP if prefix[iP] == s[iS]: # match? simply increment both indices iP+=1 iS+=1 else: # first mismatch if len(prefix[0:iP]) prefix = prefix[0:iP] # set prefix to the shorter of two iP = len(prefix) # exit while loop return prefix

@tsunami8892

10 ай бұрын

same bro

@jassemtoumi8748

9 ай бұрын

nice optimization.... yet the time complexity is not O(n) it is O(n*m) where n is the number of strings in the array and the m is the average length of the shortest string (found in the first loop O(n)))

Incredible! Thank you!

The best explanations. !!!

Such a clean and concise solution..Thanks a ton

@marianpascu8474

Жыл бұрын

Yeah, but slow.. it requires double for loop

@darellarocho5729

Жыл бұрын

@@marianpascu8474 How would you do it with a single loop?

Thank you so much!

Awesome explanation

Thanks for the video))

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

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.

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( [ ... ] )

@ekcelhenrichekoumelong4457

4 ай бұрын

A string is also a type of array. There's no value added by the solution you propose here.

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

How about a prefix tree solution?

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

@asjadmulani9640

11 ай бұрын

I usually avoid doing DSA questions using a OOPs language

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

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

@googoo725

Жыл бұрын

Thanks buddy! This was the method I had in my head but I couldn’t quite figure out how to execute it.

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

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

@Vaishravana07

2 жыл бұрын

have you watched abdul bari's videos on KMP??

@dhivyashri6554

2 жыл бұрын

@@Vaishravana07 yes my dumbass didnt understand despite that lol

@Vaishravana07

2 жыл бұрын

@@dhivyashri6554 yes , I recently watched the video and understood it , but I don't think I will be able to code It yet are you preparing for your coding interview

@nikobekris8542

2 жыл бұрын

I had the same problem and had to watch multiple different videos and read multiple articles to get it to actually make sense. I think this video was the most informative though. kzread.info/dash/bejne/eYh-1JqIptyrhrQ.html&ab_channel=TusharRoy-CodingMadeSimple

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."

@lapwamen1913

7 ай бұрын

Are you certain about the matching in step 2-4? I think if you iterate through string 1 by 1, it takes O(n). Then the index matching between 'ans' takes another O(m), therefore the overall time complexity is still O(n * m)

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

damn, you made it look so simple

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

@antrikshsingh7798

Жыл бұрын

Shouldn't that be n[i] within the if condition n = min(strs,key=len) ## shortest string res = "" for i in range(len(n)): for char in strs: if char[i] != n[i]: ## check if condition with the shortest string return res res += n[i] return res

@stevenlam1606

7 ай бұрын

The loop will break once it reaches the shortest string "i == len(s)"

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

@clomz213

2 жыл бұрын

What I was thinking also... Maybe problem just assumes first str is longest?

@yingyuan589

2 жыл бұрын

I think it doesn't matter. This could be arbitrary string in the array. i == len(s) and the immediate return check the min length of strings.

@roshanzameer5020

2 жыл бұрын

My first solution had this: word = min(strs, key=len)

@hassannajam4634

2 жыл бұрын

If there is a longer string, the prefix won't be longer than strs[0] since the prefix can at most be as long as the shortest string. The code account for shorter strings already.

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

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

@eltonsilvamtm

Жыл бұрын

love this solution! thanks for sharing

@thenerdycoder07

Жыл бұрын

can you please explain this solution

@VarunMittal-viralmutant

Жыл бұрын

@@thenerdycoder07 zip(*strs) will collect all the corresponding characters from each of the given string. Number of elements in the list is the length of shortest string Eg: chars = zip('flower', 'flow', 'flight') chars = [(f, f, f), (l, l, l), (o, o, i), (w, w, g)] Then we are just iterating this chars list and checking if all elements are same: len(set(char)) == 1 If it is, we add char to res else break as soon as we find the first mismatch

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

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

BEAUTIFUL

Thanks!

@NeetCode

Жыл бұрын

Thank you 🙏

could you reiterate concept of inbound and outbound?

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: kzread.info/dash/bejne/l4Ccl8WTobHTZ8Y.html

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

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 if f_str[i] == l_str[i]: res += f_str[i] i+=1 else: return res return res

@nikhil_a01

Жыл бұрын

No, it has worse time complexity because you're sorting which is O(N log N). Conceptually your idea works fine though. But instead of sorting, you can use min and max in O(N) time. shortest = min(strs) longest = max(strs) That'll make it roughly an optimal solution.

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)

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

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

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

@user-we5lp1yr3r

Жыл бұрын

No, It's O(n⋅m), where n - number of strings, and m - average length of the strings

@jpkeys6000

Жыл бұрын

@@user-we5lp1yr3r It makes sense now. Thank you!

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

@Jr-xs9hy

2 жыл бұрын

idk about that... that solution looks way more complicated

@Rajmanov

Жыл бұрын

this is cheating AF

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

@ombothre2350

13 күн бұрын

class Solution: def longestCommonPrefix(self, strs: List[str]) -> str: strs.sort() i = 0 ans = "" while i ans += strs[0][i] i += 1 return ans

plz add typescript support in neetcode

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

@shalinisangal84

Ай бұрын

Because if it is equal then we will keep checking next indexes

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

@drewskii9708

Жыл бұрын

I believe it's because the first for loop is iterating over all of the letters in the first word which can be size 'm'. The second nested for loop is iterating through all of the words in the input array which can be size 'n'. Thus it's O(m * n). Or at least that's my understanding.

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

@jacobw9647

11 ай бұрын

you take the iterator as your multiplier. In this case the worst case is n for the length of strs and m in relation to the word chosen to iterator/match to. Therefore, O is O(n*m)

does there exist a linear solution?

@pedrov8868

Жыл бұрын

Not possible (under the definition). Worst case you have the nearly the same words so it'd be O(n*m).

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

@BossKing1243

Жыл бұрын

No, it would actually be slower. You’d have to pass through the array again to sort the elements, which would add to the runtime

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.

@Century-uq8rg

2 жыл бұрын

time complexity is o of n squared as there two nested for loops

@taylorman1111

2 жыл бұрын

@@Century-uq8rg Not exactly since they're iterating over two different things, it's o(n*m) where n is the number of strings and m is the shortest string.

@shashanksharma7242

2 жыл бұрын

@@taylorman1111 I agree with you.

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

@buhnanner2935

2 ай бұрын

Hi, I know this is a very late reply and you may have figured this out already Since we are referencing the 0'th element of strs array to initialize our loop, this element could be of any length. it could be shorter, or longer, than proceeding strings in the array. checking if i == len(s) with each iteration is a way of preventing an out-of-range error when looking at different strings in the array. Here is the thought process: We are iterating on a loop for the length of the array (strs) Say that the len(strs[0]) is equal to 5. Say we are on the 3rd iteration (i == 3) of our outer loop. in our inner loop (for s in strs:) it checks with every iteration if 'i' is equal to the length of the current string. If it IS equal, we need not to iterate again on this string, as it would cause an out-of-range error. since this would denote that we are at the ending character of 's' Hopefully this makes sense

Love your content

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

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

@jingwang2111

Жыл бұрын

this is an O(n) solution even though there are indented for loops.

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.

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]

You sound like jeany collects

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) :)

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

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

@darellarocho5729

Жыл бұрын

I think you're not quite seeing what strs[0][i] is actually doing. Maybe I can explain. So we have the following array/list: ["flower", "flow", "flight"] strs[0] is equal to the first string in the array/list. In other words, strs[0] = "flower" Then when you add the [i] afterwards it looks at the individual characters of that string which we are at. Since strs[0] = "flower", the [i] will loop through the word "flower" itself. So it's going to go: 'f' > 'l' > 'o' > 'w', etc. So basically, strs[0][i] is looking at the individual characters of the first word in the array/list, which in our example happens to be the word "flower", so it's going to go through each letter of the word "flower". Hope this helps!

@priyak3133

5 ай бұрын

I have the same doubt, it is like comparing first and second string, but how we are taking common between 2nd and third string here

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

@primogem_160

2 жыл бұрын

string longestCommonPrefix(vector &strs) { string pre = ""; for (int i = 0; i { for (string &str : strs) if (i == str.length() || str[i] != strs[0][i]) return pre; pre += strs[0][i]; } return pre; }

I did not understand the code

is this Easy problem?

@VinceMichaelDizon

6 күн бұрын

For some have background but for beginners 😂😂😂😂😂

I was hoping for a TRIE solution explanation..

I still dont understand this man :(

@Anon-xz6hu

2 жыл бұрын

U understand now?

@farjanashaik9601

2 жыл бұрын

same here..i too didn't understand...

@roshanzameer5020

2 жыл бұрын

@@farjanashaik9601 @Anon Try to visualise what happens on every iteration. Use Print statements or Pycharm Debugger.

my interview question🥲

@doc9448

2 ай бұрын

Interview where?