Longest Consecutive Sequence - Leetcode 128 - Hashmaps & Sets (Python)

[@GregHogg]

IMPORTANT FIX - WE SHOULD LOOP THROUGH THE SET S AND NOT NUMS ON LINE 5!!!

[@orlanduca2567]

why is it relevant?

[@khushgandhi1085]

@@orlanduca2567I think it’s because looping through the set allows for skipping any duplicates in nums, which would improve the performance.

[@ffy291]

@@orlanduca2567 skipping over duplicates. If not: if the start of a seq is a duplicated that exist k times you would check the seq k times which would bring you time up drasticlly

[@franciscoserra8455]

@@orlanduca2567I tested the same code looping through the list and it took 434ms but looping through the set, which doesn’t have repeated numbers, took only 17ms.

[@lautarortega]

Does the set creation itself not count as an O(n) operation? You would need to iterate through all elements of the list to construct it. Then, you would be iterating over the elements twice, being O(n**2). Edit: Sorry, it would be O(2n), right? And the notation simplifies to O(n).

[@aidanahram8245]

This is O(n^2) because for each value in the set, you are finding the longest sequence that starts with that value. For example [1, 2, 3, 4, 5], it will find count 5, then 4, ..., to 1. Before you start the inside while loop you must check that it is the start of the sequence by making sure that the num - 1 isn't in the set. If its not in the set then start checking num + 1

[@Infinitely16]

checking for the existence of a value in a set takes O(1) time. That's why we are using the set.

[@SamuelSandeen]

Interesting, my thought would be to remove elements from the set each time it was part of a sequence. Yours is likely more elegant since it doesn't mutate the set.

[@GregHogg]

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

[@JoeTan-nq4fq]

Awesome solution

[@anuraag5487]

Very clean ❤❤

[@SubhashCS-q8p]

can anyone please tell me why this is giving time limit exceeded error on leetcode? longest = 0 sett = set(nums) for num in nums: if num - 1 not in sett: max_len = 1 while num+1 in sett: max_len += 1 num += 1 longest = max(longest, max_len) return longest

[@sajinreyans3329]

What is the use of longest =0 variable

[@tominchazhikat3708]

W Fellow right here

[@fadygamilmahrousmasoud5863]

thats smart

[@cmarquay]

Hurray

[@GregHogg]

😂

[@chungt6545]

Thank you for the explanation. I'm not sure if I understand it correctly, but I think the time complexity is not O(n) but O(n^2), since we have 2 loops. The while loop makes the solution O(nk), where k is the average consecutive sequence's length. In the worst case, it's O(n^2), when all n elements construct an n-length consecutive sequence. How do you think?

[@sonicrushXII]

My Thoughts exactly, I mean there are two loops in there

[@mohammadhammoud6531]

That's wrong , it is O(n) because you are iterating over each element exactly once . The worst case you are talking about is not O( n^2) it is O(n + n ) since you will run over all the elements once you reach the min of the sequence , but after that , every other element will have the element before already in the set , thus won't enter the 2nd loop. Hope this explains it.

[@RashidAlipage]

@@mohammadhammoud6531 it is O(n), not O(n^2)

[@chungt6545]

@@mohammadhammoud6531 I think I got it finally. Thank you!

[@mohammadhammoud6531]

​@@chungt6545 ur welcome 🙏🏻

[@hlubradio2318]

Very nicely done. You should be a college professor but most of them are cocky bastards anyway.

[@ccricc-tf7fk]

Time limit Exceeded when you submit

[@mouseaviator3672]

Iterate over each item in the set, not over each item in the list, this is because the list will have repetitive values, and you will continue computing the same sequence multiple times

[@doomnypd]

@@mouseaviator3672 Thanks got it

[@hlubradio2318]

Holy cow! Aren't there Sr SE who'd architect the software? Why make us do things like this. I know people who never majored in CS and are Software Engineers. Unbelievable

[@hlubradio2318]

Prof Singh Gupta. First day of class. Hi students! Are you smarter than me? If not you'll be in hell in my class. If you are you can be my student. What the f!

[@technicallytechnical1]

wild 💀