Please watch the new video which covers it in more depth, and also prints it: th-cam.com/video/oO5uLE7EUlM/w-d-xo.html 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
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)
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
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.
@@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.
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
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)
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
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.
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.
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.
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))
@@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.
@@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.
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)
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.
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 ....
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)
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.
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
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
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
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;
There have been many comments on TH-cam 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....
@@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 .😂
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; }
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?
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).
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
@@jaynilgaglani9480 You could refer to my code explanation also. leetcode.com/problems/longest-consecutive-sequence/discuss/789257/Easy-Java-Solution-with-Explanation-O(N)
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
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();
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++);;
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)
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)?
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?
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.
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 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
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
@@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.
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);
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?
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
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.
@@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 !!
@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)
@@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
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 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 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.
for directly iterating we need to sort the array & it takes o(nlog) +o(n)to sort . by doing this we are getting o(n)+o(n)+o(n) which is o(n) finally But may be o(nlog) +o(n) would take less time than this .
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).
Please watch the new video which covers it in more depth, and also prints it: th-cam.com/video/oO5uLE7EUlM/w-d-xo.html
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
@RAJVEER Singh video release hua hi nai h XD
sir please create internship roadmap for people who have wasted first year i.e have 1 year left
yuppppppppppppppp!
ek baar me hi smjh aa gaya dono approach....awesome bro....thanks!
yes
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
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)
This is a really good point, Thanks!
Agreed. On Leetcode just this small change made it much more faster.
Valid Point
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
@@rishavgupta7868 Use unordered set.
It will give tle on leetcode. Use this instead
int longestConsecutive(vector& nums) {
unordered_set s;
for(int i=0;i
Thank u ❤
bro i did get tle but idk why ??? can you tell why it gives tle
@@shikharmalik3787 The time complexity will be O(n^2). So TLE
i used unordered map instead of set, it runs but is very slow compared to set, why?
after watching the intution i have coded it myself, way of your teaching is magic. i am feeling the improvment. Thanks a lot
The hashset solution is actually slower in practice than the sorting one
sorting one takes around 15 ms on avg but the set one is takinh 800+ ms
@@sourin.majumdar exactly its O(n2) actually
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.
@@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.
If you are getting TLE, just declare it as unoredered_set it will pass
Bhai it really worked....but what's the reason behind this?
Bhai it really worked....but what's the reason behind this?
@@kartiksuman9814 Accessing element is faster in unordered set , costs O(1), but in orderd set, its O(log n)
Okay... thankyou
@@kartiksuman9814 tc of set is O(nlog) because it sorts the elements, but for unordered_set, its O(n)
After striver posted this video, the difficulty of this question got reduced to medium. Power of striver.
its actually just a simple application of hash sets, shouldn't it be easy
@@mannthakkar the concept is easy but the implementation is a lil bit tricky
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
thanks bro
could you also tell what to correct in the 4sum problem,it is giving runtime error
thank you so much buddy, it works now
@@yatin3699 Inside the second loop (j loop), for calculating target2 use "long long" instead of using "int", this will solve the issue.
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
Deciding at the last that time complexity of given solution is actually ~O(n) was really challenging. Thanks Striver for this explanation.
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)
but we are using set..so it will eliminate duplicate elements
sets doesnt contain duplicate values
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
@@VishalGupta-xw2rp even if array contains, duplicate elements, the order won't change to O(N2).
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.
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.
how is this useful in this problem? i didnt understand
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
🤣
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)
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.
Bhai I am not getting brute force approach can you tell me???
@@Yash_Parashar brute force ...if you are sorting a vector ...it will take n logn
maze aa gaye. after knowing the approach its difficult to believe that this question comes under hard category. Thank you striver really missed you.
Now Leetcode moved this question into "Medium" category😅
@@venkateshn9884 xd
if u r getting error use this simple solve -- sets;
for(int i=0;i
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))
Same ques here
We are inserting in unordered_set or hashset which has insertion complexity of O(1).
Inserting into a hashset takes constant time complexity O(1)
@@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.
@@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.
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
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.
Glad it was helpful!
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 ....
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;
Thats what i call a brilliant explanation 🙏
finally... ! cant ask for more, but good and more helpful if we get atleast two videos on the series.
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++
yes he told hash set ,so it is same as unordered set.
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)
UNDERSTOOD...!!!
Thanks, striver for the video... :)
Nice explanation Striver bhaia .. thanks for making this series .. each and every question helps me to get more better in data structures 😍
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.
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
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
haan bhai XOR ka efficient solution ka video jaldi bro
+1 on XOR video
"Count number of subarrays with given XOR" referring to this I think? Yeah I'd like a video for that
XOR question on Day 4 was supposed to clear problems not create more... XD Help would be appreciated
xor video nikalo bro jaldi waiting for it
the explanation is great
Literally you are doing great ✌
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
complexity will still be o(nlogn) although the soln will be accepted since set uses o(nlogn) for storing n elements.
I'm still confused why Time complexity is O(3N), isn't it O(N) +O(N*N) ???
Yes I am confused too.
yes ur right that will be in the cases of duplicate elements, iterate over the hashset instead of the array to avoid that
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;
so smooth and crystal clear explanation.
Clement's girlfriend has started haunting me now .
@code fire i dont understand
There have been many comments on TH-cam 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....
@@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 .😂
@@narc7885 get adblocker for youtube kid!
Don't stalk my future wife😂😉@saurav dhar
absolutely loved the intuition
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;
}
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?
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?
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).
Superb explanation 🔥
The explanation is really great
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
after watching this video, leetcode set this questions difficulty to medium.
I think you used set instead of unordered_set in the c++ solution ......btw awesome video
yeah it might have been, you can tell that to the interviewer does not matters that most.
yaa that will make the overall time complexity (nlogn)
Can you also talk more about the intuition behind the approaches used for solving this problem?
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!
@@takeUforward Oh, Yeah! Got it.
@@jaynilgaglani9480 You could refer to my code explanation also.
leetcode.com/problems/longest-consecutive-sequence/discuss/789257/Easy-Java-Solution-with-Explanation-O(N)
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)
Thanks Bhai!! understood the algorithm and solved in a jiffy
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
What a simple approach it is but my tiny brain couldn't think about it 😭😭
Thank you for explaining the time complexity, why Time Complexity = O(n) is real key
Very nice videos.... Really appreciable
At the time of video, this was a hard problem..... And now it came down to Medium... Striver's effect 😎
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
Brilliant explanation!
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++);;
Thank you sooooooo much bro!
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)
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++!
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)?
Getting TLE on leetcode if we use set but not with unordered_set.can anyone explain why?
Because set works in O(logN) complexity, unordered_set in O(N)
Wonderful Bhaiyaa.. Pls iska union-find wala soln pe bhi thoda insight dedo
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?
Checkout the last example explained !
Great vid as always
❤️ great examplanation
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.
Thnku so much bhaiyaa 💖💖💖
int longestConsecutive(vector& nums) {
unordered_set st;
int n = nums.size();
for(int i=0;i
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
No, try to do it properly, i have showed an example in the explanation
@@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
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
how can this test case have a output of 3: [1,2,0,1]
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
set(which is ordered ) is implemented from bst and unordered set is just a hash table same with map and unordered_map
@@jaydave2500 thanks for info
JAVA Solution = 10:52
C++ Solution = 12:21
it's lead to time limit exceeded problem while running on leetcode.
Nah, use the exact code as mine. Don’t do modifications!
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)
Unordered set average case me O(1) me chal jaata. But the worst case of unordered is o(N)..
@@takeUforward Thank you Bhaiya for clarification :)
awesome explanation !!!😍
Search time complexity is O(logn) and i think you solution is of O(nlogn) using map of C++.
unordered map takes o(1) in average that has been taken into consideration
@@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.
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
the best explanation ever! thank you
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;
}
Amazing. Thank you Bhaiya
@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;
}'
Asked by interviewer today 🙏
how is the brute force solution faster than 75% of submissions on leetcode while the optimized is only 5%
you explain really well. thankyou;
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?
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
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.
Yes, just mention this in the interview it will work!
Where is unordered_map used? I can see only set. And how can we use bool array instead. Please reply.
@@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 !!
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;
}
@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)
Nah, count the iterations the inner loop does not always runs for N time, observe carefully..
@@takeUforward sir I had the same query .thanks for answering it 👏👏👏👏
@@takeUforward How do you say that? Even the inner while loop run m times (m
@@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
Will it work if numbers in array are repeated??
yes ..set only keep unique elements.
doesn't set have logn complexity for insertion and access(c++ code)?
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?
No it won't make, watch the entire video! And count iterations while doing dry run!
@@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.
@@rahulrawat4265 but it will wont run n^2 times, think on it properly!
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.
@@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.
good work bro... HAPPY!!
wouldn't the time complexity be in nlogn (in C++)?
The insert() function takes logn to insert the element
and in leetcode, there is a huge difference in time taken, the sorting is taking time around 150ms, whereas the HashSet is taking more than 2000 ms
Solved it yesterday using hasmap
Why aren't you directly iterating on the set?
for directly iterating we need to sort the array & it takes o(nlog) +o(n)to sort .
by doing this we are getting o(n)+o(n)+o(n) which is o(n) finally
But may be o(nlog) +o(n) would take less time than this .
@@pruthvirajjadhav3853 set is already in sorted order
@@hardikagarwal7652 check here 0:08
@@pruthvirajjadhav1996 when we store elements in the set then they are sorted
Nice explanation!!
Just one doubt , doesn't inserting n elements in a set takes nlogn time.
Please correct me if I am wrong.
set take O(logn) to one element , so than it use unordered_Set inplace of set
set takes O(logn) time
@@ushnispanja7121 yes bro
@@SharvanKumar-ui1kw worst case searching time will be O(n^2) in case of unordered_map and unordered_set.
In gfg, a solution with priority queue is also there. What if the interviewer asks me to discuss that approach too?
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).
class Solution {
public int longestConsecutive(int[] nums) {
if(nums.length==0) return 0;
Setset =new HashSet();
for(int i: nums) set.add(i);
int count =1;
for(int i=0; i
Why brute force approach is faster than set method on leetcode runtime?
Leetcode's runtime feature is not reliable, try sort 0's, 1's and 2's problem..