Longest Consecutive Sequence - Leetcode 128

#coding #leetcode #python

[siddmathlver]

I want my entire yt shorts feed to be filled with this type of content.

[Sedeerah]

It's O(n), because the while loop is only executed if n-1 is not in the set, meaning only for the starting elements of a sequence. Each sequence has exactly one starting element, so it iterates once per existing sequence. It iterates until it reaches the end of a given sequence. The set of n numbers is equal to the union of all existing sequences, so you get O(n). Creating the set is of course also O(n)

[manoharpenta]

Thank you so much man. Pls keep making these shorts solving interview coding questions. It saves me from going through these questions every time I have a interview. I would prefer going through bunch of shorts than going through questions and see their solutions.

[jaymomnang]

That's a very clever way to solve it

[ianokay]

I actually love this format for your content, who would have thought 🤯

[subratkumarnayak]

I really love that mostly hashmaps are used for optimal solution

[Cicada]

But thats not totaly linear because of the while loop, if there are multiple long sequences it will take longer than if there was only one

[kuruluu]

With larger sets of data, sets have an extra log factor and since they also have a bad constant, the sorting solution should theoretically outperform the one shown here.

[Mar_]

next level bro! never thought to use a hash set 👏🏾🏆another great video!!💯

[lestath]

You could've ended the short with "Now you know how to solve" and at the beginning say "The longest consecutive sequence...". That would've been pretty neat lol

[dbgmitre]

Your while loop in there would make it O(n²) for a descending ordered sequence. You could keep track of how long are the sequences and "join" them

[adityarawat]

What about time for inserting each element into the hashset?

[altkev]

Love practicing skills that have never come up in LOB programming

[ash__borne]

Had the same problem but with a constraint: using nothing but strings and integers 😂 try breaking your head like that guys. Anyways, nice video 👍🏾

[---]

Sorry, I'm not sure if I understand. Is this solution in O(n) average case or worst case?

Because HashSet's Worst Case time complexity is O(n) for search/insertion/removal, while it's average case time complexity is O(1) for all 3 operations. Which could mean that this solution's worst case time complexity is O(n^2) because you will be searching the hash set each iteration inside a loop that iterates n times.

All in all, it's still a very creative solution!

[ShinAkuma]

Lots of questions here. Do duplicate elements count in the subsequence ?
What if 2 different subsecuences have the same length ?

[Sprezzatura]

Hashset is not free. It is just a way to hide the actual complexity

[MohanRam-mqpk]

But why it is not n^2 for every element we are checking the set ..?

[michaelvankley]

But you can sort faster than n*log(n)… It’d be more work and maybe not as good a solution in this case (though I suspect on a large scale, the hash lookups are gonna get costly). But I hate hearing a solution that involves sorting getting dunked on for a time complexity that has to do with standard library sorting implementations.

[michaelvankley]

But you can sort faster than n*log(n)… It’d be more work and not as good a solution in this case, but I hate hearing a solution that involves sorting getting dunked on for a time complexity that has to do with standard library sorting implementations.