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

[@AadeshKulkarni]

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 ❤

[@JustMeItsMMN]

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

[@stoiandelev12345678]

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

[@unknownman1]

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

[@jaydoshi3623]

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]

how you chechked

[@RamPageMMA]

Where in the code are we setting the first number we are currently on from the array to true in the map?

[@Jaydoshi77]

gr8 explanation 👌👌

[@techsavy5669]

Nice approach. Thank you.

[@nikoo28]

Glad it was helpful!

[@kunalkheeva]

Best video so far, thank you.

[@snehakandukuri429]

Getting the time Limit exceeded with the above solution.

[@nikoo28]

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

[@prasoonlall9432]

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.

[@ravishankar7972]

yes you are right.

[@RamPageMMA]

Exactly, that’s what I’m wondering too!!

[@sreeharsharaveendra289]

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]

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.

[@manishasharma-mh7fo]

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

[@vvssspraneeth1852]

excellent solution bro super methodology

[@Usseeer_kaizen]

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

[@candichiu7850]

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

[@myosith4795]

Brilliant explanation I understand

[@kevalgundigara]

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]

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

[@HeitorBernardino]

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]

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

[@tejaltatiwar4682]

how bruteforce is taking n^3

[@himanshujoshi1848]

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?

[@mohitjain957]

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

[@nikoo28]

Keep watching

[@alexmercer416]

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

[@sachinsoma5757]

Thanks for the wonderful explaination

[@nikoo28]

Glad it was helpful!

[@ramphapal6610]

Nice explanation.. 🎉

[@user-rh9rk9hx1t]

Does this work even for duplicate values in the array?

[@mohamedhassan-ub4kj]

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

[@vinaykumarnandhikanti2822]

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

[@subee128]

Thank you

[@akshanshsharma8157]

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

[@vsaihruthikreddy7127]

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]

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

[@pratyakshamaheshwari8269]

Thank you!

[@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]

sir java is perfect i like ur video@@nikoo28

[@Amit00978]

helpful video :)

[@parthmodi2028]

Really love ur videos.

[@nikoo28]

Thank you so much 😀

[@continnum_radhe-radhe]

❤❤❤

[@aswanthnarayanan]

Thanks

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

[@adityakumarsingh8406]

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]

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]

Absolutely correct

[@atharv9924]

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

[@nikoo28]

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

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

[@omkarkhandalkar8869]

sir can you name that book for learning DsAlgo

[@nikoo28]

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

[@kag1984007]

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

[@Digitalgalaxy11]

In which language u write this code sir

[@nikoo28]

that is JAVA usually

[@fandusmercius723]

you didnt even run your code

[@nikoo28]

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

[@honey-xr5kp]

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]

You are checking in both directions