this is what I wrote before looking at better approach const findLongestConsecutiveLength = (arr) => { let longest_consecutive = 1; let max_longest_consecutive = 1; let last_item = arr[0]; for (let i = 1; i 1) { longest_consecutive = 1; last_item = arr[i]; } } return max_longest_consecutive; };
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 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
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 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
Initial State: lastSmaller starts with INT_MIN, an extremely small value that will be replaced with the first element of the array once we begin processing. First Condition (if (a[i] - 1 == lastSmaller)): This condition checks if the current element a[i] is exactly one greater than lastSmaller, meaning it is the next element in a consecutive sequence. If this is true, the current element a[i] is part of the current consecutive sequence, so cnt is incremented to count this element, and lastSmaller is updated to a[i]. Second Condition (else if (a[i] != lastSmaller)): If a[i] is not consecutive to lastSmaller (i.e., a[i] is not equal to lastSmaller + 1), the code checks if it is different from lastSmaller. This condition avoids counting duplicates in the sorted array. If the element is different, it starts a new sequence with cnt reset to 1, and lastSmaller is updated to the current element a[i].
The Sorting based approach got me a better percentile at LC, not sure about the Set based one(why it got a lower). Thanks Striver as always, posting this just for refs
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
for (int i = 0; i < n; i++) { if (a[i] - 1 == lastSmaller) { cnt += 1; } cnt = 1; // This line now always resets `cnt` to 1 in every iteration lastSmaller = a[i]; longest = max(longest, cnt); } for those who are thinking what if we remove the else if statement but keep the code inside it in the loop, the code would look like above
#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.....
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.
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)
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
I TRIED MYSELF T.C = O(NlogN) and S.C = O(1) class Solution { public: int longestConsecutive(vector& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); int count =1; int maxCount = INT_MIN; if(nums.begin()==nums.end()) return 0; for(int i=0;i
st.end() refers to the position just after the last element in the set and st.find(x) does not finds the value then it will also return the position just after the last element in the set .
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
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
Hey Striver, I came up with this solution It takes only O(1) space to solve class Solution { public int longestConsecutive(int[] nums) { int n=nums.length; if(n
In the optimal approach, is there any way. we could remove the elements from the set after checking. For example when we check for 100, theres no element before it as it is the starting element. Can we remove 101 and 102 after counting it as the longest consecutive subsequence?
Can we do this question like , firstly hashing the array by first finding size of hash array and then hashing it and then checking whether the hash number is zero or not for the consecutive ones and then counting the number of non zero hash numbers and storing the max count , will this be a better solution?
lastsmaller at the very first would confuse but just think like these on the very first step it will get over right by the very first element of your array cause its not equal just dont get confuse guys
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
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
Isn't the TC just O(N) for the better approach where we sort the array ? since we are not sorting and iterating in the same look the Time Complexity will be O(log(n)) for sorting and O(N) for iteration to determine the max sequence length. With O(N) dominating O(log(n)) due to beign higher thus resulting in TC of O(N) ?
Hello everyone... I have a doubt in brute force solution which is given in the video. Please help me if anyone understand my doubt. For test case: 5,8,3,2,1,4 The longest subsequence will be 1,2,3,4,5 (len=5) But according to brute force solution when my i=4 ,it is pointing to the 1 in first for loop in second for loop we are trying to find out the 2,3,4,5 from the starting .. firstly we try to find out the 2 and then three.. but in our in test case 2 comes after the 3 so the 3 will skip.. and we never got the correct solution... This is code int longestSuccessiveElements(vector&a) { int count=1; int maxcount=1; for(int i=0;i
A long comment but I have answered where you went wrong The brute force solution mentioned in the video has repeated searching of consecutive elements possible for an x. If x+1 has been found for an x we search for x+2 and x+3 and so on. What it means is that for a particular element (say x) picked up by the outer loop - for `i` in range(len(a)) [Bear with me for writing pythonic pseudocode], we look for `x+1` in the while(ls(arr,x+1)) part. Since it's a while loop, if `x+1` is found which leads to the true condition of while loop, the counter is incremented and (as linear search returns true), the x value has been increased to `x+1` i.e. the original value of x itself has been incremented. This is so because now the while loop would actually search for `x+1` (This x is the incremented x) which actually is `x+2` (Here x means original x we picked from the outer for loop). If again we find `x+2`, we look for `x+3` and so on. Do note that this brute force approach will have TC of O(n^3) as the linear search in while loop itself would take another O(n) and not O(n^2) The code you have written has the ability to pick an element `x` and only search for `x+1` as it has only two loops - the outer one picks the element x and the inner nested loop only looks for the `x+1`. Your code has no ability to look for `x+2` if it occurs before `x+1` as it has already been accessed by the inner loop and discarded. To actually search for `x+2` you need to go back and search once again. This code has only TC of O(n^2) and simply has no ability to repeatedly search for successive incremented x values which was achieved in the video's brute force solution by a while loop.
Hello, can you make a NEW playlist where you just code the java solutions of all these problems? we would get better understanding that reading the notes/codes directly and would have an easier time learning to code in java , you can attach those videos individually or just make a separate playlist and we will automatically go to that and see the java code after we are done understanding the algorithm
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.🙂
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.
Please watch our new video on the same topic: th-cam.com/video/oO5uLE7EUlM/w-d-xo.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 is what I wrote before looking at better approach
const findLongestConsecutiveLength = (arr) => {
let longest_consecutive = 1;
let max_longest_consecutive = 1;
let last_item = arr[0];
for (let i = 1; i 1) {
longest_consecutive = 1;
last_item = arr[i];
}
}
return max_longest_consecutive;
};
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!!
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?
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
@@sandipan_c
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
** 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
Literally the best content available in youtube , it really beats paid content.
Let's march ahead, and create an unmatchable DSA course! ❤
Use the problem links in the description.
Idk why did you upload this video again but if you did just because better solution had edge case of multiple duplicate elements then hats off to you man ❤ even though it was negligible mistake still you re-recorded that part and uploaded video again I really appreciate your efforts 🫂
Yess that was the reason
Understood
Thank you brother for this DSA 💥💥course
I 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
dont confuse guys when solving this just do else if (a[i] == a[i-1]) {
continue;
} to handle duplicate edge cases
Finally found the explanation of the while loop time complexity. Thanks!
Whenever your heart is broken don't ever forget you're golden💯
You understood brutforce and better very well but i do not understtod optimal
correction 13:44 hashset in java also doesn't order elements
Correct
+1
Initial State:
lastSmaller starts with INT_MIN, an extremely small value that will be replaced with the first element of the array once we begin processing.
First Condition (if (a[i] - 1 == lastSmaller)):
This condition checks if the current element a[i] is exactly one greater than lastSmaller, meaning it is the next element in a consecutive sequence.
If this is true, the current element a[i] is part of the current consecutive sequence, so cnt is incremented to count this element, and lastSmaller is updated to a[i].
Second Condition (else if (a[i] != lastSmaller)):
If a[i] is not consecutive to lastSmaller (i.e., a[i] is not equal to lastSmaller + 1), the code checks if it is different from lastSmaller. This condition avoids counting duplicates in the sorted array.
If the element is different, it starts a new sequence with cnt reset to 1, and lastSmaller is updated to the current element a[i].
Thank you soo much dude you really helped me where I was stuck !!!
The Sorting based approach got me a better percentile at LC, not sure about the Set based one(why it got a lower). Thanks Striver as always, posting this just for refs
Excellent course no one covered like this best way to teaching 🥰🤩
when I saw this video update today, I was like what, wasn't it uploaded yesterday 😂
@15:53 worst case time complexity of find operation in unordered_set is O(N) and average case is of O(1).
Understood! Awesome explanation as always, thank you very very much for your effort!!
Amazing work.... I will complete the whole series....
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
Thank you striver , Very well explained and Time complexity part was amazing.
Understood. Amazing. Keep going mate.
You might be the GOAT of DSA
for (int i = 0; i < n; i++) {
if (a[i] - 1 == lastSmaller) {
cnt += 1;
}
cnt = 1; // This line now always resets `cnt` to 1 in every iteration
lastSmaller = a[i];
longest = max(longest, cnt);
}
for those who are thinking what if we remove the else if statement but keep the code inside it in the loop, the code would look like above
#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+”
Understood🎉
40 lakh
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.
awesome videos, but one correction like in brute force approach the time complexity should be o(n^3) , rest everything is perfect.
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 😭
this is GOD level man!! Thank you!!
you are the GOAT. thank you
i directly got better approach in mind
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)
Your video is very helpful for everyone, thank you ❤
thanku so much striver ji ...loads of love
i think the complexity for the first brute force would be O(n^3)
Yes you are correct
agree
understood, thanks for the perfect explanation
Very well explained, brother. Thank you
Great Explanation
sir what do you mean when you say collision happens??? can you explain with example....
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)
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......
In my opinion, the time complexity for the brute force solution would be O(n^3)
Amazing content ❤🔥
I TRIED MYSELF T.C = O(NlogN) and S.C = O(1) class Solution {
public:
int longestConsecutive(vector& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int count =1;
int maxCount = INT_MIN;
if(nums.begin()==nums.end()) return 0;
for(int i=0;i
well explanaation bro it helps me lotttttttttttttttttttttt
Great one !! ❤
plese any one can help me on optimal solution
if(st.find(it-1)==st.end());
19:31 how this condtion will execute
st.end() refers to the position just after the last element in the set and st.find(x) does not finds the value then it will also return the position just after the last element in the set .
How the optimal solution is optimal, still taking O(n^2) and better solution takes only O(nlogn). Can anyone please explain this.
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
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)..?
Life Changing 💕💕
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
Hey Striver, I came up with this solution
It takes only O(1) space to solve
class Solution {
public int longestConsecutive(int[] nums) {
int n=nums.length;
if(n
us, really a good one in TC Explain
i also thinks that the time complexity of brute could be best expressed as O(n raised to 3) in the worst case.Please respond.
brute force solution t.c : O(N^3) ?
No bro
Why not @@tarunrajput6865
Understood ❤
In the optimal approach, is there any way. we could remove the elements from the set after checking. For example when we check for 100, theres no element before it as it is the starting element. Can we remove 101 and 102 after counting it as the longest consecutive subsequence?
Fantastic Explaination..!
Can we do this question like , firstly hashing the array by first finding size of hash array and then hashing it and then checking whether the hash number is zero or not for the consecutive ones and then counting the number of non zero hash numbers and storing the max count , will this be a better solution?
No, you can't. This would throw a time complexity error in my opinion as when the number is very large such large size of array is not possible.
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
understood 🎯
lastsmaller at the very first would confuse but just think like these on the very first step it will get over right by the very first element of your array cause its not equal just dont get confuse guys
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
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.
Can we not make it easy by using Sorted Set in java ?
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
Happy teacher's day striver ,
Today is 5 th sep and i am watching this one
But we could solve this question with time complexity o(n square logn) first we sort the array and then travel through the each element of the array
understood striver , thank you
Isn't the TC just O(N) for the better approach where we sort the array ? since we are not sorting and iterating in the same look the Time Complexity will be O(log(n)) for sorting and O(N) for iteration to determine the max sequence length. With O(N) dominating O(log(n)) due to beign higher thus resulting in TC of O(N) ?
O(nlogn) for sorting bro, nobody can sort in O(logn), so the overall TC will be O(nlogn)
Thank ❤❤ you
very nice problem sir understood very nicely sir......
Understood. Thanks a lot
Hello everyone...
I have a doubt in brute force solution which is given in the video. Please help me if anyone understand my doubt.
For test case:
5,8,3,2,1,4
The longest subsequence will be 1,2,3,4,5 (len=5)
But according to brute force solution when my i=4 ,it is pointing to the 1 in first for loop
in second for loop we are trying to find out the 2,3,4,5 from the starting ..
firstly we try to find out the 2 and then three.. but in our in test case 2 comes after the 3 so the 3 will skip.. and we never got the correct solution...
This is code
int longestSuccessiveElements(vector&a) {
int count=1;
int maxcount=1;
for(int i=0;i
A long comment but I have answered where you went wrong
The brute force solution mentioned in the video has repeated searching of consecutive elements possible for an x. If x+1 has been found for an x we search for x+2 and x+3 and so on. What it means is that for a particular element (say x) picked up by the outer loop - for `i` in range(len(a)) [Bear with me for writing pythonic pseudocode], we look for `x+1` in the while(ls(arr,x+1)) part. Since it's a while loop, if `x+1` is found which leads to the true condition of while loop, the counter is incremented and (as linear search returns true), the x value has been increased to `x+1` i.e. the original value of x itself has been incremented. This is so because now the while loop would actually search for `x+1` (This x is the incremented x) which actually is `x+2` (Here x means original x we picked from the outer for loop). If again we find `x+2`, we look for `x+3` and so on. Do note that this brute force approach will have TC of O(n^3) as the linear search in while loop itself would take another O(n) and not O(n^2)
The code you have written has the ability to pick an element `x` and only search for `x+1` as it has only two loops - the outer one picks the element x and the inner nested loop only looks for the `x+1`. Your code has no ability to look for `x+2` if it occurs before `x+1` as it has already been accessed by the inner loop and discarded. To actually search for `x+2` you need to go back and search once again. This code has only TC of O(n^2) and simply has no ability to repeatedly search for successive incremented x values which was achieved in the video's brute force solution by a while loop.
@@hetanshumalik6778 Thank u so much
Understood Bhaiya!
Can we do it using map to get O(N) complexity?
I think the better one is most optimal.
finding from set every time, doesn't make it so much slow?
Hello, can you make a NEW playlist where you just code the java solutions of all these problems? we would get better understanding that reading the notes/codes directly and would have an easier time learning to code in java , you can attach those videos individually or just make a separate playlist and we will automatically go to that and see the java code after we are done understanding the algorithm
understood
please came with String playlist sir
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
Can anyone pls explain me what is set.end() is representing here ? Im not able to get the condition in while loop .
in better approach,wont be else condition would be else if(arr[i]-1!=lastsmaller)??
Understood✅🔥🔥
set already stores in sorted and unique mannaer right?
Hello sir,
I had a doubt that using set(ordered) just takes o(logN) know????
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.
bhaiya yha pr aapne for each loop me while loop lagaya hai yha time complexity O(n*n) nhi hoggi ?
Understood, thank you.
for the set solution. why he is not considering complexity of set.find() which is O(logn) ?
because it's converted into O(1) after some operations
Insertion in set is logn...so for n elements, isnt it o(nlogn) tc??
That's rare in most is o(1)
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
code 360 not show some of the code which i was done before, can anyone tell about this ?
Brute force will be O(N^3) isn't it. Assume we are given a sorted array with all consecutive integers.
please write the ode for 1st and 2nd method also in coming videos