Longest Consecutive Sequence (LeetCode 128) | Full solution quick and easy explanation | Interviews
HTML-код
- Опубликовано: 30 июл 2024
- As direct this problem looks, the trickier it is to solve in O(n) time complexity. In this video learn how to build a better solution on top of a brute force solution and how to determine which data structure will be a good choice. This will speed up how you find the longest consecutive sequence. All along with beautiful animations and visuals.
Actual problem on LeetCode: leetcode.com/problems/longest...
Chapters:
00:00 - Intro
00:59 - Problem Statement and Description
03:17 - Brute Force Method
05:54 - Sorting to the rescue
08:21 - Optimizing for O(n)
14:02 - Dry-run of Code
17:21 - Final Thoughts
📚 Links to topics I talk about in the video:
Brute Force Paradigm: • Brute Force algorithms...
Quick Sort: • Quick Sort super easy ...
HashMap Data Structure: • What is a HashMap? | D...
What is Time Complexity: • Big O Notation Simplif...
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🔗 To see more videos like this, you can show your support on: www.buymeacoffee.com/studyalg...
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview
I would have given up on my DSA journey had you not started this channel, baba!
Great explanation. A very impressive approach. Thank you very much.
Best video so far, thank you.
thanku😇, was struggling a lot to understand this problem...finaallyyyy got the best
The best!!! Keep up the great work!!!😃
Brilliant explanation I understand
Nice approach. Thank you.
Glad it was helpful!
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
Thank you!
I love your all video sir
You are teaching like in best way ☺️
Keep watching
Nice explanation.. 🎉
Thanks for the wonderful explaination
Glad it was helpful!
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
helpful video :)
Thank you
Really love ur videos.
Thank you so much 😀
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.
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?
Does this work even for duplicate values in the array?
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.
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
Getting the time Limit exceeded with the above solution.
The solution passes well on LeetCode. Check the code in video description
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
Thanks
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
even after sorting, we need somthing like set, to avoid test cases like: [1,2,0,1]
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.
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
The brute force approach has time complexity n^2 but not n^3.
how bruteforce is taking n^3
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.
❤❤❤
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!!
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]
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
sir can you name that book for learning DsAlgo
The book by Cormen is really exhaustive..covers everything you need to learn
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)
In which language u write this code sir
that is JAVA usually
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
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