Longest Consecutive Sequence | Google Interview Question | Brute Better Optimal

[@takeUforward]

Please watch our new video on the same topic: kzbin.info/www/bejne/pYCYpn97bKqIoq8

[@ANONYMOUS-ir8xq]

striver i am totally confused with the time complexity in optimal approach to find an element in set we need only o(1)??

[@ANURAGDOIJODE]

in brute force approach time complexity is O(n^3)

[@ANURAGDOIJODE]

one for for loop second may be maxi subarray is n and third for linear search

[@jeevankurian9148]

@9:45 It was like Raj is showing middle finger to us😂.

[@shubhanshusharma7457]

this person deserves lot of respect for giving such a content for us free of cost. massive respect for you bhai.

[@lingasodanapalli615]

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.

[@b_01_aditidonode43]

yes i think the same, it should be N^3

[@sandipanchakraborty8489]

Correct O(N * N * N)

[@alexmercer416]

how? can u explain pls @@sandipanchakraborty8489

[@alexmercer416]

how can u explain pls ? @@b_01_aditidonode43

[@Rahul_Mongia]

no

[@sontujain7851]

The best part is that you just know that you solved the question just after raj draws the diagram. Amazing!!

[@sumanthvarma1908]

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

[@yowaimo890]

bhai wo zinda h

[@khanra17]

🤣🤣@@yowaimo890

[@lucygaming9726]

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.

[@futuretl1250]

how?can you give some hint?

[@RaunitJaiswal-s9v]

for (int i = 0; i < n; i++) { if (a[i] - 1 == lastSmaller) { cnt += 1; } cnt = 1; // This line now always resets `cnt` to 1 in every iteration lastSmaller = a[i]; longest = max(longest, cnt); } for those who are thinking what if we remove the else if statement but keep the code inside it in the loop, the code would look like above

[@prabhagaikwad4849]

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.

[@tusharvlogs6333]

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 .

[@yugal8627]

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

[@ShivamSingh-gk3qu]

@@yugal8627 its O(N^3) bro just do dry run

[@krishanubiswas6869]

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

[@omrasal7945]

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

[@ritikshandilya7075]

Literally the best content available in youtube , it really beats paid content.

[@CodewithKing360]

You understood brutforce and better very well but i do not understtod optimal

[@infernogamer52]

Whenever your heart is broken don't ever forget you're golden💯

[@yourstrulysidhu]

Finally found the explanation of the while loop time complexity. Thanks!

[@RaunitJaiswal-s9v]

Initial State: lastSmaller starts with INT_MIN, an extremely small value that will be replaced with the first element of the array once we begin processing. First Condition (if (a[i] - 1 == lastSmaller)): This condition checks if the current element a[i] is exactly one greater than lastSmaller, meaning it is the next element in a consecutive sequence. If this is true, the current element a[i] is part of the current consecutive sequence, so cnt is incremented to count this element, and lastSmaller is updated to a[i]. Second Condition (else if (a[i] != lastSmaller)): If a[i] is not consecutive to lastSmaller (i.e., a[i] is not equal to lastSmaller + 1), the code checks if it is different from lastSmaller. This condition avoids counting duplicates in the sorted array. If the element is different, it starts a new sequence with cnt reset to 1, and lastSmaller is updated to the current element a[i].

[@thebishalpaul]

correction 13:44 hashset in java also doesn't order elements

[@manavpatnaik222]

Correct

[@time7192]

+1

[@takeUforward]

Let's march ahead, and create an unmatchable DSA course! ❤ Use the problem links in the description.

[@leoved1073]

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 🫂

[@takeUforward]

Yess that was the reason

[@dayashankarlakhotia4943]

Understood

[@heybuddy_JAI_SHREE_RAM]

Thank you brother for this DSA 💥💥course

[@paritoshmalhotra6309]

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

[@calisthenics5247]

And we can also use sorting to reduce it to nlogn time complexity

[@GOJOANDSUKUNAFAN]

​@@calisthenics5247 yes correct I used hashing tho 😭

[@vaibhavpratapsingh9956]

i think the complexity for the first brute force would be O(n^3)

[@takeUforward]

Yes you are correct

[@vivekpatwal4655]

agree

[@leoved1073]

** 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

[@many987]

when I saw this video update today, I was like what, wasn't it uploaded yesterday 😂

[@ksankethkumar7223]

I guess the brute force technique will take O(N^3) and not O(N^2) because for every element we have to linear search until we break out of the longest sequence

[@nagame859]

Nice observation!

[@RajeevCanDev]

That comes under a manually defined function which will not be counted in the loop and would have an another O(n) TC ...as per my observation 🧐

[@ksankethkumar7223]

@@RajeevCanDev It will run in the loop even though it is user defined function and hence TC boils down to N^3

[@RajeevCanDev]

@@ksankethkumar7223 yeahh true👍🏻, but may be there is an another logic by which striver stated it as TC O(N²) or maybe he is wrong

[@ksankethkumar7223]

@@RajeevCanDev idk about that but the approach he mentioned is O(N^3)

[@lillyput2275]

thanku so much striver ji ...loads of love

[@tonylee1868]

Amazing work.... I will complete the whole series....

[@user-ke7fs7ds6h]

awesome videos, but one correction like in brute force approach the time complexity should be o(n^3) , rest everything is perfect.

[@cinime]

Understood! Awesome explanation as always, thank you very very much for your effort!!

[@impalash_ag]

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.

[@Manishgupta200]

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

[@iamnoob7593]

Thank you striver , Very well explained and Time complexity part was amazing.

[@amansrivastava1232]

In my opinion, the time complexity for the brute force solution would be O(n^3)

[@kajiazadali7738]

brute force solution t.c : O(N^3) ?

[@tarunrajput6865]

No bro

[@kajiazadali7738]

Why not ​@@tarunrajput6865

[@venkatraman7357]

Understood. Amazing. Keep going mate.

[@chaitanyabalanagu626]

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

[@Metacognator]

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

[@takeUforward]

unordered set works for O(1)

[@arpitkumarmishra2734]

@@takeUforward but on gfg it says O(N)..?

[@kroax9720]

Life Changing 💕💕

[@trojanhorse8278]

@15:53 worst case time complexity of find operation in unordered_set is O(N) and average case is of O(1).

[@culeforever5408]

understood 🎯

[@vaibhavkotary3949]

sir what do you mean when you say collision happens??? can you explain with example....

[@surbhirathore._]

What's wrong in this code! It's working for half test cases not all Int n = a.length; Int largest = 1; for(int I=0 ; I

[@raorao7329]

bro it should be i

[@meghasharma4875]

i directly got better approach in mind

[@mdfaizanmdfaizan6041]

But we could solve this question with time complexity o(n square logn) first we sort the array and then travel through the each element of the array

[@RaunitJaiswal-s9v]

lastsmaller at the very first would confuse but just think like these on the very first step it will get over right by the very first element of your array cause its not equal just dont get confuse guys

[@prabhakaran5542]

Understood ❤

[@parica117]

understood striver , thank you

[@momentos811]

Your video is very helpful for everyone, thank you ❤

[@joelpappachan7853]

You might be the GOAT of DSA

[@sachinboreoffl]

Great Explanation

[@harshukey6072]

Understood🎉 40 lakh

[@shubhamagarwal1434]

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

[@aryanchauhan2571]

Say that again, after you discover something called “TUF+”

[@kabilm8040]

I TRIED MYSELF T.C = O(NlogN) and S.C = O(1) class Solution { public: int longestConsecutive(vector& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); int count =1; int maxCount = INT_MIN; if(nums.begin()==nums.end()) return 0; for(int i=0;i

[@nikhild.20]

Instead of iterating in set, we can iterate in array as well, right? int longestSuccessiveElements(vector&a) { // Write your code here. setst; for(int i=0;i

[@nirbhaybhardwaj4330]

can you explain me bro why we using " == st.end() " and " != st.end()" ...... he used in many problems but i don't understood......

[@pavansai2859]

this is GOD level man!! Thank you!!

[@shubhamdhiman5602]

How the optimal solution is optimal, still taking O(n^2) and better solution takes only O(nlogn). Can anyone please explain this.

[@SAROJKUMAR-xe8vm]

If I can not be the part of the sequence then I will be the new sequence.

[@balakrishnanr648]

us, really a good one in TC Explain

[@Dhruvbala]

Very well explained, brother. Thank you

[@sukhpreetsingh5200]

Amazing explanation❤️

[@mohammadtanveer8606]

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)

[@shreekarpasupuletia2269]

please write the ode for 1st and 2nd method also in coming videos

[@infernogamer52]

Understood Bhaiya!

[@JK-de2gh]

understood

[@HR-pz7ts]

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

[@shashankgsharma0901]

Understood!

[@RohitRaj-kr7ti]

Hey, The complexity in brute force is N^3, as there is a linear search too. In the optimal code, one point that can be corrected is that while you say that we will iterate over set but essentially you end up reiterating the input array again.. I would request to use the set numbers only, convert them to array and then use it only. int[] numsFromSet = hashSet.stream().mapToInt(Integer::intValue).toArray(); @takeUforward

[@gourabbhattacharjee2128]

Why are you converting the hashSet to an array? This operation takes another O(set size) for unboxing the elements. And you have no other option other than linear search to search for consecutive elements using the array approach. Use the set.contains() while iterating through the set itself.

[@user-mt4jk5gq7g]

i also thinks that the time complexity of brute could be best expressed as O(n raised to 3) in the worst case.Please respond.

[@diggl3358]

Why we don't use an array of frecvente, also can use and bitsed for memories, complexity will be O(n*max) max mean the maximum number, and we read n number and after with for we go through maximum number

[@diggl3358]

Bitset b; Int maxi; Int main(){ Int n; For(int i=1;i>x; b[x] = 1; If( x > maxi ) maxi=x; } Int length=0,cnt=0; For(int i=1;i length) length = cnt; If( b[i] == 0) cnt = 0; } Cout

[@sayantanpoddar5428]

understood please came with String playlist sir

[@cameye9]

We can solve this question in O(N) Time Complexity and O(1) Space Complexity, by taking previous int arr[0] and comparing from index 1 to it's difference is either 0 or 1 if it is 0 continue and else if 1 increments count++ and update maxLen=Math.max(maxLen,count) and else count =1 and previous will be arr[i] current value. By that approach we can easily solve in O(N) time and O(1) space.🙂

[@GOJOANDSUKUNAFAN]

Kinda true only for this array

[@yugal8627]

I think this solution will never come in mind of someone who didn't seen this type of problem.

[@GhostVaibhav]

Understood🔥

[@ShivamSingh-gk3qu]

107,106,105,104,103,102,101,100 for this case the time complexity even using Hashset will be O(N^2+N), bcoz if we are using unordered set then we have iterate from 107 to 100 and when we reach 100 then again we'll iterate using while loop to get the longest sequence. Someone plz correct me if i am wrong ........

[@pradhyumnapalore5942]

No, it is not the case as we are firstly iterating from 107 to 101 and as these are not the first element, while loop will never run while the loop will run for 100 only So, we are only iterating the whole array again for 100, not for all the cases

[@ali_dev7415]

you are missing if condition, if 107 is not the starting element then while won't run

[@gautamsaxena4647]

understood bhaiya

[@ParasSharma-mf8or]

This same video was uploaded yesterday also

[@divyangdheer7292]

Nd then deleted

[@Srinivasssssss]

Fantastic Explaination..!

[@oyeesharme]

thanks bhaiya

[@NazeerBashaShaik]

Understood, thank you.

[@arnavkumar4631]

Understood

[@samuelfrank1369]

Understood. Thanks a lot

[@rajatpatra2593]

Understood ❤️

[@jagratgupta8392]

very nice problem sir understood very nicely sir......

[@abhaymandal4903]

Happy teacher's day striver , Today is 5 th sep and i am watching this one

[@sarthakkharade7112]

understood sir

[@tamilmukbang3789]

Understood. thank you

[@YourCodeVerse]

Understood✅🔥🔥

[@heyOrca2711]

Understood! Sir

[@HARSHA_27]

Understood!!🙇‍♂

[@sumitkawade9396]

Can anyone explain if(st.find(it-1)==st.end()) && if(st.find(x+1)!=st.end())

[@himanshukaushik9223]

First element ka previous search kar raye hai agar vo == end ho Gaya matlab vo nahi ha set ma this means it is 1st ele otherwise vo 1st ele nahi hoga

[@AbjSir]

I think brute should be O(n!) Correct me please if i'm wrong

[@khanra17]

I think the better one is most optimal. finding from set every time, doesn't make it so much slow?

[@dhruvnivatia9222]

This is O(N^2) solution, better to sort the array. '

[@prapti2385]

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?

[@WolfMan-z8k]

Understand

[@juhichoudhary9281]

Understood❤️‍🔥

[@tusharsrivastava107]

Can we not make it easy by using Sorted Set in java ?

[@MaheshPatil-of1zy]

I think the brute force complexity is o(N^3).

[@bharathi66]

Understood Bhai

[@smilemka3342]

set already stores in sorted and unique mannaer right?

[@lakshmiprasanna7058]

Understood 💯💯💯

[@per.seus._]

understood❤

[@utsavseth6573]

as usual, awesome

[@user-is6ky7pp2n]

Understood !!

[@parshchoradia9909]

Understood Sir!