You always provide the best, easiest, and simplest approaches. I watch your explanations and then try to write the code independently, and I succeed most of the time. Keep making such great content. It really helps us a lot.
I was stucking this question for 4 days by watching many of videos but I can't find out the best way to answer this question. But you did and explain it really well. I know I'm not that good as problem solving but you are the one who can explain the concept from really hard to a really human can understanding really easy
@@officialdreamplayz just only 6-7. We are going slow because I think we are missing something or some concept to answer or design to answer the question. I think keep doing it will help us a lot. For me answering in Code war was really easy more than leetcode
great teaching bhaiya. I always look for ur videos whenever I search for a solution of a leetcode question. No one comes close to you when it comes to explaining multiple approaches and finally solving with the most optimal approach . Thanks bhaiya.
I really try to go over the concept, rather than just giving away the code...the same you would be solving a problem in an interview. Thanks for your support. Much appreciated. 😄
bro i stuck at this problem and i dont understand how to solve this question but after watching some video i not getting it better but u solve this question with very simple approach. 👍👍 well done bro
If the string contain a mixture of capital and small letter then sorting can't be the solution... string commonPrefix(vector& strs,int n){ string s1 = strs[0]; int ans_length = s1.length(); for(int i = 0 ; i< n ; i++){ int j = 0 ; while(j
That optimization only works in python or other interpreted languages, where sorting is much cheaper than a loop. In golang or c or c++ it's much faster to do loops, so you don't need to spend O(n log n) on sorting
Interesting solution with sorting - but then you get n*log n. You can simply search the list for the shortest word and then compare it with all other words, thus making it O(n * k) where k is the length of the shortest word. Depending on the input you have in a real life scenario, your approach might be more efficient if the strings are very long, so if the length of the shoertest string k > n where n is number of values in the list, then your approach is more efficient. Anyway cool explanation thanks!
Great explanation, but I would add a check for potential issue where an Index error can occur if the first and last strings in the strs array have different lengths. Like this: min_length = min(len(first), len(last)) for i in range(min_length)
Hey, found a similar problem but no one had a good solution online. The idea is to find the longest palindromic prefix. Would help a lot if you can make a video on this. thanks for the videos. love them.
The efficient solution isn't in fact the most optimal, sorting strings is not nlog(n) but the worst-case & average time is n^2log(n). Only in the best case where the first characters of the string do not match, the TC becomes O(long(n)).
what is the time complexity of brute force. And Sorting must be also compare all the characters internally then just wondering how it is optimized solution
#this code for #python. def pre(a): a.sort() first=a[0] last=a[-1] out="" for i in range(len(first)): if first[i] == last[i]: out+=first[i] else: break return out print(pre(["flower","flow","flight"]))
don't you think that for loop should also have the condition "&& i < last.lenght()" as if the first array has length greater, then it would also check that index char for the last array, which would result in "IndexArrayOutOfBonds" exception like the example: canada, car, czech (sorted) here the first element would have the length 6, so the for loop would also run for the value i = 5, but the last[5] doesn't exist
ok so I came up with the answer, its because the traversal of the string would just stop before it hits index more than the last element, correct me if i'm wrong
Hello... Nice and clear explanation. But i have a doubt. Shouldn't the time complexity of efficient approach be: O(n*s*log(n)) (where n: length of array and s: average length of string) Instead of O(nlogn) (13:52) . If that is the case, then time complexity of brute force would be better than this approach. Isn't it? Also aren't we going to consider space complexity taken by sorting algo internally?
#python:- 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)
Thanks for the video. But in the end, it looks a bit confusing. The time complexity of the "brute force" approach should O(n * m) where m is the length of the string and in the case of the "efficient approach" we will have O(n * m * log n) which is slower than the previous one. Is it a case or did I miss something?
if possible try to show the code for brute force approach also, this helps in understandig the problem in a much better way,btw doing great work,appreciated.
thanks for your feedback and support :)...but usually coding for brute force is not desirable...i only do that in scenarios when you tweak a brute force approach to convert it to an optimal solution.
i have a query , why we are comparing rhe first and the last string in the efficient solution after sorting the strings .. after sorting even first two strings can give the solution
Based on the given constraints for the problem of finding the longest common prefix, let's evaluate the three approaches and determine the most appropriate algorithm: Divide and Conquer: Time Complexity: O(S), where S is the total number of characters in all the strings. Space Complexity: O(M * log N), where M is the length of the longest string and N is the number of strings. Sorting Method: Time Complexity: O(N * M * log N), where N is the number of strings and M is the maximum length of a string. Space Complexity: O(1). First Solution (Nested Loops): Time Complexity: O(N * M), where N is the number of strings and M is the maximum length of a string. Space Complexity: O(1). Considering the constraints of the problem, where the number of strings (N) and the length of strings (M) can be at most 200, all three approaches are feasible. In terms of time complexity, the Divide and Conquer approach has the best complexity of O(S), which is optimal. However, it has a higher space complexity of O(M * log N) due to the recursion stack. The Sorting Method has a time complexity of O(N * M * log N), which is higher than the other two approaches. Additionally, it does not guarantee a correct answer if the sorting affects the relative order of the strings. The First Solution with nested loops has a time complexity of O(N * M), which is slightly better than the Sorting Method. It also has a space complexity of O(1), making it more memory-efficient than the Divide and Conquer approach. Given the constraints and the considerations above, the most appropriate algorithm for finding the longest common prefix among the strings would be the First Solution with nested loops. It provides a good balance between time complexity and space efficiency.
