Amazon Interview Question! | Longest Consecutive Sequence - Leetcode 128

leetcode, coding interview question, data structures, data structures and algorithms, faang

[GregHogg]

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

[denravonska]

Are these real interview questions in the US?

"If you want to work here you must solve this super obscure problem that you'll most likely not encounter within the next 20 years"

I get that it's a way to assess problem solving skills, but Jeez Luigi is it a niche problem to solve.

[DarkSwitchJ]

How about sort the array and going through it checking for increasing number intervals?

[Benthorpy]

Your solution is O(n^2) but it can be O(n) if you just iterate over the set s instead of nums

consider the case when you have n/2 1's and then the sequence 2 ... n/2

for each 1 you will enter the inner if statement and then you will enter the while loop n/2 times while you build up current_len to n/2

there are n/2 1's so you have O(n/2 * n/2) == O(n^2 /4) == O(n^2)

correct me if i am wrong

[Speiger]

As someone who wrote an entire collection library.
I didnt know that hashsets were sorted by natural order.
Assuming you semi random inputs your solution works only with lower spec numbers because the hashing function allows for ordering. The moment you go above bucket sizes you basically lose all "ordering" support.

A better solution would have been using a TreeSet.
Because that 1 deduplicates entries and 2 sorts them too.
And due to how the tree structure works it has similar insertion complexity and faster iteration speed then a hashset.
Which means you can simply use a iterator a single iterator and 3-4 variables to achieve the same thing faster.

Also yes you do have a unhealthy relationship with normal hashsets...
Like others said.

Because all examples i have seen so far were actually slower with sets...
Some were slower because ignoring that cpu caches are existing.
Others being that there were better structures out there.
Or simply that hashsets are terrible to iterate over because you also iterate over the empty entries too. Thats why linkedHashSets also exists

[nothinhh]

This is a very nice solution! Thank you so much!
But another challenge for you: Can you do this in C++? I think C++ is much more primitive than Python therefore makes it harder...

[kursh]

i think you have an unhealthy relationship with hashsets

[gone]

Worst case is O(n^2) therefore its complexity is not O(n)

[AyushSingh-yqso]

Why set, why don't we check for n-1 in given array

[jeremyrobin]

Not totally sure I know what I'm talking about. But isn't searching for something in a hashmap O(1). And if you have 1, 2, 3, 4, 5, ... wouldn't that be like n^2/2 operations which would mean it is worst case O(n^2)

[electrowizard]

I don't see how this handles input [1, 3, 2]. Max_len is 1, 1, 1 on the three iterations. Final loop of 2, 2-1 is in the set and the inner loop doesnt execute. Right?

[amitd]

What will happen if first number is [2, 1, 3] first if condition is (2-1) not in set, so it is there but we are skipping the logic?

[harshaggarwal]

It would be much easier to just sort the array first then go through the array to find the sequence

[sanjeevsinghrajput]

Can this be done using a Priority Queue?

[wdeniss]

O(n) is the average case right?
The worst case should be O(n²), bc of the set(nums)

[AlfonsoRoa]

The order of this solution is n^2 and instead of iterate the "nums" you should iterate the set, im the worst case it will have the same amount of values as in nums.

A better solution is to order the values (n log(n)) and in a single iteration check if the current value plus 1 is equal to the next, add 1 to the actual length, add 0 if they are equal, or restart the counter in any other case. Keep the longest streak. N log(n) solution. It can be eaven easier with a sorted set to skip equal values.