Leetcode 128 - LONGEST CONSECUTIVE SEQUENCE
Vložit
- čas přidán 26. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Problem Link: neetcode.io/problems/longest-...
0:00 - Sorting Solution
1:02 - Conceptual optimal solution
7:23 - Coding optimal solution
#Coding #Programming #CodingInterview - Věda a technologie
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Correction: at 8:13 the subtitle should read "We could also initialize length=1"
Can you explain how this code time complexity is O(n), coz I see inner loop.
@@aumrudhlalkumartj1948 Think about when the inner loop would be worst case (O(n)). It would happen if the input is [1,2,3,4,5,6,7,8] for example. In first outer loop, you will go through all numbers (causing O(n) inner loop) and get your current longest. When you go through second time, the if statement doesn't allow the inner loop to be ran again. Same with the rest of the cases, thus O(1) * O(n) would be worst case
how is this O(n) while there is an inner while loop!!
@@devstuff2576 because the while loop iterates only as many times as the length of the sequence. In the same time it only gets executed at the start of sequences, so it'll only be executed as many times as many sequences there are. So this is the sum of the length of all sequences, which is N. Taking into account each and every element is considered by the outer loop, it adds up to 2*N.
@MrHarryGaming I think the worst case is O(n^2).Because let's suppose we have the array[1,2,3,4,5,6,7].For number 1,the inner loop will iterate for n-1times,so it is O(n).After that, the outer loop will iterate up to n times to check whether there is left neighbor for 2,3,4 up until 7, which is O(n)
So the worst case for time complexity is O(n^2)
Leetcode watched your explanation and switched this question from 'hard' to 'medium' :D
LOL
I also noticed 🤕
😂😂
True XD
leetcode thought they pulled a sneaky on us. but they know only half about us.
Very clear explanation with illustrations without jumping into the code immediately. One of me favorite channels.
Thanks!
Looping over the set is faster than looping over the array if there are duplicate values.
Since this video came out I think they've added new test cases with lots of duplicate values, the runtime of this solution is ~5000ms instead of ~50ms. But if you loop through the set instead of the array the runtime is ~350ms.
I just realized that, I have similar solution to his, but mine removes values from set and it's quite fast, if I remove the nums_set.remove(num) line it works but really slow:
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
nums_set = set(nums)
max_consecutive = 0
for i, num in enumerate(nums):
if num - 1 in nums_set:
continue
curr_consecutive = 0
while num in nums_set:
curr_consecutive += 1
nums_set.remove(num)
num += 1
max_consecutive = max(max_consecutive, curr_consecutive)
return max_consecutive
Nice observation my dude. It's almost hilarious how much the running time improved with a small change. Thanks.
Makes sense. I was wondering why it was taking so long to run
My java solution changed from 1104ms to 28ms with this change. Thanks!
I was just about to complain about how my code is so much slower than his, and thought maybe swift was just not as performant as python, but as soon as i saw this command changed my code to loop over the set the runtime went from 1500ms to 200ms, thanks!!
Hi Neetcode, love your channel and explanation, thanks again! I'd like to suggest one minor code change which speeds up this solution by a lot!
change iterating over nums to numSet. This way you'll skip checking for duplicate numbers.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
numSet = set(nums)
longest = 0
for n in numSet:
# check if its the start of a sequence
if (n - 1) not in numSet:
length = 1
while (n + length) in numSet:
length += 1
longest = max(length, longest)
return longest
Damn this really does improve the runtime significantly. I was confused why mine was so much slower than the best solutions but this makes sense. Thanks!
You can also check if the current sequence is longer that the half of the array at the end of finding sequence
If it is, then there's no possible longer sequence so you can break out of the loop.
"Speeds up the solution by a lot", The time complexity is still O(n), sure it runs faster on the leetcode platform but that is irrelevant
@@dabocousin depends on the occasion. If there are a lot of duplicates, then it makes a big difference.
These videos are great! I am always able to write the code after viewing your explanation (but before viewing your implementation). I think that proves how effective your videos are. Thank you!
Hey NeetCode. I have a question for you. Could you make a video where you explain your failures at solving these problems? I think that even you struggled and had to look at solutions to solve problems. By watching your videos where you have a solution for everything I've always wondered if you are always coming up to these solutions alone or not. I would find very interesting if you show us also your human process, your failures and eventually how you begun getting good at these.
He said in one of the videos that he had practiced alot of problems (i guess he knows most of the patterns) on leetcode in such a way that he can solve medium level problems in 30-40 mins.
I think the majority of the people need exposure to problems and solutions before being able to creatively solve. Especially for the memory and time optimized solutions. I'm definitely not letting that bog me down in my prep process as I know it takes a lot of exposure to first spot the strategies and paradigms you can use to solve these problems. Ex: hashmap frequency counts, two pointers, binary search, etc.
@@sawyerburnett8319 very true. I came up with a solution which looked almost like it instead of constant space. I used array to note down the neighbours that is if a number less than the current number exist, then mark their index as its neighbour. It’s was a similar approach to the union find data structure, though it passed all the test cases it was quite slow, but his solution is much faster and more eligible. Still, the fact that I was able to solve it makes me happy, but yes, you are correct that we have to solve a lot of problems and the main distinction come when we try to optimise.
This solution gives a TLE now. I believe it is still not a O(n) solution since there is a loop inside of a loop and given a long sorted input with duplicate first non left existing integer will make this loop run wild. Nonetheless, appreciate all the solutions you've been posting! Thanks
This. If this was O(n), every sorting algorithm where space is not important, would use this behind the scenes.
Yep, iterating through numSet instead of nums takes care of the test with a bazillion zeroes
Exactly! I was like this isn't O(n)?
@@The2Coolest2what would the complexity be? It seems like it would be, worst case, O(n*m) where m is the length of the longest subsequence (since that’s what occurs on the inner while loop).
@@troyjones9344 But it just counts upwards by 1, it wouldnt be performant on an array like [1, 100000000]
Incredible explanation, so simple when you know to look at the left neighbor, and awesome walkthrough. Keep it up!
Im actually starting to get better at leetcode and problem solving in general thanks to this channel.
I've managed to solve this on my own with the optimal solution as well!
I just solved this and its Medium now. I feel a little better that I struggled so much knowing this used to be a Hard question.
Same!!
wouldnt that make you feel worse?? lol
same
should feel worse, this means old Hards are becoming Mediums and new Hards are even harder now lol.
@@EE12345 Nah, that's too broad of a view. On the scale of mediums it's still closer to a harder problem, so I know where I stand.
Your solutions are so intuitive. Thanks for making these videos!
Very nice explanation, thank you. I think it would be useful to add this note:
"In python, set is implemented as a hash table. So you can expect to lookup/insert/delete in O(1) average."
So are hashtables just called sets in python? similar to how arrays are called lists?
So python has dictionaries too which are the equivalent to hash tables. Sets have some strange implementation which allows O(1) lookups (stackoverflow.com/questions/3949310/how-is-set-implemented)
I think the implementation in this video might give you O(n * log n) running time in other programming languages.
@@andrewfakhry3943 ty!
But since the worst case for a lookup is O(n), doesn’t that make this O(n^2)?
thx man, I appreciate this note cuz i was so confused
Your explanations always help! Interesting that Leetcode has downgraded this problem to medium now.
This is the BEST explanation on the entire Internet! Awesome!
Really awesome explanation, thank you! I am able to code it up just by following your drawing
explanation at it best! I just coded it up with such a flow after you clarified the problem
i love the way you explain the algorithm. Appreciate your efforts.
I never used SET in my life during problem solving 😂 and now I'm giving it a try in every sequence problem that i come across. Genius👏
I already noticed that I could solve this by looking at the left and right sides of current number to see if it is a start of consecutive numbers but I don't know I could use "Set" data structure to do this !
You're so smart!
Once again, the solution as explained here is easy to understand. But the challenge remains that my train of thought would never have brought me to such logic or conclusion in an actual interview.
Tips for increasing performance in C++:
1. Delete each walked number in the set after it has been counted in a consecutive sequence. It will never have to be looked up again, thus it will speed up later lookups.
2. Use unordered_set instead of set. Inserting elements into a set has a time complexity O(log(n)) while an unordered_set has an average time complexity of O(1) and a worst case of O(n). Similarly the time complexity of lookups is better in unordered_set.
My code went from 2000ms to 200ms with these changes.
would deleting each walked number in the set after its been counted in a sequence work? What if there is another sequence that uses the same number
@@hwang1607 If two sequences have the same number, that means they are parts of one complete sequence.
I was able to code it up once you showed the left neighbor deduction. Genius mister neetcode
I was trying to solve this by taking another list where index will be numbers and values should be the existence of these numbers (1: exists, otherwise 0) and then counting the longest sequence of 1s in the list. But it failed for the test cases in which list has negative integers in it. This solution solved the problem entirely. Well Done Neet Code.
Hey I just wanted to say that watching your videos from time to time really helps me to improve. In this one I just watched your explanation to the concept to 03:20 and I can complete my code. Your ability of problem analysis and explanation of key points slowly has a significant influence to my brain, thank you!
Thank you sir for such an informative and simple video. Have a great day ahead!
Best explanation, clear enough to understand, really helps!
I'm in awe! Thank you for the clear explanation!
@jeff pentagon lol
Yeah... that's some good intuition... even with them all on a number line like that, well, when I was going through this problem, my intuition wasn't finding the start of each range, but how I can iterate through the numbers and building/merging ranges without knowing or caring what is the start or end. I came up with a range merging solution using a HashMap (map[lowBound]=highBound and map[highBound]=lowBound) but later found out there were some corner cases requiring using a set (for duplicate numbers in the array). Same complexity in time and space, but constant factor makes the range merging approach slower. Fantastic approach in this video.
Wow !!!!! Awesome !!! What a solid and through explanation !!! Fantastic !!
Isn't this an O(n²) solution. Since we access elements in the set n times.
I understand lookup is 0(1) but it is done n times, does that not make it O(n) x O(n). especially in the case when the longest subsequence is the entire array?
Nope it 2n. Books down to n
yes, this looks like o n^2.
Its definitely not O(n) but I think a bit less than O(n^2)
If you give it a sorted array like [1, 2, 3, 4], then your runtime is O(n) for the first element + O(n-1) for the second + O(n-2) + ... O(1). I don't know the recurrence for that lol but I think you can use masters theorem to figure it out
A workaround I thought of is to create a second set of numbers that are already in a sequence so you can skip over them, but Im not sure that gets you down to O(n)
Edit: I was wrong
In the case of [1, 2, 3, 4], only 1 is the start of a sequence so it will run through the whole array so O(n) for the first value, but since the rest of the values aren't the start of a sequence (which is determinable in constant time), they will take O(1) time each. That is, only elements that are the start of a sequence end up iterating over their whole sequence, and there is no overlap over sequences, so it boils down to O(2n) or O(n)
This question finally "clicked" for me. Thank you so much!
Very good explanation! Thanks for the video!
You are a genius! You explained a Hard problem like it was nothing!
thank you this makes so much sense when you draw it out
Thank you for clear expalantion and the best solution. You do a great job. Keep moving
very clear solution with time complexity explained, thanks for sharing!
the more I learn from you, the more I'm amazed by your explanations!
your explanations make Hard and Medium problems look Easy level problems!
how the hell am I gonna even think of the idea behind solving a question like this in an interview im cooked
We share a common stress 😑😑
Great solution! Thanks.
Brother you gotta warn me before flashbanging with the light theme.
Cool video as always. Can finally mark the Array section as completed in Neetcode 150 now ✅
Ths graph is a very good explanation on why we need to look for nums-1 in the hash set / set.
I don't understand how time complexity is O(n) in solution you used two nested loops so it should be O(n^2). Please explain?
If a number is part of a sequence, it'll visited at most twice. If a number is only a sequence of itself, it'll be visited once. So time complexity = O(2n) = O(n).
@@danny65769 if we go by nested loop logic then yes, TC appears to be quadratic but your comment made it clear that it would actually be linear. Thanks.
Best explanation ever, thank you!
I am wondering how you can come up with such nice intuitive, easily understood solution without using any fancy algorithm to explain! Kudos!
no wonder he got into GOOGLE
Thank you for solving and explaining it in an intuitive way!
The goat always coming thru with the awesome explanations!
Just starting out so please excuse the dumb question but why is it not O(n^2) or O(n^3) since there are 3 steps with O(n) time complexity?
1. creating a set from the nums list
2. iterating over each element in the nums list
3. in the worst case, the while loop can run for the entire length of the consecutive sequence
Thank you
1. takes O(n) time
2. takes O(n) time
3. takes O(n) time
Since 1 and 2 will run only once, and 3 will only traverse through the original nums array at most, our time complexity is O(n) + O(n) + O(n) = O(3n). But since constants are dropped in Big O notation, we just say the time complexity is O(n).
If we instead used an algorithm where we did step 3 for each element in the nums array, we would have O(n^2). But we know that will never happen because we only go to step 3 when n, an element in nums, is the start of a consecutive sequence because we check if (n - 1) is already in our set.
Guys, could someone please explain what time complexity does converting Array to a Set operation has? It seems to me that it's not O(1), it's most likely O(n). In previous comments Sahil Dhawan mentioned that operations that come after the Set creation, are actaully cost O(2*n). Adding this to the initial Set conversion, we get O(3*n). Which is still O(N), but I think it's good to understand the details
The language is just a spec, so to understand what the time complexity of set(array) is you'd have to check the source code of the Python implementation or whatever programming language you're using.
If you're doing this just for the sake of LeetCode, think intuitively. Imagine that you wrote the set(array) function, how would you do it? The simplest way I can think of it is by using a HashMap, where inserts are O(1). There would be an O(1) insert operation for each element in the array, so therefore the answer to what the time complexity is of set(array) is O(n), since there are n elements in an array.
Good question.
Thank you so much. your videos are just great!
Superb explanation.. Thanks for this video
Good solution. Thank you for the explaination.
just a note: it is worth doing your loop (line 6) over your set (i.e. non-duplicate values) instead of looping through nums that might contain duplicates.
for i in numSet
this is huge, this can reduce your runtime significantly. I didn't do this at first and it beat 28% but after changing to iterating on set it beat 85%
@@huckleberryginesta7941 i wouldn't even always trust the notation since my O(nlogn) solution runs at 346ms while the optimized O(n) solution runs at 768 ms
same, i had to switch it from nums to num_set. Idk how he got 87% using nums😂
@@SteeleJackson2 the problem apparently used to have shorter test cases, now they have ones with hundreds of duplicate zeroes in them
Hats off! just love all these explanations you do for such problems. Just one question, how can one develop such skills to look at the problems from different perspective?
I don't think this is a linear time situation. Worst case time complexity is O(n^2)
Assume input array is [n,n-1,n-2,...3,2,1],
Every iteration takes i iterations to complete index. So overall time is 1 + 2 + 3+...n = O(n^2) for this example.
Worst case complexity is O(n^2) and not O(n)
To make it a O(n)solution ,you would need two hashmaps (map_start_to_end ,map_end_to_start) and hashset (To find if element is already in array.
You just convinced me to go back to pen and paper when solving anything ( not just programming).
One improvement is to have a separate set to track all the visited num, marking the num+1 visited in the inner while. Doing this will allow us to skip the item in the outer for-loop.
Could you explain pls what you mean
They swapped it from hard to medium, and it makes sense because the previous NeetCodes that were medium I could not manage to do them, this one supposed to be hard in the past I managed to do it (obviously not as well as you did) with an HashMap and an HashSet to store booleans and seen numbers
Nice Solution. Explanation of the linear time if its not clear right away.
Though the solution may look like quadratic due to the while loop inside the for loop, the while loop only gets executed at the start of a sequence when (n-1) is not found in the set. Worst case for a sorted array, the first pass will run the while loop (n-1) times, but all other run it will not get executed at all. so the while loop will only run a total of n times for the entire length of the solution.
so the complexity is O(n+n) which is O(n)..
Hope this helps
For a sorted array it would be great but how about something like (10, 9, 8, ... 0) wouldn't this be O(n^2)?
Super clear solution, but you can actually change the for loop: for n in nums --> n in numSet to avoid looping duplicates
This allows the test with a bazillion zeroes to pass in time, too...Nice, simple optimization
It was very helpful. Thanks!
This solution gave me a TLE with Ruby. Instead of iterating over the nums array, I changed it to iterate over the set and that fixed my issue.
Nicely explained this hard problem.
Sir ,You made problem very simple . Neat and clean explanation!!
Wow, once you explained it I understood it immediatly!
Looks like time complexity is O(n*k) where k is the length of longest seq. When k = n then it is O(n2), right?
No because of the "(n - 1) not in subSet" statement. It won't run the while loop if it is not a start of a sequence
Great explanation, I love watching your channel
Just WONDERFUL, I am AMAZED
thanks for the explanation, it was easier to understand.
One optimization can be made is to loop over the numSet instead of the whole array num, consider you have an array looks like [0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5], 0 will be visited 8 times and each time it has to check the following consecutive sequence 5 times! which seems more than O(n) operation.
is the time complexity not O(n * m) ?
Ok i got it ... it will be O(n * m) only
if m < n then it will be O(n) eventually
but if m = n then it will be O(n^2)
where m is no. of operations inside that while loop
and m will never be > n
so ig for the above alogrithm best case would be O(n) and worst will be O(n^2) [i.e when longest seq is equal to length of the given array]
correct me if i am wrong
I was trying to come up with a really space inefficient solution, where I would store all the neighbours of a number in a HashMap, and then recursively find how many neighbours each number has. Can't believe it was so simple!
anaha same
7:34 , doesn't converting a vector(or list) to set take n-square time complexity???
clean explanation . thanks
I like the way he talked about this problem, like so nonchalantly
You're God level! Best wishes for you mate!
Bruh I was in this for like 2 hours and got it done and then looked at how much easier u broke this down I will keep this in mind thank you 🦍
It will be more efficient to iterate through numSet instead of nums.
Very clear explanation though, thanks a lot.
Soothing voice, clear explanation, and most importantly, drawing these beautiful graphs with a mouse (cuz I heard the clicks)... God, can you make a more perfect guy than this?
There's no way I ever would have thought of that number line strategy on my own. No wonder why I was struggling to do this in less than O(nlog(n)) time before watching this video.
such a smart solution
totally loved your explanation
Super helpful! Thank You:)
bro you are genius !!
Awsome! Thank you so much!
Thank you for such concise explanation. Just one query:
Instead of using:
for n in nums:
won't it be better if we use:
for n in numSet:
Cause if we traverse through nums it will check the condition of repetitive numbers also
That's how I coded after seeing his drawing explanation..
[1,2,2,3,3,4] is still considered a consecutive sequence, if you loop through the set you won’t compute the right sequence since Sets don’t allow duplicates.
@@aminafounoun it should be [1,2,3,4] not [1,2,2,3,3,4], so loop through the set is correct
Great video, as usual! (Java) I found it much faster if you use the set when iterating the numbers. Instead of for n in nums, iterate over the set. The set will contain fewer items/remove duplicates. Thank you!
This is very true ... I just tried this and the runtime for all the test cases in leetcode was about 4 times less than iterating over the whole "nums" list.
set = 409ms
list = 2843ms
@@kofinartey6348 I can confirm the same.
There is no need to check duplicates when we are trying to find the longest sequence.
You should also remove the current number from the set so that I won't be checked again making the solution actually O(n). Please correct me if there's any flaw in my understanding.
best explanation ever !
Hi! Thanks for the awesome content. My question is, why not use a Map with O(1) access, and we can use the map value to mark the elements we have already checked to shorten the loop:
e.g 1,2,3,4,100,200:
when we 1st check 1->2->3->4, no need to then check 2, 3 and 4 again
good idea! I think thats actually necessary to keep the runtime in O(n) because if we - in worst case - check the entire array for every number to find out if there is there is a left neighbor the complexity is O(n^2) in my opinion.
I can't believe this way is available, thank you :>
Hello SIr ! Thank you for the explanation. I just had a question. The inner while loop , how is it not increasing time complexity?
the inner while loop only runs when it is the first element in the sequence, hence the number of iterations of inner while loop for all outer loops totals up to N iterations. therefore, the time complexity is still O(N)
@@TheGuywithnolife A better explanation would be each element will only be looked up for at most 2 times, despite the 2 loops. Once if it is start of a sequence. Otherwise twice if it is part of a sequence. hence worst time complexity would be O(2n) which is O(n)
@@TheGuywithnolife thank you, well explained 🌸🌸
FYI : why is this still O(N)?
Unique Starting Points: The while loop only starts for numbers that are the beginning of a new consecutive sequence. Not every number in the list will be the start of such a sequence. In fact, most numbers won't be, especially in longer sequences.
Each Number Processed Once: As the while loop runs, it processes each number in a consecutive sequence exactly once. Once a number has been included in a sequence, it won't trigger the while loop again in future iterations of the for loop, because it will no longer be the start of a new sequence (its predecessor will be in the set).
Total Work is Proportional to N: Even though there's a loop inside a loop (which often suggests O(N^2) complexity), the total amount of work done by the inner while loop across the entire execution of the function is proportional to the number of elements in the list. Each element gets a turn to "extend" a sequence, but only if it's the start of a new sequence. After it has been part of a sequence, it won't contribute to further inner loop runs. Therefore, the total work done by all runs of the inner loop adds up to linear work in relation to the number of elements.
but if nums = [1,2,3,4,5,6,7,8].for loop runs 8 times. Inner while loop also runs 8 times right = n2?
This is a great explanation , I was able to come up with a more efficient approach - combining it with your method as well:
def longestConsecutive(self, nums: List[int]) -> int:
numSet = set(nums)
longest = 0
for n in nums :
if (n-1) not in numSet:
length = 1
while(n+1) in numSet:
n = n+1
length = length+1
numSet.remove(n)
longest = max(length,longest)
return longest
By doing so , we're removing the n+1 element from numSet and counting the length as well, inclusive of this element, thus we are decreasing the size of numSet and speeding up the search to check an entry in numSet. And once we find the start of any sequence we know that the length of that sequence is 1, because of that element.
Another way to do it is to blow up your set as you go, and not worry about starting at the beginning of a sequence. For each number that you get to, if it's still in the set, remove it from the set, then count how many numbers are in a sequence with it above it, removing them from the set as you go, then do the same for numbers below it. You will count through a sequence and remove all elements of that sequence from the set at the same time, so when your loop iterates to an element that was already part of a sequence, it can just pass.
can you show your code here
I did exactly this and it's exceeding the time limit in Java
you made a complicated process looks so simple. thanks for the explanation and approach
Wouldn't checking the hashmap be O(logN) complexity? so minimum O(nlog(n))? Pretty much same as sort and going through it?
sets when they are not ordered have O(1) average operation time complexity
Wow what a simple break down. I derived my own O(n) runtime solution but my code was way more complicated and involved storing ranges in a dictionary. In my experience when I am struggling to implement the code of the solution, I most likely didn't do it in the best way. But a solution that works (and in the expected time) is better than nothing at all probably. Anyways great video!
Thanks!! Awesome guy
next time i will watch your video before reading the editorial since you show the thought process so maybe I will figure it out before its laid out
Awesome, thanks!