Longest Consecutive Sequence Leetcode 128

Longest Consecutive Sequence Leetcode 128

[GregHogg]

Master coding interviews for FREE at AlgoMap.io!

[galduscz]

num in set has a worst case time complexity of O(n) which means the actual time complexity of the algorithm might be O(n*logn)

[lagmaster]

did this in C++. only need to iterate the entire array one single time, storing found numbers into a bitmask and then check the bitmask for where the sequence breaks.

[lqueryvg]

Here's my explanation as to why the time complexity is O(n):
1. The best case is where the list contains no sequences at all. This will examine every element once O(n) and look for its predecessor (O(n)) and not find it. This is O(n) + O(n) = O(n).
2. Worst case is where the whole list is a sequence. It still needs to examine every element O(n) and check it's predecessor O(n), but when it finds the lowest number in the sequence it will examine all the elements in the set one more time O(n) as it counts the length of the sequence. This is O(n) + O(n) + O(n) = O(n).
Note: I haven't included the initial conversion from a list to a set. This is another O(n). But O(4*n) is still the same as O(n) when we are talking about time complexity notation.

[AvidCluelessGuy]

Second one is definitely more elegant, but the only reason that the first isn’t O(n) is because radix sort wasn’t used.

[muizzy]

The way your structuring of this code just made me question whether it should be O(n^2) instead... xD

[epicgamer]

I need an explanation on why sets are so powerful in these cases. I know they are supposed to work like the mathematical set, but i dont understand how looking for elements are so quick.

[raviiMaurya]

Could you explain more on the 2nd part. Else we dont gain anything from these type of series

[dieformusic]

i think there is no need of set in the optimal solution

[erikremmelzwaal]

Create a help function that checks if the previous value is one larger else reset counter to 1.
class CountConsecutive:
def __init__(self):
self.c = 0
self.x = sys.maxsize
def __call__(self, x):
self.c = (self.c + 1) if (x == self.x + 1) else 1
self.x = x
return self.c
cc = CCountConsecutive()
Now make from nums a set and sort, apply function and take max value:
print(max( map( cc,
I think that set() is O(n) and sorted is O(n*log(n))

[youssefmamdouh]

Can i solve it using disjoint set union?

[pi_xi]

Why even search in the set instead of sorting and iterating? You can even exit earlier when the set's remaining length is < than the longest closed sequence you found.

[imadelachiri]

Can you recommend a good whiteboard software to use with a mouse for writing code explanations in interviews?

[ViktorTheRook]

if num-1 not in s -> doesnt this search the entire set to make sure its not in the set? so for each num he is checking num -1 not in set so n²? I dont understand how not in works in python i guess

[alexmckinley]

I learn nothing from your videos, other than some programmers like to flex their python skills. Am I missing something?

[bufdud]

I got confused. Idk but can you explain how the voice doesnt match your face

[ahmetemregurdal]

Set isn't O(n), stop spreading lies. A regular set, based on red black tree or similar, would be O(nlogn), and actually, θ(nlogn). A hash based set however has an average runtime of n, which is Ω(n). Because it is the best case. But hashes has an issue, it is called collision. Because of this, hash sets actually have a worst case of O(n^2)

[pigbull]

is this dubbed over? wtf is with this 1990's japanese samurai movie dubbed in english AI voice

[akdas]

Your are bad at algorithm. You use built in sorting, two for loops like brute force. How do you do solve this by O(n)