For the approach using optimization by sorting, one edge case to solve for would be repeated numbers. For example, take [1, 2, 0, 1] as input. After sorting it would be [0, 1, 1, 2]. So finding longest sequence, the right answer is [0, 1, 2], but your approach would take [0, 1] or [1, 2] as the final answer. Am curious to know how to handle this case with the sorting approach.
One question Nikhil sir. Where have me marked the first visited elem as true as mentioned in the video at 14:48 ? Am I missing something or its a typo. Btw thanks a lot for this beautiful explanation.
you can make it more efficient by adding: if (longestLength > nums.length / 2) { return longestLength; } to the end of every iteration, this will check if we have a longestLength that is bigger that 1/2 array
This is nice too! I love Java. numSet = set(nums) # remove repetition longest = 0 for n in nums: # check if n is the start of a sequence # that is, if left neighbour does not exist, then it is the start of a sequence if (n-1) not in numSet: # if it is, check for consecutive sequence length = 0 while (n + length) in numSet: # if right neighbour exist, keep increasing the length length += 1 longest = max(longest, length) return longest
Hello Nikhil sir, I tried both the sorting approach and the HashMap approach on leetcode. Why does using the map take more time than the sorting approach, even though it is O(n) compared to O(NlogN)? Using sorting - 16ms Using hashmap - 47ms
bro don't rely on runtime of leetcode, it will differ every time you submit a code, even the same code may give you different runtime if submitted again and again. That's why we use big O notations to summarize the efficiency.
Thanks for de explanation, it was very clear and helpful. I have just one question... Why does the solution with map work without something like numberTravelledMap.put(num, Boolean.TRUE); at any moment?
what would happen if we did't check whether it had been explored or not? just this part was a little bit confusing for me, but overall great explanation
How is the the time-complexity of brute force is O(n^3)? Shouldn't it be O(n^6)? For example, if the array is [5, 1, 4, 3, 2, 6], then, if we start with 1, we need to traverse the array 5 times to get to the answer?
How is this O(n) with the nested while loop? Is it because this would technically be O(n * m) where n is the length of nums and m is the longest possible sequence, and m will always be less than or equal to n so it's negligible to O(n) ? Couldn't this be O(n^2) if all numbers in nums are sequential? Am I close or way off?
why not use a Set add all of the elements to that set, check if that element does not contain any left neighbor just loop through while loop to get the max length say S1 is the set and check S1.contains(num+len) initialize len to be 0. When it comes out of while loop take the longest one. I know the approach is the same with hashmap too but the code is lot less and we can check less conditions class Solution { public int longestConsecutive(int[] nums) { Set S1 = new HashSet(); int longest = 0, len = 0; for(int num:nums) S1.add(num); for(int num:nums){ if(!S1.contains(num-1)){ len = 0; while(S1.contains(num+len)){ len++; } longest = Math.max(len, longest); } } return longest; } }
it is really hard to explain code in several languages. Everyone has their own preference. But rest assured, if you are following the logic correctly...writing code shouldn't be a problem.
@@nikoo28 u r right Bhaiya but just for feedback I said and max programmers prefer C++ as I know, otherwise your words are very clear and stable that anyone can understand.
Your video is really helpful brother but in this particular source code there is a minor mistake and i have also checked the source code in your git hub profile "MINOR MISTAKE : Here when we traverse through the hashMap we are not marking it as true for eg: if (numberTravelledMap.get(num) == true) { continue; } // this will skip it and // Mark the current number as traveled numberTravelledMap.put(num, Boolean.TRUE); this was not in the original source code " KINDLY CORRECT ME IF I AM WRONG , BUT ANYWAYS YOUR VIDEOS ARE REALLY HELPFUL FOR MY DSA PREPATATION JOURNEY , GOD BLESS YOU BROTHER ❤
Tnxs sir..... I am from bd🇧🇩......sir can you please make a video about Github....how can open...how can it work....how can we use properly it.....that typ video..... Tnxs once againAs sir❤️
no, this approach is O(n) time. you only iterate through the array once. With the help of the hashmap, you can cut the time complexity down, at the cost of a little bit extra space.
a question i have: the first while loop when you search for nextNum (&& exploreMap.get(nextNum) == false) and the second while loop when you search for prevNum (&& !exploreMap.get(prevNum). The first one you say if it equals false. The second one you just use an exclamation point. Is this doing the same thing, or is it different? If it is the same, why did you do it in 2 different ways? It just confuses me a little bit.
![[UNCUT] “บอสณวัฒน์” ลากไส้!! ใครหนุนหลัง "แม่ตั๊ก ป๋าเบียร์" I คนดังนั่งเคลียร์ I 30 ก.ย. 67](http://i.ytimg.com/vi/QlD7mU2KKRk/mqdefault.jpg)
I would have given up on my DSA journey had you not started this channel, baba!
When ever I need a solution for any leetcode problem I always look for your channel first.
Why didn't I find this channel early but I'm grateful I found it. Thank you so much, your channel is a real blessing ❤
Your explaination is so so neat !!!!.. Thanks for your time :)
Getting the time Limit exceeded with the above solution.
The solution passes well on LeetCode. Check the code in video description
Great explanation. A very impressive approach. Thank you very much.
Your'e the best, keep going.
For the approach using optimization by sorting, one edge case to solve for would be repeated numbers. For example, take [1, 2, 0, 1] as input. After sorting it would be [0, 1, 1, 2]. So finding longest sequence, the right answer is [0, 1, 2], but your approach would take [0, 1] or [1, 2] as the final answer. Am curious to know how to handle this case with the sorting approach.
for a test case : [1, 2, 0, 1]
the right answer is: [0, 1] or [1, 2]
0, 1, 2 are not consecutive in your input test case.
Nice approach. Thank you.
Glad it was helpful!
Best video so far, thank you.
Brilliant explanation I understand
The best!!! Keep up the great work!!!😃
One question Nikhil sir. Where have me marked the first visited elem as true as mentioned in the video at 14:48 ? Am I missing something or its a typo.
Btw thanks a lot for this beautiful explanation.
yes you are right.
Exactly, that’s what I’m wondering too!!
excellent solution bro super methodology
you can make it more efficient by adding:
if (longestLength > nums.length / 2) {
return longestLength;
}
to the end of every iteration, this will check if we have a longestLength that is bigger that 1/2 array
thanku😇, was struggling a lot to understand this problem...finaallyyyy got the best
Easy solution,
public int longestConsecutive(int[] nums) {
HashSet myset = new HashSet();
int maxsize = 0;
for(int num: nums){
myset.add(num);
}
for(int num: myset){
int current = num;
int current_size = 1;
if(!myset.contains(current-1)){
while(myset.contains(current+1)){
current = current + 1;
current_size ++;
}
maxsize = Math.max(maxsize, current_size);
}
}
return maxsize;
}
This is nice too! I love Java.
numSet = set(nums) # remove repetition
longest = 0
for n in nums:
# check if n is the start of a sequence
# that is, if left neighbour does not exist, then it is the start of a sequence
if (n-1) not in numSet:
# if it is, check for consecutive sequence
length = 0
while (n + length) in numSet:
# if right neighbour exist, keep increasing the length
length += 1
longest = max(longest, length)
return longest
Hello Nikhil sir, I tried both the sorting approach and the HashMap approach on leetcode. Why does using the map take more time than the sorting approach, even though it is O(n) compared to O(NlogN)?
Using sorting - 16ms
Using hashmap - 47ms
how you chechked
bro don't rely on runtime of leetcode, it will differ every time you submit a code, even the same code may give you different runtime if submitted again and again. That's why we use big O notations to summarize the efficiency.
gr8 explanation 👌👌
very nice sir
Thanks for de explanation, it was very clear and helpful.
I have just one question... Why does the solution with map work without something like numberTravelledMap.put(num, Boolean.TRUE); at any moment?
I have the same question. Feels like you can do it with out pre setting of the map to false
what would happen if we did't check whether it had been explored or not? just this part was a little bit confusing for me, but overall great explanation
How is the the time-complexity of brute force is O(n^3)? Shouldn't it be O(n^6)? For example, if the array is [5, 1, 4, 3, 2, 6], then, if we start with 1, we need to traverse the array 5 times to get to the answer?
How is this O(n) with the nested while loop? Is it because this would technically be O(n * m) where n is the length of nums and m is the longest possible sequence, and m will always be less than or equal to n so it's negligible to O(n) ? Couldn't this be O(n^2) if all numbers in nums are sequential? Am I close or way off?
even if it is a nested loop, we do not iterate on every element twice. We use the inner loop to move ahead.
why not use a Set add all of the elements to that set, check if that element does not contain any left neighbor just loop through while loop to get the max length say S1 is the set and check S1.contains(num+len) initialize len to be 0. When it comes out of while loop take the longest one. I know the approach is the same with hashmap too but the code is lot less and we can check less conditions
class Solution {
public int longestConsecutive(int[] nums) {
Set S1 = new HashSet();
int longest = 0, len = 0;
for(int num:nums) S1.add(num);
for(int num:nums){
if(!S1.contains(num-1)){
len = 0;
while(S1.contains(num+len)){
len++;
}
longest = Math.max(len, longest);
}
}
return longest;
}
}
this method works as well...great job!!
Nice explanation.. 🎉
I love your all video sir
You are teaching like in best way ☺️
Keep watching
Where in the code are we setting the first number we are currently on from the array to true in the map?
Thank you
brute force is o(n^2) not n^3 as you have stated , thanks
it is O(n^n) noob. If you have like all sequence [1,3,2,5,4,8,6,7,10,11,9]
even after sorting, we need somthing like set, to avoid test cases like: [1,2,0,1]
Thanks for the wonderful explaination
Glad it was helpful!
The brute force approach has time complexity n^2 but not n^3.
how bruteforce is taking n^3
Thank you!
Thanks, bhaiya
and yes bhaiya try to explain code in C++ also.
it is really hard to explain code in several languages. Everyone has their own preference. But rest assured, if you are following the logic correctly...writing code shouldn't be a problem.
@@nikoo28 u r right Bhaiya but just for feedback I said and max programmers prefer C++ as I know, otherwise your words are very clear and stable that anyone can understand.
@@nikoo28 no sir please! your current language is prefect.
sir java is perfect i like ur video@@nikoo28
Does this work even for duplicate values in the array?
Really love ur videos.
Thank you so much 😀
Didn't you traversed through the input list twice?? Once to create hashmap and next while actually iterating over list.
yes, so the complexity is O(2 * n) which is equivalent to O(n)
helpful video :)
Thanks
❤❤❤
Your video is really helpful brother but in this particular source code there is a minor mistake and i have also checked the source code in your git hub profile "MINOR MISTAKE : Here when we traverse through the hashMap we are not marking it as true for eg: if (numberTravelledMap.get(num) == true) {
continue;
} // this will skip it and // Mark the current number as traveled
numberTravelledMap.put(num, Boolean.TRUE); this was not in the original source code " KINDLY CORRECT ME IF I AM WRONG , BUT ANYWAYS YOUR VIDEOS ARE REALLY HELPFUL FOR MY DSA PREPATATION JOURNEY , GOD BLESS YOU BROTHER ❤
Tnxs sir..... I am from bd🇧🇩......sir can you please make a video about Github....how can open...how can it work....how can we use properly it.....that typ video..... Tnxs once againAs sir❤️
Ok I will try
The question mentions that You must write an algorithm that runs in O(n) time but ig this approach takes 0(n^2) time.
no, this approach is O(n) time. you only iterate through the array once. With the help of the hashmap, you can cut the time complexity down, at the cost of a little bit extra space.
Absolutely correct
sir can you name that book for learning DsAlgo
The book by Cormen is really exhaustive..covers everything you need to learn
can someone help me with the code for brute force. just for the better understanding of loops.
to understand loops, this problem is not ideal. Nested loops are never easy to look at and understand.
In which language u write this code sir
that is JAVA usually
Here is my solution , I think its simpler , please let me know if any issues: public int longestConsecutive(int[] nums) {
if(nums.length < 2){
return nums.length ;
}
Arrays.sort(nums);
int lC = 1;
int longestLc = 1;
int lastNum = nums[0];
for(int i = 1 ; i < nums.length ; i++){
if( nums[i] == lastNum){
continue;
}else if(nums[i] == lastNum+1){
lastNum = nums[i];
lC++;
}else{
lastNum = nums[i];
if(longestLc < lC){
longestLc = lC;
}
lC = 1;
}
}
if(longestLc < lC){
longestLc = lC;
}
return longestLc;
}
you didnt even run your code
check out my code on github...link available in description
a question i have: the first while loop when you search for nextNum (&& exploreMap.get(nextNum) == false) and the second while loop when you search for prevNum (&& !exploreMap.get(prevNum). The first one you say if it equals false. The second one you just use an exclamation point. Is this doing the same thing, or is it different? If it is the same, why did you do it in 2 different ways? It just confuses me a little bit.
You are checking in both directions