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

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.

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:

📖 Reference Books:

🎥 My Recording Gear:

💻 Get Social 💻

#leetcode #programming #interview

[AadeshKulkarni]

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

[stoiandelev]

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

[candichiu]

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

[manishasharma-mhfo]

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

[mohitjain]

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

[rhrkhxt]

Does this work even for duplicate values in the array?

[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

[prasoonlall]

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]

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?

[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

[snehakandukuri]

Getting the time Limit exceeded with the above solution.

[sreeharsharaveendra]

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.

[jaydoshi]

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

[himanshujoshi]

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?

[adityajaiswal]

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

[alexmercer]

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

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

[akshanshsharma]

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

[notmrabhi]

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

[unknownman]

Easy solution,

public int longestConsecutive(int[] nums) {
HashSet<Integer> myset = new HashSet();
int maxsize = 0;

for(int num: nums){
myset.add(num);
}

for(int num: myset){
int current = num;
int current_size = 1;



current = current + 1;
current_size ++;
}

maxsize = Math.max(maxsize, current_size);
}

}
return maxsize;
}