Longest Consecutive Sequence | Google Interview Question | Brute Better Optimal
Vložit
- čas přidán 5. 08. 2024
- Problem Link: bit.ly/3GiWSJP
Notes/C++/Java/Python codes: takeuforward.org/data-structu...
We have solved the problem, and we have gone from brute force and ended with the most optimal solution. Every approach's code has been written in the video itself. Also, we have covered the algorithm with intuition.
Full Course: bit.ly/tufA2ZYt
You can follow me across social media, all my handles are below:
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
0:00 Introduction
0:52 Explanation of problem.
1:48 Brutforce approach
4:01 Code
5:21 Better approach
10:30 Code
12:56 Optimal approach
18:35 Code
Please watch our new video on the same topic: czcams.com/video/oO5uLE7EUlM/video.html
striver i am totally confused with the time complexity in optimal approach to find an element in set we need only o(1)??
in brute force approach time complexity is O(n^3)
one for for loop second may be maxi subarray is n and third for linear search
this person deserves lot of respect for giving such a content for us free of cost. massive respect for you bhai.
The best part is that you just know that you solved the question just after raj draws the diagram. Amazing!!
I think the brute force is not equal to N*N. But it is N*N*N. Because for every outer loop the inner loop will be traversed N*N times.
yes i think the same, it should be N^3
Correct O(N * N * N)
how? can u explain pls
@@sandipanchakraborty8489
how can u explain pls ?
@@b_01_aditidonode43
no
Let's march ahead, and create an unmatchable DSA course! ❤
Use the problem links in the description.
Idk why did you upload this video again but if you did just because better solution had edge case of multiple duplicate elements then hats off to you man ❤ even though it was negligible mistake still you re-recorded that part and uploaded video again I really appreciate your efforts 🫂
Yess that was the reason
Understood
Thank you brother for this DSA 💥💥course
I believe that you #striver will remain forever in the hearts of lakhs of students around the world ❤
You are more than virat kohli for me because no one can come closer to your selflessness regarding contribution to the community
Two people are my inspiration in this world #Virat #Striver
For your HardWork and dedication
bhai wo zinda h
🤣🤣@@yowaimo890
Literally the best content available in youtube , it really beats paid content.
For anyone following the SDE Sheet, solve all problems of Disjoint Set Union (DSU) in Graph Series first.
This question can be easily solved using DSU and very easy to come up too.
Again, thanks to Striver for creating an awesome Graph playlist.
how?can you give some hint?
** Timestamps **
0:00 Introduction
0:52 Explaination of problem.
1:48 Brutforce approach
4:01 Code
5:21 Better approach
10:30 Code
12:56 Optimal approach
18:35 Code
Finally found the explanation of the while loop time complexity. Thanks!
Understood! Awesome explanation as always, thank you very very much for your effort!!
I implemented the brute force first, the time complexity is O(n^3) as we need to start over the search for every found consecutive number. As array may be in sorted order.
glad i found this. was also thinking the same how can it be n^2 . because like if we have 104,101,102,103. so for 101 i need to check the whole array again then when i reach 103 again from starting .
@@tusharvlogs6333 For every element you are traversing the whole array , to traverse each element it is O(N) and for each element you are traversing the array again so another O(N) , i.e., O(N^2)
@@yugal8627 its O(N^3) bro just do dry run
thanks for the confirmaton...i was also thinking that...striver may have forgotten to take into account the time complexity of the linear search part....
int longestSuccessiveElements(vector& a) {
sort(a.begin(), a.end());
int n = a.size();
int maxCount = 1, c = 1;
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1] + 1) {
c++;
maxCount = max(maxCount, c);
}
else if (a[i] != a[i - 1]) {
c = 1;
}
}
return maxCount;
}
more simple app
Time complexity explaination in depth by yours after every explaination of problem is really really helpful that i love the most. And better and optimat solution here is really cool. I solved better solution by myself before watching your tutorial. Thankyou Striver
Understood. Amazing. Keep going mate.
Your video is very helpful for everyone, thank you ❤
Very well explained, brother. Thank you
Amazing work.... I will complete the whole series....
Thank you striver , Very well explained and Time complexity part was amazing.
#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India.....
Whenever your heart is broken don't ever forget you're golden💯
Amazing explanation❤️
this is GOD level man!! Thank you!!
Great Explanation
Fantastic Explaination..!
very nice problem sir understood very nicely sir......
us, really a good one in TC Explain
Understood. Thanks a lot
Understood, thank you.
You might be the GOAT of DSA
Life Changing 💕💕
when I saw this video update today, I was like what, wasn't it uploaded yesterday 😂
as usual, awesome
Understood. thank you
Understood ❤
understood 🎯
Understood Bhaiya!
sir what do you mean when you say collision happens??? can you explain with example....
correction 13:44 hashset in java also doesn't order elements
Correct
Understood🔥
Understood✅🔥🔥
Understood ❤️
Understood, thanks :)
Understood Sir!
awesome videos, but one correction like in brute force approach the time complexity should be o(n^3) , rest everything is perfect.
Understood!!🙇♂
Understood!
Understood❤️🔥
Understood 💯💯💯
Understood! Sir
Understood👍🏻
Hi Raj, the TC for the BF solution should be O(n^3) and not O(n^2) since there are 3 nested loops and inner while loop will run for nearly n times and same goes for the function that does the linear search.
its great, thanks
Thank you Bhaiya
Understood !!
How the optimal solution is optimal, still taking O(n^2) and better solution takes only O(nlogn). Can anyone please explain this.
Understood Bhai
Thank you
In the optimal approach, is there any way. we could remove the elements from the set after checking. For example when we check for 100, theres no element before it as it is the starting element. Can we remove 101 and 102 after counting it as the longest consecutive subsequence?
Using treeset would also be a better solution, as adding elements into treeset takes nlogn time and then parsing and checking is easy after that
Understood 🚀🚀🚀
We can use unordered_map to replace the Linear Search in the brute force solution to bring down it's complexity to O(n^2).
And we can also use sorting to reduce it to nlogn time complexity
@@calisthenics5247 yes correct I used hashing tho 😭
Can anyone pls explain me what is set.end() is representing here ? Im not able to get the condition in while loop .
Happy teacher's day striver ,
Today is 5 th sep and i am watching this one
Thanks Brother
understood❤
Hello sir,
I had a doubt that using set(ordered) just takes o(logN) know????
Understood 🔥🎧
understood ♥
brute force solution t.c : O(N^3) ?
No bro
Why not @@tarunrajput6865
understood
please came with String playlist sir
in better approach,wont be else condition would be else if(arr[i]-1!=lastsmaller)??
Understood.
fabulous
understood!
In my opinion, the time complexity for the brute force solution would be O(n^3)
UNDERSTOOD
If I can not be the part of the sequence then I will be the new sequence.
Understood
@15:53 worst case time complexity of find operation in unordered_set is O(N) and average case is of O(1).
Understood🎉
40 lakh
set already stores in sorted and unique mannaer right?
understood😍
bhaiya yha pr aapne for each loop me while loop lagaya hai yha time complexity O(n*n) nhi hoggi ?
I think we need to consider the time complexity of underlying data structure as well
I mean if we are using set.find() then it not happens in O(1) time and we have not considered its time complexity...
we can insted go for unordered map
unordered set works for O(1)
@@takeUforward but on gfg it says O(N)..?
i think the complexity for the first brute force would be O(n^3)
Yes you are correct
agree
understood✔✔
Understand
Inspiration
code 360 not show some of the code which i was done before, can anyone tell about this ?
You understood brutforce and better very well but i do not understtod optimal
what if all size of list is n and all elements are distant to each other by a difference of 2. Meaning the longest consecutive subseq is 1. Then this algo is taking TC of n^2
Brute force will be O(N^3) isn't it. Assume we are given a sorted array with all consecutive integers.
Why there's no trie python code in the site?
Understood.............
understood
I think the better one is most optimal.
finding from set every time, doesn't make it so much slow?
Isn't the TC just O(N) for the better approach where we sort the array ? since we are not sorting and iterating in the same look the Time Complexity will be O(log(n)) for sorting and O(N) for iteration to determine the max sequence length. With O(N) dominating O(log(n)) due to beign higher thus resulting in TC of O(N) ?
O(nlogn) for sorting bro, nobody can sort in O(logn), so the overall TC will be O(nlogn)
the time complexity for insertion in set is O(logN) so the time complexity for this algo will be O(NlogN)
no its unordered set
For unordered_set the time complexity of every operation in set is O(1). So, after N operations the TC will be o(N) in the best and average case and O(N^2) in the worst case if collision happens.
python optimal solution:
longest=1
hashmap={}
count=0
n=len(arr)
for i in range(n):
num=arr[i]
hashmap[num]=1
for j in range(n):
num=arr[j]
count=1
while num+1 in hashmap:
count+=1
num+=1
longest=max(longest,count)
return longest
i used hashmap to access the elements which will be taking o(1) complexity so o(n+n) will be time complexity and sc-->o(n)
good video