Its all love, love, and love 💖💖💖💖💖💖💖💖💖. I have never seen ur full video but, still able to solve problems. Do you know what does this means? It means that you are a great teacher and you explain things so simply. I just love it. Thank You 3000
I was learning dsa in java and struggling in a hasmap . But after watching this video now able to solve the many problem using hashing. THANK YOU SO MUCH SIR...❤
Thanks sir. Bahut accha kaam karte hai aap. The way with which you present your explanations and give sound logic for each is something which you only possess.
Thank you for appreciating. and I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem. If you like our efforts, we request a review g.page/Pepcoding/review?rc You can subscribe to our channel here ua-cam.com/users/Pepcodingabout?view_as=subscriber
Wow man! This problem looked very complicated at first but as you explain it - It just kept getting easier. Every single concept taught by you is unforgettable -
Here is another solution using which has less time complexity: int ans = 1; HashSet hashSet = new HashSet(); for (int num: nums) { // nums is the array hashSet.add(num); } for (int val: hashSet) { //Looping through hashSet if (!hashSet.contains(val-1)) { int maxStreak = 1; while (hashSet.contains(val+1)) { maxStreak++; val++; } ans = Math.max(ans, maxStreak); } } return ans;
Sir in worst case I think the third loop will not execute for exactly n times. It will execute for (2*n-1) times if there is only one consecutive sequence. For example [4,5,7,6,8,9,10] -> 7 times for loop will get executed for each element of array...and 6 times inner while loop will get executed for array element 4. Although it will not make any difference overall TC will remain O(n) but i just want to confirm that what I am thinking is correct or not. Sir your teaching method is very good after seeing your lectures all concepts gets crystal clear. ThankYou for such wonderful content.
Glad to know that you liked the content and thank you for appreciating. The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos. So, keep motivating, keep learning and keep loving Pepcoding😊
python code if someone needs: class Solution: def longestConsecutive(self, arr: List[int]) -> int: d = {} res = [] for i in arr: d[i]=True for i in d: if (i-1) in d: d[i] = False max_len = 0 max_start = 0 for i in d: if d[i] == True: temp_length = 1 temp_start = i while ((temp_length + temp_start) in d): temp_length+=1 if temp_length>max_len: max_start = temp_start max_len = temp_length for i in range(max_len): res.append(max_start+i)
awesome explanation.Just a small clarification.The consecutive sequence can be in any order is true but what if the consecutive sequence has duplicates like for the above example say [100,1,200,1,10,4,0,3,8,2].Here the consecutive sequence is [0,1,1,2,3,4] so i need to store the frequency also correct if input has duplicates?
if the question says to store duplicates too ,then just use the same logic for sequence , for every number in the answer seq , if it is repeating then print freq no. of times
Thankyou beta! I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem. If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
Bahar wali loop chali n baar agar each element ke liye andar wali loop n baar chalti to n*n hoti but yahan har ek element ke liye nahi totally he loop n baar chalegi that is considered as o(n),hope that makes sense
Although the time complexity appears to be quadratic due to the while loop nested within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums), the while loop can only run for nn iterations throughout the entire runtime of the algorithm. This means that despite looking like O(n \cdot n)O(n⋅n) complexity, the nested loops actually run in O(n + n) = O(n)O(n+n)=O(n) time. All other computations occur in constant time, so the overall runtime is linear.
// CPP AC code #include using namespace std; void printUsingHashMap(vector &arr){ int n = arr.size(); unordered_map m; // m[element] == true, so element is the starting point of the sequence // initialization for(auto e: arr){ m[e] = true; } for(auto element : m) if(m.find(element.first-1)!=m.end() && m[element.first-1]) element.second =false;
// now all those keys which are true, are starting points of consecutive sequence int maxm_length=INT_MIN; int start;
for(auto element: m){ if(element.second==true){ int length = 1; int i = element.first; while(m.find(i+1)!=m.end()) i++,length++;
even aapne loop ke andr loop use kiya hai atleast wo element ko check krega ki next wala hai ya nhi hai to map me ksi bhi element ko search krne me hi o(log n) complexity lagti hai to n kaise hui??
duplicate ke liye compute hoga, but it's length will be atmost = not > maxSequenceLen, thus, it won't be printed twice only computed twice. And even the computation can be ignored if at the end of first computation you make it false in hm. Dry run karo with a test case that contains duplicate start points, clear ho jayega. Mujhe bhi same doubt tha.
Sir at 14:12 you said "while ne 'n' times contribute kiya". Then in for loop isn't time complexity will become n*n (n for for loop and n for while loop)?
S.end() actually indicates the end of the hashmap, it returns an iterator pointing to the location next to the last element of hashmap. S.find(arr[i] - 1) == S.end() this statement means you have checked the entire map and didn't find the element hence, reached the end of it .
Basically last me jo sir ne loop lgaya hai for loop me usme while loop total n bar chelega her element ke liye kuch kuch chlega lekin total n bar chelgea bas o(n) hi ho ha
Wo to mjhe bhi PTA hai par complexity always find in wrost case , so agar elements agar sequence me ho 1 upto n ho aur saare sequence me to so in that case toh n^2 hogi. Bcz elements to hm kuch bhi daal skte na ?? Mai is case me phuchi hu? Like Consider the case when values in a are a sequence from 1 to n... 1,2,3...n then in that case complexity will n^2
You're welcome If you like my efforts, I request a review g.page/Pepcoding/review?rc You can subscribe to our channel here ua-cam.com/users/Pepcodingabout?view_as=subscriber For clearing your doubts, you can join our community on telegram t.me/pepcoding
Sir, not able to understand, Why it is O(n). Since the outer loop will run n times and in worst case the inner loop will also run n times, so if i am not wrong it should be O(n*n). Please make one video to explain it's time complexity that how it is O(n).
@@anushkasharma4815 Outer loop runs n times but it doesn't do operations at each time... It just runs blindly... Which is not difficult for the compiler... Complexity is always for algorithmic operations. Let's say:- i == 1 ---> no operations i == 2 ---> no operations i == 3 ---> 3 operations i == 4 ---> no operations . . . i == n ---> 5 operations So, taking this problem into consideration... It does n operations in total
Although the time complexity appears to be quadratic due to the while loop nested within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums), the while loop can only run for nn iterations throughout the entire runtime of the algorithm. This means that despite looking like O(n \cdot n)O(n⋅n) complexity, the nested loops actually run in O(n + n) = O(n)O(n+n)=O(n) time. All other computations occur in constant time, so the overall runtime is linear.
@@chantelsopio5826 always we talk about worst case complexity and in worst case its not O(n) we dont care about best we care about worst and more worst complexity will less more our code will efficient
@@fashionvella730 as mentioned above I am talking about worst case here. You might want to Google to better understand this logic since it's fairly well known and even on LeetCode they've explained how it's O(N) since this particular logic confuses a lot of people.
hi i need ur assistance in doing the given problem kindly help me in this can i get ur official gmail id to get in touch with you for resolving my issue.
Sir, your teaching method is just like Irrfan Khan's acting.
It's just effortless.
You make look difficult problems look easy to solve.
Thank you.
Its all love, love, and love 💖💖💖💖💖💖💖💖💖.
I have never seen ur full video but, still able to solve problems. Do you know what does this means?
It means that you are a great teacher and you explain things so simply. I just love it.
Thank You 3000
You make explaination look very very easy thanks much appreciated
I was learning dsa in java and struggling in a hasmap . But after watching this video now able to solve the many problem using hashing.
THANK YOU SO MUCH SIR...❤
Sir u completes the definition of a teacher..🙇♀
Thanks sir. Bahut accha kaam karte hai aap. The way with which you present your explanations
and give sound logic for each is something which you only possess.
Thank you for appreciating. and I am glad you liked it. I also hope that you are watching till end and trying to understand the what, how and especially why of the problem.
If you like our efforts, we request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
ua-cam.com/users/Pepcodingabout?view_as=subscriber
@@Pepcoding I have already reviewed Pepcoding in the google maps and am already subscribed.
great teacher ever seen after 12th
The explanation for time complexity can't get better than this. Period.
for better experience why don't you use this same content on nados.pepcoding.com?
Wow man! This problem looked very complicated at first but as you explain it - It just kept getting easier. Every single concept taught by you is unforgettable -
your teaching method is best
made it way easy, thank u sir ❤️
Love From Kashmir 😍
Thanku PrabhuJi🙌🌸
Amazing sir👏👏.
The way of teaching is
so unique and very easy way.🙏🙏
Here is another solution using which has less time complexity:
int ans = 1;
HashSet hashSet = new HashSet();
for (int num: nums) { // nums is the array
hashSet.add(num);
}
for (int val: hashSet) { //Looping through hashSet
if (!hashSet.contains(val-1)) {
int maxStreak = 1;
while (hashSet.contains(val+1)) {
maxStreak++;
val++;
}
ans = Math.max(ans, maxStreak);
}
}
return ans;
Sir in worst case I think the third loop will not execute for exactly n times. It will execute for (2*n-1) times if there is only one consecutive sequence.
For example [4,5,7,6,8,9,10] -> 7 times for loop will get executed for each element of array...and 6 times inner while loop will get executed for array element 4.
Although it will not make any difference overall TC will remain O(n) but i just want to confirm that what I am thinking is correct or not.
Sir your teaching method is very good after seeing your lectures all concepts gets crystal clear.
ThankYou for such wonderful content.
good job sir , best explanation ever.
Glad to know that you liked the content and thank you for appreciating.
The love and respect which I get from you people keep me highly motivated and the same I am able to forward It to you people through my videos.
So, keep motivating, keep learning and keep loving Pepcoding😊
bhai aap great ho yaaar
python code if someone needs:
class Solution:
def longestConsecutive(self, arr: List[int]) -> int:
d = {}
res = []
for i in arr:
d[i]=True
for i in d:
if (i-1) in d:
d[i] = False
max_len = 0
max_start = 0
for i in d:
if d[i] == True:
temp_length = 1
temp_start = i
while ((temp_length + temp_start) in d):
temp_length+=1
if temp_length>max_len:
max_start = temp_start
max_len = temp_length
for i in range(max_len):
res.append(max_start+i)
return len(res)
Good Explanation!👌
Can we solve this using union find?
awesome explanation.Just a small clarification.The consecutive sequence can be in any order is true but what if the consecutive sequence has duplicates like for the above example say [100,1,200,1,10,4,0,3,8,2].Here the consecutive sequence is [0,1,1,2,3,4] so i need to store the frequency also correct if input has duplicates?
For doubt support use nados.pepcoding.com
if the question says to store duplicates too ,then just use the same logic for sequence , for every number in the answer seq , if it is repeating then print freq no. of times
great bhai
Awesome explanation sir
Thanks buddy!
Keep learning and keep growing!
Very nice explanantion, thanks sir!
Thankyou beta!
I am glad you liked it. I hope that you are watching till the end and trying to understand what, how, and especially why of the problem.
If you like our efforts, will you like to write a few words about us here (www.quora.com/What-are-the-good-websites-to-learn-data-structures-and-algorithms )
@@Pepcoding sure sir!! :)
Time complexity of this solution I think is: O(n*h) ; h = length of maximum consecutive sequence. Not O(n)
Any suggestions?
Bahar wali loop chali n baar agar each element ke liye andar wali loop n baar chalti to n*n hoti but yahan har ek element ke liye nahi totally he loop n baar chalegi that is considered as o(n),hope that makes sense
Aesa samjh lo jo false hain vo 0 baar chalenge or jo true hain usko milla ke hamesha n hoga
Although the time complexity appears to be quadratic due to the while loop nested within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums), the while loop can only run for nn iterations throughout the entire runtime of the algorithm. This means that despite looking like O(n \cdot n)O(n⋅n) complexity, the nested loops actually run in O(n + n) = O(n)O(n+n)=O(n) time. All other computations occur in constant time, so the overall runtime is linear.
// CPP AC code
#include
using namespace std;
void printUsingHashMap(vector &arr){
int n = arr.size();
unordered_map m; // m[element] == true, so element is the starting point of the sequence
// initialization
for(auto e: arr){
m[e] = true;
}
for(auto element : m)
if(m.find(element.first-1)!=m.end() && m[element.first-1])
element.second =false;
// now all those keys which are true, are starting points of consecutive sequence
int maxm_length=INT_MIN;
int start;
for(auto element: m){
if(element.second==true){
int length = 1;
int i = element.first;
while(m.find(i+1)!=m.end())
i++,length++;
if(length>maxm_length){
maxm_length = length;
start = element.first;
}
else if(length == maxm_length && element.first < start){
maxm_length = length;
start = element.first;
}
}
}
// printing the solution
for(int i = start; i
thanks buddy
Great 👍❤️❤️❤️😍😍💯❣️💢
wow explanation
Glad you liked it!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
even aapne loop ke andr loop use kiya hai atleast wo element ko check krega ki next wala hai ya nhi hai to map me ksi bhi element ko search krne me hi o(log n) complexity lagti hai to n kaise hui??
Map ki search O(1) hoti hai. logn hoti toh hum BST hi lete... hash banane ki jarurat hi nahi hoti
isme duplicate element cover nahi ho payenge sir. Sari element distinct is prerequisite I assume.
duplicate ke liye compute hoga, but it's length will be atmost = not > maxSequenceLen, thus, it won't be printed twice only computed twice. And even the computation can be ignored if at the end of first computation you make it false in hm. Dry run karo with a test case that contains duplicate start points, clear ho jayega. Mujhe bhi same doubt tha.
Sir at 14:12 you said "while ne 'n' times contribute kiya". Then in for loop isn't time complexity will become n*n (n for for loop and n for while loop)?
While ne over all loops n contribute kia all in all
Har baar n nahi contribute kia
@@Pepcoding Thank you sir, matlab each time n bar run hota while tabh n*n complexity hoti?
@@shubhamsood1406 ha
if (S.find(arr[i] - 1) == S.end())
In c++ it's S.end( )
Thus this S.end checks for only last element or entire set????
it means u have checked the entire set(and not found the element), reached the end of it .
S.end() actually indicates the end of the hashmap, it returns an iterator pointing to the location next to the last element of hashmap. S.find(arr[i] - 1) == S.end() this statement means you have checked the entire map and didn't find the element hence, reached the end of it .
sir map ka creation bhi to time complexity O(n * Log n) letta hai...
For better insight, visit nados.pepcoding.com, post your doubts, community will help you out there.
Sir leetcode par submit karne par 69/70 tc pass ho rhe hain. Ek test case main TLE aa rha hai
TLE aa rha hai because wo expected time se jyada time le rha hai
Sir can you explain O(n) iski complexity Kaise hogi
Basically last me jo sir ne loop lgaya hai for loop me usme while loop total n bar chelega her element ke liye kuch kuch chlega lekin total n bar chelgea bas o(n) hi ho ha
Wo to mjhe bhi PTA hai par complexity always find in wrost case , so agar elements agar sequence me ho 1 upto n ho aur saare sequence me to so in that case toh n^2 hogi. Bcz elements to hm kuch bhi daal skte na ?? Mai is case me phuchi hu? Like Consider the case when values in a are a sequence from 1 to n... 1,2,3...n then in that case complexity will n^2
@@sukanyasinha3583 I think sir can be clear you doubts
@@SCRIPTSAG ji
@@sukanyasinha3583 teligram joine Kiya hai sir ka
Thank you
You're welcome
If you like my efforts, I request a review
g.page/Pepcoding/review?rc
You can subscribe to our channel here
ua-cam.com/users/Pepcodingabout?view_as=subscriber
For clearing your doubts, you can join our community on telegram
t.me/pepcoding
@@Pepcoding done. You're doing a fantastic job.
Thankyou sir
You're welcome🙏
for loop ke andar while sir n kaise hua n*n hona chahiye worst case mein
Worst case mei bhi n hai. Ache se sochie. For mei while hote hue bhi n hai. Total kitni baar chalega andar wala loop?
Sir, not able to understand, Why it is O(n). Since the outer loop will run n times and in worst case the inner loop will also run n times, so if i am not wrong it should be O(n*n).
Please make one video to explain it's time complexity that how it is O(n).
@@anushkasharma4815 Outer loop runs n times but it doesn't do operations at each time...
It just runs blindly... Which is not difficult for the compiler... Complexity is always for algorithmic operations.
Let's say:-
i == 1 ---> no operations
i == 2 ---> no operations
i == 3 ---> 3 operations
i == 4 ---> no operations
.
.
.
i == n ---> 5 operations
So, taking this problem into consideration... It does n operations in total
@@hymnish_you u mean that if a simple for loop which is running till arr.length and not doing any operation won't have a complexity of size of array?
@@crackthecode1372 yeah
OP sir
thank you beta
iski time complexity kaafi kharab h leetcode me submit karne pe 255 ms dikha rha h
leetcode ke run-time par jaya karo bro! wo most optimal soln ko bhi 20% faster batata hai
its not O(n)
Although the time complexity appears to be quadratic due to the while loop nested within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums), the while loop can only run for nn iterations throughout the entire runtime of the algorithm. This means that despite looking like O(n \cdot n)O(n⋅n) complexity, the nested loops actually run in O(n + n) = O(n)O(n+n)=O(n) time. All other computations occur in constant time, so the overall runtime is linear.
@@chantelsopio5826 always we talk about worst case complexity and in worst case its not O(n) we dont care about best we care about worst and more worst complexity will less more our code will efficient
@@fashionvella730 as mentioned above I am talking about worst case here. You might want to Google to better understand this logic since it's fairly well known and even on LeetCode they've explained how it's O(N) since this particular logic confuses a lot of people.
hi i need ur assistance in doing the given problem kindly help me in this can i get ur official gmail id to get in touch with you for resolving my issue.
Great explanation sir.
thank you