Longest Consecutive Sequence (LeetCode 128) | Full solution quick and easy explanation

Longest Consecutive Sequence (LeetCode 128) | Full solution quick and easy explanation | Interviews

Рет қаралды 15,923

Күн бұрын

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

Пікірлер: 69

@AadeshKulkarni 6 ай бұрын

I would have given up on my DSA journey had you not started this channel, baba!

@sunshineandrainbow5453 Күн бұрын

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 ❤

@stoiandelev12345678 9 ай бұрын

Great explanation. A very impressive approach. Thank you very much.

@kunalkheeva Жыл бұрын

Best video so far, thank you.

@manishasharma-mh7fo Жыл бұрын

thanku😇, was struggling a lot to understand this problem...finaallyyyy got the best

@myosith4795 8 ай бұрын

Brilliant explanation I understand

@Jaydoshi77 6 күн бұрын

gr8 explanation 👌👌

@candichiu7850 Жыл бұрын

The best!!! Keep up the great work!!!😃

@ramphapal6610 Ай бұрын

Nice explanation.. 🎉

@techsavy5669 Жыл бұрын

Nice approach. Thank you.

@nikoo28 Жыл бұрын

Glad it was helpful!

@pratyakshamaheshwari8269 Жыл бұрын

Thank you!

@mohitjain957 Жыл бұрын

I love your all video sir You are teaching like in best way ☺️

@nikoo28 Жыл бұрын

Keep watching

@sachinsoma5757 10 ай бұрын

Thanks for the wonderful explaination

@nikoo28 10 ай бұрын

Glad it was helpful!

@Amit00978 Жыл бұрын

helpful video :)

@subee128 7 ай бұрын

Thank you

@parthmodi2028 7 ай бұрын

Really love ur videos.

@nikoo28 6 ай бұрын

Thank you so much 😀

@unknownman1 8 ай бұрын

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; }

@DeleMike7 Ай бұрын

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

@JustMeItsMMN 3 ай бұрын

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

@user-rh9rk9hx1t 4 ай бұрын

Does this work even for duplicate values in the array?

@snehakandukuri429 3 ай бұрын

Getting the time Limit exceeded with the above solution.

@nikoo28 3 ай бұрын

The solution passes well on LeetCode. Check the code in video description

@aswanthnarayanan2942 Жыл бұрын

Thanks

@prasoonlall9432 14 күн бұрын

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.

@HeitorBernardino 6 ай бұрын

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?

@billyfigueroa1617 5 ай бұрын

I have the same question. Feels like you can do it with out pre setting of the map to false

@tejaltatiwar4682 10 күн бұрын

how bruteforce is taking n^3

@Usseeer_kaizen 20 күн бұрын

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

@sreeharsharaveendra289 7 ай бұрын

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.

@nikoo28 7 ай бұрын

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.

@jaydoshi3623 2 ай бұрын

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

@tejaltatiwar4682 26 күн бұрын

how you chechked

@kevalgundigara 5 ай бұрын

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?

@nikoo28 4 ай бұрын

even if it is a nested loop, we do not iterate on every element twice. We use the inner loop to move ahead.

@himanshujoshi1848 6 ай бұрын

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?

@notmrabhi1 Жыл бұрын

Thanks, bhaiya and yes bhaiya try to explain code in C++ also.

@nikoo28 Жыл бұрын

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.

@notmrabhi1 Жыл бұрын

@@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.

@aayushpatel8584 Жыл бұрын

@@nikoo28 no sir please! your current language is prefect.

@rizwanalikhan9213 11 ай бұрын

sir java is perfect i like ur video@@nikoo28

@adityajaiswal9069 Жыл бұрын

can someone help me with the code for brute force. just for the better understanding of loops.

@nikoo28 Жыл бұрын

to understand loops, this problem is not ideal. Nested loops are never easy to look at and understand.

@alexmercer416 5 ай бұрын

even after sorting, we need somthing like set, to avoid test cases like: [1,2,0,1]

@continnum_radhe-radhe Жыл бұрын

❤❤❤

@omkarkhandalkar8869 Жыл бұрын

sir can you name that book for learning DsAlgo

@nikoo28 Жыл бұрын

The book by Cormen is really exhaustive..covers everything you need to learn

@abdullahalnahian1266 Жыл бұрын

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❤️

@nikoo28 Жыл бұрын

Ok I will try

@akshanshsharma8157 4 ай бұрын

The brute force approach has time complexity n^2 but not n^3.

@mohamedhassan-ub4kj 11 ай бұрын

brute force is o(n^2) not n^3 as you have stated , thanks

@vinaykumarnandhikanti2822 10 ай бұрын

it is O(n^n) noob. If you have like all sequence [1,3,2,5,4,8,6,7,10,11,9]

@xtremedance6330 10 ай бұрын

In which language u write this code sir

@nikoo28 9 ай бұрын

that is JAVA usually

@atharv9924 9 ай бұрын

Didn't you traversed through the input list twice?? Once to create hashmap and next while actually iterating over list.

@nikoo28 8 ай бұрын

yes, so the complexity is O(2 * n) which is equivalent to O(n)

@vsaihruthikreddy7127 24 күн бұрын

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; } }

@nikoo28 24 күн бұрын

this method works as well...great job!!

@adityakumarsingh8406 4 ай бұрын

The question mentions that You must write an algorithm that runs in O(n) time but ig this approach takes 0(n^2) time.

@honey-xr5kp 4 ай бұрын

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.

@nikoo28 4 ай бұрын

Absolutely correct

@kag1984007 6 ай бұрын

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; }

@fandusmercius723 5 ай бұрын

you didnt even run your code

@nikoo28 4 ай бұрын

check out my code on github...link available in description

@honey-xr5kp 4 ай бұрын

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.

@nikoo28 3 ай бұрын

You are checking in both directions