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
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.
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)
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
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 🫂
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
#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.....
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
the better solution was not working on coding ninja so i just want to update the code and show the code which was working! int longestSuccessiveElements(vector&a) { if (a.empty()) { return 0; // Return 0 for an empty vector } std::sort(a.begin(), a.end()); int n = a.size(); int longest = 1; int count = 1; for (int i = 1; i < n; i++) { if (a[i] == a[i - 1] + 1) { count++; } else if (a[i] != a[i - 1]) { count = 1; } // Update the longest length longest = std::max(longest, count); } return longest; }
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.
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)
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.🙂
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
My approach for better solution :- #include using namespace std; int main() { vector v = {100,5,100,101,101,4,3,2,3,2,1,1,1,2}; int n = v.size(); sort(v.begin(),v.end()); int longest = 1; int length = 1; for(int i =0; i 1 + v[i]) //if consecutive diff > 1 then reset count to 1 { length = 1; } } cout
Best better solution with edge cases:- O(nlogn)+O(n) class Solution { public: int longestConsecutive(vector& nums) { int n = nums.size(); int count = 1; int maxx = 1;
if (n == 0) return 0;
sort(nums.begin(), nums.end());
for (int i = 1; i < n; i++) { if (nums[i] == nums[i-1] + 1) { count++; maxx = max(count, maxx); } else if (nums[i-1] == nums[i]) { continue; } else { maxx = max(count, maxx); count = 1; } }
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
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.
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
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 ........
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
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
Please watch our new video on the same topic: ua-cam.com/video/oO5uLE7EUlM/v-deo.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
@9:45 It was like Raj is showing middle finger to us😂.
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
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
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?
Literally the best content available in youtube , it really beats paid content.
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
** 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
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
Finally found the explanation of the while loop time complexity. Thanks!
Whenever your heart is broken don't ever forget you're golden💯
correction 13:44 hashset in java also doesn't order elements
Correct
Amazing work.... I will complete the whole series....
when I saw this video update today, I was like what, wasn't it uploaded yesterday 😂
i think the complexity for the first brute force would be O(n^3)
Yes you are correct
agree
i directly got better approach in mind
Understood! Awesome explanation as always, thank you very very much for your effort!!
Understood. Amazing. Keep going mate.
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 😭
You understood brutforce and better very well but i do not understtod optimal
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
Nice observation!
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 🧐
@@RajeevCanDev It will run in the loop even though it is user defined function and hence TC boils down to N^3
@@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
@@RajeevCanDev idk about that but the approach he mentioned is O(N^3)
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.....
Say that again, after you discover something called “TUF+”
In my opinion, the time complexity for the brute force solution would be O(n^3)
If I can not be the part of the sequence then I will be the new sequence.
awesome videos, but one correction like in brute force approach the time complexity should be o(n^3) , rest everything is perfect.
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
brute force solution t.c : O(N^3) ?
No bro
Why not @@tarunrajput6865
Great Explanation
You might be the GOAT of DSA
understood 🎯
Life Changing 💕💕
Understood🎉
40 lakh
the better solution was not working on coding ninja so i just want to update the code and show the code which was working!
int longestSuccessiveElements(vector&a) {
if (a.empty()) {
return 0; // Return 0 for an empty vector
}
std::sort(a.begin(), a.end());
int n = a.size();
int longest = 1;
int count = 1;
for (int i = 1; i < n; i++) {
if (a[i] == a[i - 1] + 1) {
count++;
} else if (a[i] != a[i - 1]) {
count = 1;
}
// Update the longest length
longest = std::max(longest, count);
}
return longest;
}
Your video is very helpful for everyone, thank you ❤
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
bro it should be i
I think this solution will never come in mind of someone who didn't seen this type of problem.
this is GOD level man!! Thank you!!
Amazing explanation❤️
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 ❤
us, really a good one in TC Explain
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.
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.
Very well explained, brother. Thank you
Fantastic Explaination..!
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)
@15:53 worst case time complexity of find operation in unordered_set is O(N) and average case is of O(1).
How the optimal solution is optimal, still taking O(n^2) and better solution takes only O(nlogn). Can anyone please explain this.
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.🙂
Kinda true only for this array
sir what do you mean when you say collision happens??? can you explain with example....
Understood, thank you.
Understood. Thanks a lot
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)..?
please write the ode for 1st and 2nd method also in coming videos
Solution using map :
class Solution {
public:
int longestConsecutive(vector& nums) {
int n=nums.size();
int cnt=0,longest=0;
map mpp;
for(int i=0;i
understood
This same video was uploaded yesterday also
Nd then deleted
Understood Bhaiya!
My approach for better solution :-
#include
using namespace std;
int main()
{
vector v = {100,5,100,101,101,4,3,2,3,2,1,1,1,2};
int n = v.size();
sort(v.begin(),v.end());
int longest = 1;
int length = 1;
for(int i =0; i 1 + v[i]) //if consecutive diff > 1 then reset count to 1
{
length = 1;
}
}
cout
Happy teacher's day striver ,
Today is 5 th sep and i am watching this one
Understood. thank you
Understood!
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
can you explain me bro why we using " == st.end() " and " != st.end()" ...... he used in many problems but i don't understood......
very nice problem sir understood very nicely sir......
i have solve this question from striver hash playlist still i am watching this video.
understood
please came with String playlist sir
understood sir
I think the brute force complexity is o(N^3).
Best better solution with edge cases:- O(nlogn)+O(n)
class Solution {
public:
int longestConsecutive(vector& nums) {
int n = nums.size();
int count = 1;
int maxx = 1;
if (n == 0) return 0;
sort(nums.begin(), nums.end());
for (int i = 1; i < n; i++) {
if (nums[i] == nums[i-1] + 1) {
count++;
maxx = max(count, maxx);
} else if (nums[i-1] == nums[i]) {
continue;
} else {
maxx = max(count, maxx);
count = 1;
}
}
return maxx;
}
};
as usual, awesome
Understood🔥
Understood ❤️
if(striver(Raj sir) == legend ) ans ="true";
else ans = "Yes Striver(Raj sir) is LEGEND";
Please, please, please if you find this video useful. Like. It is just a click away
Understood, thanks :)
Understood! Sir
Understood✅🔥🔥
This is O(N^2) solution, better to sort the array. '
Edge cases are the worst nightmares of coders.
Can anyone explain if(st.find(it-1)==st.end()) && if(st.find(x+1)!=st.end())
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
Understood!!🙇♂
Understood
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
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.
Understand
Understood Bhai
Understood Sir!
Understood❤️🔥
When you write code in editor make sure to zoom in
Understood 💯💯💯
Thanks Brother
understood❤
We can even do last one with O(n) with even worst case
Understood !!
Thank you
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
I understood this problem.
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 ........
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
you are missing if condition, if 107 is not the starting element then while won't run
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
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