LeetCode 14. Longest Common Prefix Solution Explained - Java

[@atefe3919]

No one explains solutions better than you, thank you so much for these videos, they are helping me a lot in the process of getting ready for technical interviews!

[@NickWhite]

thanks

[@joanmoralesf]

Its insane how short this video is but you explained it better than all the long fancy videos. Thank you

[@jay-wf3ft]

I think it would be great if you would show 2 solutions. One with a slow run time and then the optimal solution such as this. It really helps to understand it even more. Either way awesome video

[@pritampadhan5977]

Above logic takes more time i think

[@KhayamGondal]

you can add a check for prefix length ==0 at the end of the while loop. Incase nothing matches with the 2nd string then no need to check with rest of the list. And instead of substringing every itteration you can keep track of right index and only substring when returning the result.

[@raghavendrathakur2239]

[@vcfirefox]

Dude, I am probably much older than you, but goddamn I am LOVING your explanations. Getting a chance to prep my interviews very efficiently!

[@bhargavvaddepally3221]

Damn man that explanation was so smooth

[@ananyadutta6358]

bro your explaining method is quite creative , out of 7 videos based on this that I'd WATCHED , this was the best!

[@prajwalshenoy9117]

Nice one. We can have a case inside for loop to break it when prefix length reaches zero to avoid continuing to loop when there's no scope of common prefix further.

[@poojaupadhyay6364]

such a clear approach! everytime i do leetcode and feel like wtf about a question ,i come here to watch your tutorial and i understand the solution so clearly! thanks a lot,u have a great help dude!

[@suyogsubedi8584]

are you a better problem solver by now?

[@aadhi_dinesh7668]

IN PYTHON s=["flow","flew","flower"] k=s[0] flag=0 a="" for x in range(len(k)): for j in s[1:]: if k[x]!=j[x]: flag=1 else: a=""+k[x] if flag==1: break else: print(a,end="")

[@satyamgupta6030]

what a solution man thanks alot nick brother please continue making these videos. u r just different when it comes to explaining in most optimised ways.

[@sreenidhisreesha]

Since indexOf is linear time complexity, Doesnt it make this O(n2) time complexity?

[@6066ChetanKhairnar]

got through 3 different videos for a good solution but nick is one who always gives the best approach , Appreciate bro

[@himanshumalik6913]

You know what, you just explained in a so easier way that no one has explained yet.

[@carefree_ladka]

indexOf() takes O(N) time . How is your method linear?

[@Noname-di3yz]

the only thing I don't understand is why we can set the first element as the prefix initially... isn't it possible that there is a different longest prefix? ex/ ["ab", "cd", "cde", "cdef","cdefg"], where if we set the prefix to "ab" wouldn't your solution return "" ?

[@syc4654]

probably very late but although the problem doesn't mention it specifically,longest common means that the common prefix must be common for all the elements in the array,so yes,"" would be returned and it would be correct,you can test it yourself inputting your string own string in the Testcase section(In the console) and seeing the expected resulted (from a working code) and your result (from your code)

[@tanyagoel9140]

It was so nicely explained. Thanks a lot!

[@vicente3j]

When I search up a leetcode question I always go to Nick White if its available 😂 Great video

[@simrankak7045]

Why i didnt find your channel until now. Your explaination is crisp clear and very simple thankyou :)

[@utkarshsrivastava3114]

What a clean and simple approach

[@Ben-pb7ct]

Could you explain why the time complexity is O(S), where S is the sum of all characters in all strings?

[@hbrymiri8301]

Hands best step by step explanation.

[@saradham2844]

Best solution for this problem . Great approach and clear explanation Thanks !!!

[@abdelghafourboufenzi213]

but this is incorrect in the case of : "abower","flower","flightwer" the result should be "wer" but the result is empty.

[@syedrehan3251]

Bro prefix means starting of the letter

[@brucewayne9444]

Wow man. I could have never thought of approaching this problem this way. Thanks a ton👍

[@nurulloabdurakhmanov4914]

Exactly man. What should we do to get into thinking like these aproaches ?

[@ashish4k07]

I thought of using 1st string in array of string as base and scanned through all others and checked if one by one it matches all other strings if it is then we increment the string and hence getting final lcp ans

[@maxstanley1818]

yo but what if the first element in the "fl" prefix array is something like "dog" or something?

[@prathamchitransh5338]

best explaination for this problem on youtube

[@greatred2558]

thanks, tried many things for c# but kept falling out of bounds. This works and simple to understand

[@mohammadosama4709]

Why do we need substring method we can check character by character vertically? Wouldn't that me more optimal?

[@ryan-bo2xi]

what is the time complexity ?

[@rupaldesai7098]

the time complexity is? O(n^2)

[@NickWhite]

Nope because we're not looping through the strs array in the inner loop we're popping characters off of one string

[@suryaakella4508]

@@NickWhite What if all the elements in the string are same like all flowers than no deletion and the time complexity would be O(n^2)? I think we would have to use trie or suffix array to get O(n)?

[@i_deepeshmeena]

@@suryaakella4508 it will be still O(NM) where M is the length of the longest string in the array

[@jardondiego]

@@i_deepeshmeena Indeed, time complexity is O(MN) and space complexity is O(M).

[@jardondiego]

Time complexity with a Trie (prefix tree) would be O(M log N) where M is the length of the longest string and N the number of strings, right?

[@gayan1742]

Time complexity of indexOf is O(n) though.

[@divyanshuchaudhari5416]

Great explanation Nick!! Kudos to you.

[@kshitijpandey9376]

You wrapped that up very smoothly. Thanks Nick🙂.

[@abhishekmamgain224]

Still you are using While loop and one for-loop. Wouldn't this make the time complexity similar as two for-loops

[@mohammadrafi895]

No, it wouldn't because the inner loop will not depend on the length of input array. Input array could have 100 words but each word can't be longer than 20 characters, on average 5-10.

[@Thrallgg]

str.indexOf and str.subStr is O(m*n) i think, so I don't think it's optimal.

[@tuckerleavitt]

Yes you're correct, a.indexOf(b) is O(len(a) *len(b)) in the worst case. There is a better solution

[@pranaychoubey9706]

you can eventually shift to stringbuilder i guess.

[@pragatikumarprusty7061]

If possible, please tell the time and space complexity as well ...

[@davidc3268]

how is a linear solution? theres is a nested while loop inside?

[@abhinavs2484]

in worst case it is O^n2 right, is there any better solution!

[@ashish4k07]

So can what can be the overall time complexity for this

[@headyshotta5777]

Thanks for the explanation. I still don't really understand how your while loop works but I'll keep working to understand.

[@sameer9368]

hello....please do the problem on the merging k- sorted array using heap.

[@NickWhite]

send me a link in discord and i'll check it out

[@sameer9368]

i am solving in eclipse . i have the problem statement. can i share you that problem statement. i dont know the approach how to solve such problem, i am the beginner. also i am unaware of the concept like heap. please do the video on it

[@thomasgeorge4578]

Man! your explanation is just fire 🔥🔥🔥

[@tej3679]

best explanation, you explained clearly kudos

[@avinashpatil9662]

What is the time complexity of this solution?

[@gauravmishra8782]

how did you came up with this solution?

[@Whaleshamu]

can you make video on Gray code (Leetcode 89)?

[@NickWhite]

I’ll check it out!

[@shastriswaroop]

How about setting the prefix as the smallest length string and then starting loop from index 0. For longer string array it will be beneficial?

[@dgr8raka470]

I think in place of “indexOf” .. we need to use “startswith” method… tq for the vdo

[@velmuruganjeyakumar1746]

Yooo Man , I too had that same feeling

[@ehsanhosseini5861]

Thank you for this amazing explanation. What is the time complexity?

[@royt6924]

I believe it is O(A*S) where A is the iteration for each element of array, where S for the iteration of string

[@invictuswildlife]

Kudos to such a clean explanation ! Thank you.

[@balavardhanreddy8581]

by watching this video i subscribed ur channel

[@flyfly11111]

You explained it very nicely. Thank you so much

[@makgaboemmanuelmathekga2805]

the code breaks though, with index out of bound error when there is no common prefix

[@TheRishit99]

Great explanation. Can solve this with Trie Tree ?

[@carefree_ladka]

That's the efficient way to solve this problem

[@pjguitar15]

I literally got stuck to this problem and I just gave up and went to KZbin lol

[@iTzAlwxyss]

How does this not work for processing 4 that uses java ?

[@amitpadaliya6916]

really amazing solution

[@swethanooka896]

Can anyone explain me the while loop part of the code?

[@AlejandroRodriguez-lq9mz]

thanks for sharing such solution, very clear and easy one!

[@solomonmokua4643]

Than you, well explained, was able to implement your solution in Python.

[@sarash9607]

Can anyone tell me why do we set the first string as a prefix ? how do we know it is the longest string and the one that has all the letters that we want ? what if the array was like strs = [ "flight", "flower", "flow"]

[@raghavendrathakur2239]

when program runs it finds common between flight and flower first the common is fl and 2nd iteration it will find common between fl and flow so our aim is to find common in strings so what is there in 1st will be in all the strings if not it returns empty string

[@rajeevsingh5453]

What's the time complexity of this algorithm?

[@aryamankukal1056]

linear

[@srijitdebsarma3451]

Best explanation 😍🥰

[@thatsenoughdixit]

Very nice. Commenting so I get more videos.

[@LeetCodeSimplified]

Great explanation! Thx a lot!!

[@ricardosmith5753]

very clean solution.

[@jiangtianfeng5971]

very clear! Thx man

[@swagatzeher]

Thanks man Nick... you are a pocket sized dynamite ;)

[@shivamd23]

Best Solution 😊👍

[@zerosandones7547]

confusion.Cleared(); THANK YOU!

[@rohitkushwaha6125]

Thank you so much for the explanation ut was really nice.

[@kso3586]

Amazing! thank you so much👍

[@theolim6994]

Thank you so much for great explanation!!! Helped so much!

[@freinheit6923]

thank you for explaining!

[@KIM-ODee]

Thanks for your explain!

[@adil_k]

Thanks for this awesome video

[@abdulqudusyunus9786]

Nice explanation

[@junkmail1111]

What if the first element is not the longest string?

[@junkmail1111]

Does it not matter because the longest prefix will only be as long as the shortest word? So the length of the starting string doesn’t matter?

[@NeeruSinghK]

great.. nice and easy solution

[@Post2prqbu]

wow! elegant solution!

[@habibdurodola5728]

Best solutions , Yes you did !

[@vidhi_bhatt]

simple and on point!

[@DevanshuMevada]

Thanks Man!

[@bty_s]

There is no condition that all array items is started by the same prefix, if this prefix is actually exists. i mean the first ex in the lesson is [flower, flow, flight]. fl - longest common prefix. but in case of [flower, flow, flight, tennis, ten, tenet, tent]. ten - longest common. your solution will not work in such case.

[@deepanshuyadav6815]

So how would u do it....

[@dannytierney2969]

Your second example has no common prefix, as three of the words do not share the prefix "ten" At least, that is how the question is set up.

[@pranjalbansal8576]

can anyone explain line no 6

[@shanky046]

Read about indexOf(String s) method of String class

[@yahyashaikhworld]

if prefix becomes " " after the stripping off of characters, why would it be at the index 0 strs[i]. ?

[@jay-wf3ft]

It doesn’t become “ “. It subtracts each letter that isn’t a common prefix from the word “flower” until they all match. Once they match the loops end and you are left with the longest common prefix

[@AdryanRMC]

I feel myself so stupid after watching this

[@whiz-code]

You a genius

[@ruifan793]

Help me a lot, thanks

[@gokulkumarbhoomibalan5413]

Really helpful!

[@fahdagodzo5795]

This guy is smart

[@jasonliu7186]

Thanks very much!

[@ayushbudhwani]

Nailed it!!

[@Nick-and-Boys]

thanks don

[@mohitdangwal587]

you the BEST!!!!!!!!!!!!!!!!!

[@vrindatyagi6744]

THANKYOU SO MUCH

[@MdineshKumar-gp9wg]

cout

[@blaze9558]

thanks man!

[@simardeepkaur8275]

Thanks buddy