Longest Consecutive Sequence | Leetcode(Hard) | GooGLe

[@takeUforward]

Please watch the new video which covers it in more depth, and also prints it: kzbin.info/www/bejne/pYCYpn97bKqIoq8 Understooooooooooooooood? . Instagram(connect if you want to know how a SDE's normal life is): instagram.com/striver_79/ . . If you appreciate the channel's work, you can join the family: bit.ly/joinFamily

[@takeUforward]

@RAJVEER Singh video release hua hi nai h XD

[@BatMAn-kq3zf]

sir please create internship roadmap for people who have wasted first year i.e have 1 year left

[@abhinavmishra7617]

yuppppppppppppppp! ek baar me hi smjh aa gaya dono approach....awesome bro....thanks!

[@sahilchoudhary1473]

yes

[@adithyaharish3530]

instead of using set count(), i did find() method and the time complexity heavily increased. Also, why cant we use map or vector instead of set

[@vishal_rex]

I have a doubt. Let's take a test case: [3,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1] While loop won't execute for 3 & 2 since 1 is present. But while loop will be executed for 1 since 0 is not present, and that will be executed (n-2) times here. I think instead of iterating over nums which consists repeated elements, we can iterate over hashset then for 1 it will execute while loop only once resulting time complexity O(n) + O(n)

[@faisalahmed2394]

This is a really good point, Thanks!

[@mohsinhusain4]

Agreed. On Leetcode just this small change made it much more faster.

[@hardikagarwal3938]

Valid Point

[@rishavgupta7868]

how inserting n elements takes O(n) time? in set insertion takes logn time so it should be nlogn then it is no better than just sorting and linearly checking

[@mohsinhusain4]

@@rishavgupta7868 Use unordered set.

[@AnkitMishra-mz4xt]

If you are getting TLE, just declare it as unoredered_set it will pass

[@kartiksuman9814]

Bhai it really worked....but what's the reason behind this?

[@kartiksuman9814]

Bhai it really worked....but what's the reason behind this?

[@tusharnain6652]

@@kartiksuman9814 Accessing element is faster in unordered set , costs O(1), but in orderd set, its O(log n)

[@kartiksuman9814]

Okay... thankyou

[@adityaajay29]

@@kartiksuman9814 tc of set is O(nlog) because it sorts the elements, but for unordered_set, its O(n)

[@sandiptasardar9091]

It will give tle on leetcode. Use this instead int longestConsecutive(vector& nums) { unordered_set s; for(int i=0;i

[@beinghappy9223]

Thank u ❤

[@shikharmalik3787]

bro i did get tle but idk why ??? can you tell why it gives tle

[@techmoon_]

@@shikharmalik3787 The time complexity will be O(n^2). So TLE

[@yashtokekar4091]

i used unordered map instead of set, it runs but is very slow compared to set, why?

[@codesmart9044]

after watching the intution i have coded it myself, way of your teaching is magic. i am feeling the improvment. Thanks a lot

[@fromdjangoimport__help__3585]

if u r getting error use this simple solve -- sets; for(int i=0;i

[@sidhaantgupta1974]

The hashset solution is actually slower in practice than the sorting one

[@sourin.majumdar]

sorting one takes around 15 ms on avg but the set one is takinh 800+ ms

[@MrHip4hopper]

@@sourin.majumdar exactly its O(n2) actually

[@anurondas3853]

Guys the absolute run time actually depends upon a lot of different things than your algorithm complexity. It happens many times that an n squared solution runs faster than an n solution, but this doesn't mean that O(n^2) is suddenly better than O(n). Striver actually talked about it before.

[@amansinghal4663]

​@@anurondas3853 Yes you are right. Also particularly in leetcode, the time it shows after the solution gets accepted cannot be used to judge the actual time taken by an algorithm. It's just comparing our algorithm's running time with running time of those who have submitted it earlier. It may happen that when i am running my code, the leetcode's servers are running slower than usual and hence it took more time than others code. I have noticed one very interesting thing about this in leetcode. After a leetcode contest, if you try to submit a solution for any of that contest's question, then even if you write a O(n^2) solution, leetcode will tell that it is faster than 100% because it is a new question and it has not been submitted by many users till now.

[@gauravraj2604]

Deciding at the last that time complexity of given solution is actually ~O(n) was really challenging. Thanks Striver for this explanation.

[@agrajgarg2831]

After striver posted this video, the difficulty of this question got reduced to medium. Power of striver.

[@mannthakkar]

its actually just a simple application of hash sets, shouldn't it be easy

[@codingachinilgtifirbhikrrh9009]

@@mannthakkar the concept is easy but the implementation is a lil bit tricky

[@ritesh1211]

Yes it does give TLE just replace nums with hashSet in second for loop I.e for(int num: hashSet) not for(int num: nums) this will make complexity to o(n) he missed this by mistake

[@yatin3699]

thanks bro

[@yatin3699]

could you also tell what to correct in the 4sum problem,it is giving runtime error

[@amitarya4894]

thank you so much buddy, it works now

[@pawanchandrajoshi841]

@@yatin3699 Inside the second loop (j loop), for calculating target2 use "long long" instead of using "int", this will solve the issue.

[@herculean6748]

But what is the difference? Both nums and hashSet are having same element? Why it is giving TLE with nums and not with hashset? Please can you explain

[@gauravidesigns]

I stopped at 3:36 of your video and tried the problem and got AC . The moment you said it would be a hash set I got it. Now watching the whole video again after solving. Thank you sir.

[@Yash_Parashar]

Bhai I am not getting brute force approach can you tell me???

[@aniketbhoite7168]

@@Yash_Parashar brute force ...if you are sorting a vector ...it will take n logn

[@codingachinilgtifirbhikrrh9009]

1 doubt : the time complexity will not be O(N), if it contains duplicate elements in significant numbers(n-1,n-2 etc) beacuse then it will loop for every duplicate elements and it will b order of O(N^2)

[@maitreyikshetrapal1644]

but we are using set..so it will eliminate duplicate elements

[@shashanksrivastava7262]

sets doesnt contain duplicate values

[@VishalGupta-xw2rp]

Set won't store duplicates but I think what he is trying to say is that if the array itself contains duplicates then we will be checking that minimum number again and again and again. This question will work fine if the array itself doesn't contain any duplicates

[@sasidharnaidu4507]

​@@VishalGupta-xw2rp even if array contains, duplicate elements, the order won't change to O(N2).

[@RahulSingh-de6tb]

Your way of approaching a solution is amazing and is sufficient enough to build own solution. without looking into code, that's the beauty of your channel. Thanks!! btw you mistakenly written set instead of unordered_set.

[@takeUforward]

Glad it was helpful!

[@ranasauravsingh]

UNDERSTOOD...!!! Thanks, striver for the video... :)

[@abhishekmore5856]

if we add just visited map , time can be reduced by 800ms . unordered_map mp,vis; for(auto num:nums) mp[num]=1; int ans=0,cnt; for(auto num:nums) { cnt=0; if(vis[num]==0&&mp.find(num-1)==mp.end()) while(mp.find(num)!=mp.end()) cnt++,vis[num]=1,num++; ans=max(ans,cnt); } return ans;

[@mdaffan1650]

we can actually iterate through the set as the set is having sorted elements and can get to the solution and it will also be O(n) solution

[@itsarAnkit]

🤣

[@shohanur_rifat]

use an unordered map insert all of the values as keys and set the key's values to 0.When you iterate through the map,set the values of the keys equal to 1 when you have checked the value so that you know the next time you have look for it that it has been checked.

[@divyareddy7622]

how is this useful in this problem? i didnt understand

[@reassume4826]

Brilliant Approach....I actually solved the question by counting forwards and to reduce time complexity, I stored previously counted length from that point. Damn, I should have also thought of doing backward count check ....

[@tanyacharanpahadi158]

maze aa gaye. after knowing the approach its difficult to believe that this question comes under hard category. Thank you striver really missed you.

[@venkateshn9884]

Now Leetcode moved this question into "Medium" category😅

[@sagarsharma007]

@@venkateshn9884 xd

[@Tarun-Mehta]

Thats what i call a brilliant explanation 🙏

[@manojgmanojg9600]

Wonderful Explanations, before watching this video,by question i sawn that, it is very hard and difficult to understand but after watching this video of striver bhaiya ,I understand that hard problem is very easy.

[@lokeshagarwal873]

Hi, Thanks a lot for helping us. I try to understand the concept and try to implement. So here is Naive Solution in python, class Solution(object): def longestConsecutive(self, nums): """ :type nums: List[int] :rtype: int """ if(len(nums) > 0): le = 0 cle = 0 nums.sort() print(nums) for i in range(0, len(nums)-1): curr = nums[i] nxt = nums[i+1] if((curr) == nxt): cle = cle elif((curr + 1) == nxt): cle += 1 else: le = max(cle,le) cle = 0 le = max(cle,le) return le + 1 else: return 0 Optimal Solution in python class Solution(object): def longestConsecutive(self, nums): """ :type nums: List[int] :rtype: int """ "pushing every thing into the set" elements = set() longest = 0 for i in range(0, len(nums)): if nums[i] not in elements: elements.add(nums[i]) "now we need to check if the element is present in the set or not" for i in range(0, len(nums)): flag = True val = 1 if((nums[i]-1) not in elements): while flag == True: if((nums[i] + val) in elements): val += 1 else: flag = False longest = max(val, longest) return longest

[@shri9229]

1.Insertion in a set takes O(log(n)) time , 2. we are inserting all the elements so we have N elements to enter 3. Thus building the set itself will take O(N*log(N)) how is the algorithm O(N) and not O(N*log(N))

[@phoenix-be8ko]

Same ques here

[@nisargsheth5153]

We are inserting in unordered_set or hashset which has insertion complexity of O(1).

[@SwapnilSarkar]

Inserting into a hashset takes constant time complexity O(1)

[@shri9229]

@@SwapnilSarkar Thank you , what you are saying absolutely made sense to me , in my comment I was talking about 12:48 where the cpp solution explained has a set rather than an unordered_set . So, that was my concern.

[@shri9229]

@@nisargsheth5153 @Swapnil Sarkar Thank you , what you are saying absolutely made sense to me , in my comment I was talking about 12:48 where the cpp solution explained has a set rather than an unordered_set . So, that was my concern.

[@sarswataryan59]

For those of you who might be thinking how it is O(N) - when you calculate carefully you will see that the while loop after traversal for each element of the array can maximum go upto the sum of N that's why the time complexity will add upto 3N only. In case of N^2 every element has the possibility to go upto N times but that is not the case above, here all of them combined can go upto maximum of N.

[@krsingh.shubham]

finally... ! cant ask for more, but good and more helpful if we get atleast two videos on the series.

[@itsarAnkit]

how the time complexity is O(n) as insertion on map takes log(n) time and for n size array time will be O(nlogn)

[@wanderer_ankur]

Nice explanation Striver bhaia .. thanks for making this series .. each and every question helps me to get more better in data structures 😍

[@aishwarya1895]

Literally you are doing great ✌

[@rajatbatra7416]

unordered_set takes average of O(1) time in insertionbut a set takes O(log n ) time. So we need to use unordered_set instead of set in c++

[@shahjaysheeldipalbhai207]

yes he told hash set ,so it is same as unordered set.

[@SlapB0X]

We can do 2 things: 1. Insert into ordered map - O(logN) - and access elements which is O(1).. overall time complexity - O(NlogN) 2. Insert into unordered map - O(1) - and access elements which is O(logN) .. overall time complexity is still - O(NlogN) i dont understand how either of these can be O(N)

[@krishnavamsichinnapareddy]

Superb explanation 🔥

[@sauravdhar1696]

Clement's girlfriend has started haunting me now .

[@yashgarg8906]

@code fire i dont understand

[@narc7885]

There have been many comments on KZbin abusing,mocking that girl because that ad is so damn annoying. I don't believe in disrespecting someone but at a certain point it literally annoys tf out of you. Clement should reconsider his marketing choices and not anymore use his gf....

[@sauravdhar1696]

@@narc7885 I know right. I agree she's cute but watching the same advertisement over and over again is super annoying. Yaa I get it Clement , to become a software engineer at Google I need a subscription of algoexpert .😂

[@techscout4051]

@@narc7885 get adblocker for youtube kid!

[@GAMERSINCE-br2fw]

Don't stalk my future wife😂😉@saurav dhar

[@braggergamer4975]

just using a set to store the nums arr and using the 1st approach also gives us O(n) time and O(n) space (also runs faster on leetcode) here is the code... int longestConsecutive(vector& nums) { set s; if(nums.size()==0) { return 0; } for(int i=0;i

[@manistrikes]

complexity will still be o(nlogn) although the soln will be accepted since set uses o(nlogn) for storing n elements.

[@nupurgarg6791]

class Solution { public: int longestConsecutive(vector& nums) { sethash({nums.begin(),nums.end()}); int longeststreak=0; for(int num:nums) { if(!hash.count(num-1)) { int currentnum=num; int streak=1; while(hash.count(currentnum+1)) { currentnum+=1; streak+=1; } longeststreak=max(streak,longeststreak); } } return longeststreak; } }; it works

[@imonraj]

Very nice videos.... Really appreciable

[@pritishpattnaik4674]

Ver Nice Approach //optimized approach => tc - o(n), space - o(n) int longestConsecutiveOpt(vector &nums){ set hashSet; for (auto x : nums){ hashSet.insert(x); } int longestStreak = 0; for (auto x : nums){ if (hashSet.find(x-1) == hashSet.end()){ int currNum = x; int currStreak = 1; while (hashSet.find(currNum + 1) != hashSet.end()){ currNum++; currStreak++; } longestStreak = max(longestStreak, currStreak); } } return longestStreak; }

[@tarunboricha]

insted of using set we can use unordered map to optimise code even more This is my code : unordered_map mp; int ans = 0; for(auto it:nums) mp[it] = 1; for(auto it:nums){ if(!mp[it-1]){ int n = it; int temp = 1; while(mp[n+1]){ n++; temp++; } ans = max(ans, temp); } } return ans;

[@philosphize]

It was nice explanation, I actually saw this solution on leetcode but didn't get the logic ,,but now I think this is so easy after watching your explanation Hey buddy Thanks

[@shubhankurkumar539]

Just in case someone needs brute force solution as discussed above class Solution { public: int longestConsecutive(vector& nums) { if(nums.size()==0) return 0; if(nums.size()==1) return 1; int n=nums.size(); sort(nums.begin(),nums.end()); vectorv; v.push_back(nums[0]); for(int i=1;i

[@avnishsingh1538]

the explanation is great

[@qwi3630]

bs bro. aaj dekh raha tha 'Striver' naam ka mouse GDocs mein moj kaat raha tha. pata chal liya tha video aane wali hai. Xor wale question pe video ayegi to real satisfaction milegi jindagi mein. Xor subarray wala karke depression ho lia. ty for support

[@sen-th3xo]

haan bhai XOR ka efficient solution ka video jaldi bro

[@Zero-tu3ey]

+1 on XOR video

[@uravggymbro7338]

"Count number of subarrays with given XOR" referring to this I think? Yeah I'd like a video for that

[@ludrayn936]

XOR question on Day 4 was supposed to clear problems not create more... XD Help would be appreciated

[@johnson3049]

xor video nikalo bro jaldi waiting for it

[@akhileshgoswami7699]

hey Stiver i want to ask you one question. in C++ code every time we are using count function of set , and time complexcity of count() in set is O(logN) then how dose the time complexcity of this algo could be O(N) it should to be O(Nlogn) correct me if im wrong? yha it's true that in java contains() use O(1) but in c++ count uses O(logn) so i think the time complexcity of C++ code should be O(nlogn) rather then O(N) it could be (N) if we use unordered_set coz the avarage cp of unordered_set of count function is (1) and wrost is O(N)

[@mohammedsamir6846]

yup i am thinking the same and leetcode m bhaia ka solution accept b ni hora we should use unordered set in case of c++!

[@joydeeprony89]

so smooth and crystal clear explanation.

[@adityapandey8245]

Thanks Bhai!! understood the algorithm and solved in a jiffy

[@prasantharavindramesh1078]

bro fantastic explantion as always.I just have couple of doubts. 1.Can i extend this code when all array elements are negative.?.. 2.Do we need to include cases like if there are no elements in array then just return 1 for the length and if there 0 elements return 0. Thanks bhaiya.All the videos have awesome explantions. Thank you so much for making these videos

[@WhoSangItBetter]

Great vid as always

[@adityadixit5631]

Thank you for explaining the time complexity, why Time Complexity = O(n) is real key

[@ShubhamSingh-go8om]

JAVA Solution = 10:52 C++ Solution = 12:21

[@harshavardhanravada4509]

sir i think we need to use unordered map for time complexity of O(1)*n for going through entire loop other wise it will be O(nlogn)

[@puspeshkumar3356]

The explanation is really great

[@omk2990]

I'm still confused why Time complexity is O(3N), isn't it O(N) +O(N*N) ???

[@NikhilSingh-pd7wc]

Yes I am confused too.

[@codingachinilgtifirbhikrrh9009]

yes ur right that will be in the cases of duplicate elements, iterate over the hashset instead of the array to avoid that

[@easward]

doesn't insertion of N elements into an ordered Set takes n*log(n) time? also in worst case we are using contains function which takes log(n) time in n length iteration , not n*log(n) time now?

[@varuntaneja7073]

I think you used set instead of unordered_set in the c++ solution ......btw awesome video

[@takeUforward]

yeah it might have been, you can tell that to the interviewer does not matters that most.

[@anshoorajput1413]

yaa that will make the overall time complexity (nlogn)

[@priyadarsinipaikaray6271]

awesome explanation !!!😍

[@Chiby5570]

absolutely loved the intuition

[@navneetkushwaha1830]

❤️ great examplanation

[@Tommyshelby602]

int longestConsecutive(vector& nums) { unordered_set st; int n = nums.size(); for(int i=0;i

[@deeppatidar9017]

Solution is good but shouldn't the time complexity be O(n^2) as the while loop for finding the length of the sequence lies inside the for loop?

[@manistrikes]

No...finding any element in hash set requires o(1)..so o(n) for the consequetive sequence encountered and o(n) for the traversal and o(n) for initial insertion of elements in hashset thatswhy o(3n).

[@vaidviyogi4048]

By iterating the set in cpp class Solution { public: int longestConsecutive(vector& nums) { if(nums.size()==0){ return 0; } set s; for(int i=0;i

[@jaynilgaglani9480]

Can you also talk more about the intuition behind the approaches used for solving this problem?

[@takeUforward]

I said that in the video, please watch it! I have mentioned about the intuition that I am looking to start from the minimum which is my intuition!

[@jaynilgaglani9480]

@@takeUforward Oh, Yeah! Got it.

[@decodingParinda]

@@jaynilgaglani9480 You could refer to my code explanation also. leetcode.com/problems/longest-consecutive-sequence/discuss/789257/Easy-Java-Solution-with-Explanation-O(N)

[@joseph2073]

Thnku so much bhaiyaa 💖💖💖

[@preetikushwaha8734]

the best explanation ever! thank you

[@sarthakbhatia7888]

Brilliant explanation!

[@riddhisharma9582]

Wonderful Bhaiyaa.. Pls iska union-find wala soln pe bhi thoda insight dedo

[@adityagupta9719]

@striver please explain why this solution is also working 'int longestConsecutive(vector &num) { unordered_map m; int r = 0; for (int i : num) { if (m[i]) continue; r = max(r, m[i] = m[i + m[i + 1]] = m[i - m[i - 1]] = m[i + 1] + m[i - 1] + 1); } return r; }'

[@dhananjaysahu9076]

What a simple approach it is but my tiny brain couldn't think about it 😭😭

[@ujjwalmittal3785]

I guess there is a need to erase elementd from unordered set also otherwise time may reach upto n2 . Let's suppose when have n/2 elements forming a sequnece and n/2 elements repeated . Eg 9,8,7,6,5,4. N/2 elements And reamining n/2 as 4,4,4,4,4, This will go upto n2 time complexity

[@takeUforward]

No, try to do it properly, i have showed an example in the explanation

[@ujjwalmittal3785]

@@takeUforward On submitting code time showed 552 ms in leetcode and as soon as I added a line of erase ,time got reduced to 12 ms . The logic is absolutely same , but the line is added keeping duplicate elements in mind

[@takeUforward]

Watch out the video about how to use leetcode on other channel striver to understand its not the case. Try writing a cnt++ to count the number of operations, you will have a better idea

[@Vibewithgautam]

At the time of video, this was a hard problem..... And now it came down to Medium... Striver's effect 😎

[@GauravSingh-le8mq]

hey, 1 thing I wanted to ask, if we can sort the array in linear time, I mean.....they have given the range of numbers from -10^9 to 10^9 so digits are constant so radix sort + bucket sort for each digit combined can sort the array in linear time correct? after that everything is straight fwd, correct? let me know if I am missing something.

[@akshraj2197]

Sir I have heard about c++ set is implemented in bst. So for inserting the value in to the set is nlogn then how complexity n And sorry if I'm wrong

[@jaydave2500]

set(which is ordered ) is implemented from bst and unordered set is just a hash table same with map and unordered_map

[@tejaswarambhe7464]

@@jaydave2500 thanks for info

[@linguisticgamer]

More optimised way: public int longestConsecutive(int[] nums) { Set set = new HashSet(nums.length); int count = 1; int maxCount = 0; for(int i = 0; i < nums.length; i++){ set.add(nums[i]); } for(int i = 0; i < nums.length; i++){ if(set.contains(nums[i])){ boolean run = true; int forward = nums[i] + 1; int backward = nums[i] - 1; count = 1; while(set.contains(forward)){ set.remove(forward); forward++; } while(set.contains(backward)){ set.remove(backward); backward--; } maxCount = Math.max(maxCount, forward-backward-1); } } return maxCount; }

[@sharanpreetchadha3579]

How is it exactly O(N) algo ? Suppose when we check in the for loop if a number smaller then the number at current index of the array exists and there is no smaller number then a while loop will start which will start counting till we can't find a number which belongs to the current subsequence . So it will not be exactly O(n) right .So can someone please throw some light on this topic?

[@takeUforward]

Checkout the last example explained !

[@ballisandeep3953]

Amazing. Thank you Bhaiya

[@pravinyakumbhare4864]

Great work bhaiya int longestConsecutive(vector& nums) { unordered_mapm; int r=0; for(auto i:nums) { if(m[i]) continue; r=max(r,m[i]=m[i-m[i-1]]=m[i+m[i+1]]=m[i+1]+m[i-1]+1); } return r; }

[@sagardas4569]

Really amazing love you love you love you vaiya😋😍😍

[@ankitkumaryadav562]

Time complexity to O(nlogn) Hoga because inserting the element in set it takes long(n) time if we insert N element it takes Nlog(n)

[@takeUforward]

Unordered set average case me O(1) me chal jaata. But the worst case of unordered is o(N)..

[@ankitkumaryadav562]

@@takeUforward Thank you Bhaiya for clarification :)

[@zehrxsyed]

you explain really well. thankyou;

[@Mohith7548]

I just have feeling that unordered_map will slow the performance after some time due to collisions as Hashtable is its underlying ds. Better use bool array if n is bounded.

[@takeUforward]

Yes, just mention this in the interview it will work!

[@casual_chess]

Where is unordered_map used? I can see only set. And how can we use bool array instead. Please reply.

[@akhilgupta3664]

@@casual_chess U can use Hashmap with Key: Integer,value : boolean where value false means this is not the start of the consecutive sequence and value true means this is a start of the sequence. and run the loop only for that key where value is true i.e the start of the sequence, rest Logic is same !!

[@debugagrawal]

bhaiya ye lo more cleaner code poora logic in ~3 lines and easy to understand streak=1; int currentNum=num; if(subseq.find(num-1)==subseq.end()) while(subseq.find(currentNum++)!=subseq.end()) longestStreak=max(longestStreak,streak++);;

[@mohammedwaseem8599]

Thank you sooooooo much bro!

[@HimanshuSingh-vg6rp]

Asked by interviewer today 🙏

[@mukundnayak7310]

How is the time complexity O(N),if N is large then there can be many sequences right? So inner while loop will be executed multiple times,wont it it affect time complexity?

[@manistrikes]

but the inner while loop executes only once for any subsequence thereby adding t=o(n) to complexity...suppose we have 2 ,3 ,4 ,1,101,200,102,103 we will have while loop running for the starting of sequence (1,2,3,4) from 1 and (101,102,103) from 101 i.e n times only in the entire length of hashset...It wont run from (2,3,4) nor for(3,4) nor for(102,103)....Hope this helps

[@shivambajpeyi9008]

C++ code : 12:20

[@vodnalasricharan1323]

Getting TLE on leetcode if we use set but not with unordered_set.can anyone explain why?

[@anjalis8483]

Because set works in O(logN) complexity, unordered_set in O(N)

[@122souravsinha5]

Nice explanation!! Just one doubt , doesn't inserting n elements in a set takes nlogn time. Please correct me if I am wrong.

[@_deepdhar_]

Bro I took your naive solution advice and tried solving the problem in my way, and damn... It got accepted in June LeetCoding Challenge. Damn Bro, thank you❤💥👌 Later on I noted down your efficient solution too🙌😁

[@om_1_2]

Understood bro👍👍👍

[@bhushanpatil2601]

good work bro... HAPPY!!

[@sanjaysingh5007]

Search time complexity is O(logn) and i think you solution is of O(nlogn) using map of C++.

[@takeUforward]

unordered map takes o(1) in average that has been taken into consideration

[@aakashsaini9970]

@@takeUforward but what about worst case bro ( worst case searching time will be O(n^2) in case of unordered_map and unordered_set.) ,consider all possibility your code run O(N) in java but in c++ you use set and T-O(NlogN) for insertion into set.

[@SharvanKumar-ui1kw]

set take O(logn) to one element , so than it use unordered_Set inplace of set

[@ushnispanja7121]

set takes O(logn) time

[@SharvanKumar-ui1kw]

@@ushnispanja7121 yes bro

[@aakashsaini9970]

​@@SharvanKumar-ui1kw worst case searching time will be O(n^2) in case of unordered_map and unordered_set.

[@kartikeyagupta8111]

@take U forward sir, how the optimal solution code run in O(N) time complexity, since inside for loop you run a while loop and if the longeststreak is of length 1 when for every element you run while loop then time compexity comes out to be O(N^2)

[@takeUforward]

Nah, count the iterations the inner loop does not always runs for N time, observe carefully..

[@mohammedmoin7888]

@@takeUforward sir I had the same query .thanks for answering it 👏👏👏👏

[@roberttguo606]

@@takeUforward How do you say that? Even the inner while loop run m times (m

[@AmitSingh-ut4wt]

@@roberttguo606 I also has the same doubt for the worst case the while loop will run for n times. Then the complexity will be O(N^2). The question also did not mention the longest consecutive sequence length whether it is less than n or not. Please @take U forward or anyone can clear this doubt

[@sachinworld_]

search time of unordered_set O(1) -> Average , and set -> log(n)

[@yashsrivastava5128]

if the element is in decresing order like n,n-1,n-2,,,5,4,3,2,1 then unitl element 2 we get all element-1 in a set .But at last the element we get 1 and 1-1=0 is not in set so we then check for 1->2->3->4->....->n so time complexity wont be O(n^2)?

[@rahulrawat4265]

If half of the array is filled with 1s and rest with an increasing seq of 2, 3, 4, 5... Ex- 1 1 1 1 1 1 1 1........ 2 3 4 5 6 7 8.... Then, we will count 1, 2, 3, 4...... seq, N/2 times, which will make the solution O(N^2). Am I missing something?

[@takeUforward]

No it won't make, watch the entire video! And count iterations while doing dry run!

[@rahulrawat4265]

@@takeUforward Actually I'm talking about the code, if a 1 is encountered again... the code will again loop for the streak... but that can be improved by some modifications, so alright.

[@takeUforward]

@@rahulrawat4265 but it will wont run n^2 times, think on it properly!

[@mayurkoli4145]

solution can be improved by keeping an extra flag for every starting value of a streak.if streak starting from 1 is already visited then move forward.

[@being.popular]

@@takeUforward the while loop runs 25 times in this case. the total iterations are (n/2)*(n/2) + (n/2) i.e. the total time complexity will be O(n^2) in this case. @striver bhaiya pls correct me if I am wrong.

[@fahrenheit2109]

after watching this video, leetcode set this questions difficulty to medium.

[@gauravidesigns]

Understood sir, Love You a thankyou sir

[@okokok3321]

how is the brute force solution faster than 75% of submissions on leetcode while the optimized is only 5%

[@gaunikasrivastava7851]

In gfg, a solution with priority queue is also there. What if the interviewer asks me to discuss that approach too?

[@anshoorajput1413]

In the priority queue, insertion operation takes O(logn) complexity, so inserting n elements will take O(nlogn) and it's mentioned that t.c. should be O(n).

[@adithyaharish3530]

you are doing a great work :)

[@gowthamarun43]

if i submit the same in leetcode it shows TLE but if i use unordered map it passes. actually by doing sorting it shows lesser runtime wat to do bro??

[@takeUforward]

the runtime at leetcode is highly fictional, watch my this video to understand,... kzbin.info/www/bejne/r5fCZ2ukfd6dkMU Also unordered map best and average case O(1), worst case O(N), looks like no worst case is there for collision

[@gowthamarun43]

@@takeUforward thanks for that bro👍

[@rabatoaa857]

12:23 C++ Solution