Noob O(n log n) Developer vs Strong O(n) Programmer in Longest Consecutive Sequence, Leetcode 128

Please check my playlists for free DSA problem solutions:

[GregHogg]

Master Data Structures & Algorithms For FREE at AlgoMap.io!

[adriandev]

As a n log n developer, I don't find it funny at all.

[SpeckyYT]

is it just me or is the O(n) actually worst-case O(n^2)? because it can loop for every n items n times (more precisely, in the worst case it would take (n^2/2) iterations). but I can understand why it's more efficient on average.

[volleyballhut]

Was not expecting the flex at the end 😳

[GameJam]

Wait, how long does the x in list operation take to do in python? I'd guess it would have to be using hashmaps, so constant time for that to work.

[dorkmania]

It seems like there's an a additional minor optimization that can be done here - if we find a new sequence, we can omit checking it if 'num + longest' isn't in our set 's' as it would imply that length of this new sequence won't be greater than the current value of 'longest' and thus ignored.

[gaurangdeka]

Called me a noob in n log n different ways

[rnishu_]

Not sure how python does sets, but if its hashing isnt the worst case n^2? And if its using trees the worst case is nlogn right? I think for a well thought out edge case this solution might exceed time limit

[aravind]

In the O(n) solution, there is a loop inside an loop. So won't it be considered O(n^2)?

[KarthikKarthik-elhh]

Inserting/searching in a set takes O(logn) time even in C++, so its slower in python? Im saying his solution is still O(nlogn) not O(n).

[hellNo]

ok i need to start practicing again. also is it me or haft the problems are solvable with a set? not the ones you show. like it feels like babies first step into programming.
i really like the problem you showed where you showed the closed type, since that was my first thought too. (find the number that is missing from a set of numbers between 0 and n or something like that)

[noschXL]

sort and count would be possible right?

[sumanthmurthy]

Yeah I was going to repeat what I saw on one other comment. The second way (without sorting) is looping twice so isn’t it O(n**2)?? It’s worse than O(nlogn) right?

[_bman]

sorry, correct me if im wrong, but wont the "in" operation make it more than o(n)? i know youve got your fancy hash tables and bloom filters to make testing for set membership faster, but is it really o(1) fast?

[Firewheels]

Been in the game far too long to be learning things from these videos. 😂

[RaghuArunkumar]

As a noob programmer i can relate to this video 😅

[big-anvil]

Good problem. The O(n) solution was not obvious to me at all.

If I had come up with an O(n^2) solution first, I might have actually had an easier time thinking of this solution.

[darcash]

Summary:
Convert to set for O(1) "in" checks. Loop thru, condition as if num - 1 not in set, since if it is, you should start there. from there it is while loop incrementing current count, num, and updating longest count if needed after that.

[asagiai]

If you think about it all those numbers are in sequence. The question should be longest same gap sequence or something.

[warguy]

I dont rly get how the "in" keyword can be that efficient but another super stupid way to do it in o(n) could be get max of array, make array of size max, and iterate the original array, filling values as indices of the new size max array. At the end check if all elements are "filled" whether that be boolean or integer values. Really dumb but complexity is 3n /in O(n)