🚀 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"
@@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
@dev stuff 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)
@@ilyes914 No, the inner loop will iterate only once for the number 1, that's O(n), and then starting from the number 2, the inner loop will no longer iterate, so that's O(n) + O(n), which is O(n)
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
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.
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
@@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).
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 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.
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!
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!
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.
I think im getting a little better at coding thanks to you. When i watched halfway suddenly the actual code came to mind and I was able to solve it. Eureka moment for me as this is the first time thats ever happened. Thank you man :)
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.
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
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
@@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
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.
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.
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 ✅
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!
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!
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!
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.
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
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.
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.
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.
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?
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)
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'm not sure about your result as I'm calculation O(n^2), maybe I'm missing something but: - The outer for loop iterates over the numSet, which contains n elements. This is O(n). - Inside each iteration of the for loop, we first do a constant time O(1) check for (n-1) not in numSet. - Then, we have the while loop, which in the worst case could iterate for the entire length k of the longest consecutive sequence. Since k can be up to n in the worst case, this while loop is O(n) for each iteration of the outer loop. Therefore, each iteration of the outer loop is O(1) + O(n) = O(n) Multiplying the O(n) iterations of the outer loop by the O(n) work inside each iteration, we get O(n) * O(n) = O(n^2) total time complexity. where am I wrong with that?
imagine the worse case scenario type list like [9,8,7,6,5,4,3,2,1]. you loop through the entire list once and don't find the start of the sequence until you hit the end. in the while loop, you loop through the entire list again. this isn't O(n^2) but 2 * O(n) which is just O(n). correct me if im wrong plz
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
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
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.
This seems like it could be O(n^2) in stead of O(n). The internal while loop could run for effectively n-1 times for every number as the list grows to infinity. And the for loop is O(n). So worst case its n(n-1) which is n^2 right?
If the internal loop has to run n-1 times it means you have only one sequence (only one number doesn't have a left neighbour). So it will be approximately O(2n) = O(n), never O(n^2)
As someone who watched all your previous 75 Teamblind questions, I have a feeling that you were preety sad while making this video. I hope everything is good now :)
not sure if he already landed at google, but he mentioned that he was unemployed before that. I'm glad he's at google now. Well deserved. This guy has changed my coding journey. :)
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
[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.
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?
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)
Hi! Thank you for all your videos! Btw, why is the time complexity O(n) tho, what about the while loop that is IN the for loop? Doesn't that add onto the time complexity? Thank you in advance!
@@dodziraynard Yeah so if the while loop executes once per number and each number gets executed once in the for loop wouldn't this be O(n^2)? Worst case scenario each number doesn't have anything on its left hand side which means on every number in the for loop it has to go through every number in the set. Wouldn't this solution have O(n^2) complexity?
@@anhngo581 Hi, I am still confused but the outer for loop will go over the rest of the numbers right and then figure out there is a left number for them. Example [3,2,4,5,1,6,8,7]. Outer for loop runs for every number ( n times) and inner while loop also runs n times right?
@@snehakandukuri429 hi sneha, good question. If a number is part of a sequence, the "if (n-1) not in numSet" returns false so the inner loop won't run at all. You can also see it in the video at 6:00. In your example [3,2,4,5,1,6,8,7], the inner loop won't run until it's checking 1. Because 0 doesn't exist in that set, 1 is the start of a sequence, and so the inner loop will run and calculate the length of that sequence.
As example suggested we have to iterate through the whole list one by one which will provide us the complexity of 'O(n)' and checking for the next number for each next number we are getting complexity of 'log n'. So the question is does the iteration in the set will count in while calculating the complexity or not? Also, use of While look will increase the complexity
"use of while look will increase the complexity" well yes but actually no, the while loop only runs if we have identified the start of a sequence. Not every number is the start of a sequence. Like in the input of 100,4,200,1,3,2; for the numbers 2,3,4, the while loop isn't run at all also, in the vid, he said that every number will be visited at most 2 times. While I think it is at most *3 times, the overall time complexity is still O(n)
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.
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!
No since, we will only touch each element twice. The while loop only touches one sequence and all of the sequences together make up one array, thus for loop touches each element once, and while loop once more. 2 * n which is O(n)
I see what you mean, this is avoided by having the if statement that checks if lower num in sequence doesn't exist first before getting into the while loop, so time is linear because the if condition can only be met 1 time for a given sequence
The second loop only runs for the starting indices of each sequence, not for every single index! It loops through each sequence only once. It never runs through the same sequence twice. So, both the inner loop and the outer loop run O(n) times in total which gives us a time complexity of O(2n), and since we can drop the constants we can write it as O(n).
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.
This is a much underappreciated, important comment! The Leetcode test cases as of August 2023 now time the Neetcode solution at around 1500ms in Python3. By iterating over the set, instead of the nums array, that reduces to around 350ms. Clearly the test cases contain a LOT of duplicates/duplicate sequences. Great comment, thank you!
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.
I think this is because we are definitely not checking every number (1 to n) against the current number (n). If this was the case, it would have been O(n*n). In video example, we are checking 'm' numbers, where m is subset of n. So it could have been O(m*n). But it is also mentioned in the video, we will go through a particular numbers at most 2 times- 1) When checking left neighbour 2) When checking in Set for creating sequence. So this makes it n *2 times, thus O(2n)
In the case that every number in the set is consecutive, we'd be going through it 3 times total, if not it's somewhere inbetween 2 and 3 times. So O(3N) -> O(N) worst case
Thank you for the video! Neet explanation I have 2 questions 1: what's the reasoning behind using the hashset? 2: how does this approach achieve O(n)? For number 2, I have seen some explanations in comments. I see mentions of the set being a subset of the array, and like if the longest sequence is one, then all elements require going through the while loop only once, thereby yielding O(n). However, it still does not click.
Basically the inner loop runs as many times as number of sequences with length same as that of the sequence. So if the inner while loop has length of n - 1, meaning the whole array is a single sequence then it only runs once (for the starting value) for the outer for loop. Or if every element is a new sequence then while has a length of 1 for each run of the for loop.
@@akash4393 Yeah so if the while loop executes once per number and each number gets executed once in the for loop wouldn't this be O(n^2)? Worst case scenario each number doesn't have anything on its left hand side which means on every number in the for loop it has to go through every number in the set. Wouldn't this solution have O(n^2) complexity?
If the given input was in reverse order, say [10,9,8,7,6,5,4,3,2,1,0], then this approach will be like 10 9 -> 10 8 -> 9 -> 10 7 -> 8 -> 9 -> 10 goes on 0 -> 1 -> ... -> 10 And it takes O(n logn) i guess Rather than using set, take map to save its length like {startIndex: length} and if (num[i]+1) key exists in map means, intake its length.
@@ktrize3084 for this instance it is 2n. consider the worst case [5,4,3,2,1]. you will go across the array 5->1(n). when you get to one, you will iterate from 1->5 (n). for it to n^2, it needs to iterate through each element in the array, and for each element have a nested loop. in our example: This is not the case. It's only the case for the value 1 (index 4)
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.
Popping from a heap is a log(n) operation. So in the worst case you would be performing a log(n) operation for each item of the array O(n). In other words O(nlog(n)).
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.
I think they added additonal test cases for this question which gives Time Limit Exceed error and 68/76 testcases pass. I think the reason why we get that error is because it does an inner while loop for n+length, so it's more like O(nk) where k is max length, which is likely similar to O(nlogn).
Seems like a good solution. For some reason the visualization is not making it clearer for me. Will just have to implement it and see! Was doing the sorting solution and it broken when I didn't consider duplicate items, and I fixed that by using a Set, so seems like I was on the right track there. Thanks for these helpful resources!
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?
Thanks for the solution but I just had 4-5 ads so popup, can you please decrease the number of ads in one video? I have ADD and it's really hard to get back to the explanation after. I do appreciate all you do but just wanted to offer my perspective.
@NeetCode - thank you for making this video and teaching us how to solve this problem. I have one question for the time complexity. Would it be O(n^2) and not O(n)? Because let's say we have [1,2,3,4,5]. in this case for loop will run n times and while loop will also n times making it the worst case scenario. Is my understanding correct or am i missing on something? thanks a ton again! @others - please also share your thoughts on this. Thanks in advance!
Little bit of change in code can make it more efficient. public int longestConsecutive(int[] nums) { Set set = new HashSet(nums.length); int count = 1; int maxCount = 0; for(int i = 0; i < nums.length; i++){ set.add(nums[i]); } for(int i = 0; i < nums.length; i++){ if(set.contains(nums[i])){ boolean run = true; int forward = nums[i] + 1; int backward = nums[i] - 1; count = 1; while(set.contains(forward)){ set.remove(forward); forward++; } while(set.contains(backward)){ set.remove(backward); backward--; } maxCount = Math.max(maxCount, forward-backward-1); } } return maxCount; }
🚀 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
@dev stuff 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)
@@ilyes914 No, the inner loop will iterate only once for the number 1, that's O(n), and then starting from the number 2, the inner loop will no longer iterate, so that's O(n) + O(n), which is O(n)
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.
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!!
Very clear explanation with illustrations without jumping into the code immediately. One of me favorite channels.
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.
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.
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]
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
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!
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!
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 think im getting a little better at coding thanks to you. When i watched halfway suddenly the actual code came to mind and I was able to solve it. Eureka moment for me as this is the first time thats ever happened. Thank you man :)
Your explanations always help! Interesting that Leetcode has downgraded this problem to medium now.
This is the BEST explanation on the entire Internet! Awesome!
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.
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👏
Incredible explanation, so simple when you know to look at the left neighbor, and awesome walkthrough. Keep it up!
Your solutions are so intuitive. Thanks for making these videos!
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)?
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
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.
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.
Really awesome explanation, thank you! I am able to code it up just by following your drawing
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
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 ✅
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!
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
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
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!
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.
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 think you are right
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.
@@bellxlilies9913 thank you!
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.
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
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)
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'm not sure about your result as I'm calculation O(n^2), maybe I'm missing something but:
- The outer for loop iterates over the numSet, which contains n elements. This is O(n).
- Inside each iteration of the for loop, we first do a constant time O(1) check for (n-1) not in numSet.
- Then, we have the while loop, which in the worst case could iterate for the entire length k of the longest consecutive sequence. Since k can be up to n in the worst case, this while loop is O(n) for each iteration of the outer loop. Therefore, each iteration of the outer loop is O(1) + O(n) = O(n)
Multiplying the O(n) iterations of the outer loop by the O(n) work inside each iteration, we get O(n) * O(n) = O(n^2) total time complexity.
where am I wrong with that?
because the while loop only runs if the number is at the start of the sequence
imagine the worse case scenario type list like [9,8,7,6,5,4,3,2,1]. you loop through the entire list once and don't find the start of the sequence until you hit the end. in the while loop, you loop through the entire list again. this isn't O(n^2) but 2 * O(n) which is just O(n). correct me if im wrong plz
explanation at it best! I just coded it up with such a flow after you clarified the problem
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
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
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.
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
This seems like it could be O(n^2) in stead of O(n). The internal while loop could run for effectively n-1 times for every number as the list grows to infinity. And the for loop is O(n). So worst case its n(n-1) which is n^2 right?
If the internal loop has to run n-1 times it means you have only one sequence (only one number doesn't have a left neighbour). So it will be approximately O(2n) = O(n), never O(n^2)
You just convinced me to go back to pen and paper when solving anything ( not just programming).
As someone who watched all your previous 75 Teamblind questions, I have a feeling that you were preety sad while making this video. I hope everything is good now :)
yeah. I was also thinking the same
yup :(
@@cosepeter2197 why sad?
not sure if he already landed at google, but he mentioned that he was unemployed before that. I'm glad he's at google now. Well deserved. This guy has changed my coding journey. :)
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
I'm in awe! Thank you for the clear explanation!
@jeff pentagon lol
You are a genius! You explained a Hard problem like it was nothing!
7:34 , doesn't converting a vector(or list) to set take n-square time complexity???
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?
Ths graph is a very good explanation on why we need to look for nums-1 in the hash set / set.
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.
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 🌸🌸
It will be more efficient to iterate through numSet instead of nums.
Very clear explanation though, thanks a lot.
Thank you for solving and explaining it in an intuitive way!
i love the way you explain the algorithm. Appreciate your efforts.
I like the way he talked about this problem, like so nonchalantly
Hi! Thank you for all your videos!
Btw, why is the time complexity O(n) tho, what about the while loop that is IN the for loop? Doesn't that add onto the time complexity?
Thank you in advance!
Think of it this way: how many times will the while loop execute for each number, once due to the if condition before the loop right? So it's linear.
@@dodziraynard Yeah so if the while loop executes once per number and each number gets executed once in the for loop wouldn't this be O(n^2)? Worst case scenario each number doesn't have anything on its left hand side which means on every number in the for loop it has to go through every number in the set. Wouldn't this solution have O(n^2) complexity?
@@ktrize3084 worst case scenario each number doesn't have anything on its left hand side, then the while loop only run once per number => still O(n)
@@anhngo581 Hi, I am still confused but the outer for loop will go over the rest of the numbers right and then figure out there is a left number for them. Example [3,2,4,5,1,6,8,7].
Outer for loop runs for every number ( n times) and inner while loop also runs n times right?
@@snehakandukuri429 hi sneha, good question. If a number is part of a sequence, the "if (n-1) not in numSet" returns false so the inner loop won't run at all. You can also see it in the video at 6:00.
In your example [3,2,4,5,1,6,8,7], the inner loop won't run until it's checking 1. Because 0 doesn't exist in that set, 1 is the start of a sequence, and so the inner loop will run and calculate the length of that sequence.
As example suggested we have to iterate through the whole list one by one which will provide us the complexity of 'O(n)' and checking for the next number for each next number we are getting complexity of 'log n'.
So the question is does the iteration in the set will count in while calculating the complexity or not?
Also, use of While look will increase the complexity
"use of while look will increase the complexity"
well yes but actually no, the while loop only runs if we have identified the start of a sequence. Not every number is the start of a sequence.
Like in the input of 100,4,200,1,3,2; for the numbers 2,3,4, the while loop isn't run at all
also, in the vid, he said that every number will be visited at most 2 times. While I think it is at most *3 times, the overall time complexity is still O(n)
Could you explain why do we need to make nums to be a set?
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 😑😑
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.
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 🦍
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!
you made a complicated process looks so simple. thanks for the explanation and approach
Why is this considered a O(n) solution when there is a while loop running inside a for loop! shouldn't this be O(n^2).
No since, we will only touch each element twice. The while loop only touches one sequence and all of the sequences together make up one array, thus
for loop touches each element once, and while loop once more. 2 * n which is O(n)
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
I see what you mean, this is avoided by having the if statement that checks if lower num in sequence doesn't exist first before getting into the while loop, so time is linear because the if condition can only be met 1 time for a given sequence
This question finally "clicked" for me. Thank you so much!
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!
Sir ,You made problem very simple . Neat and clean explanation!!
Very clear video NeetCode! However I'd like to know why you say this solution is O(n) when we clearly have 2 loops ?
The second loop only runs for the starting indices of each sequence, not for every single index! It loops through each sequence only once. It never runs through the same sequence twice. So, both the inner loop and the outer loop run O(n) times in total which gives us a time complexity of O(2n), and since we can drop the constants we can write it as O(n).
Best explanation, clear enough to understand, really helps!
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.
Line 6 could be for n in numSet. Excellent solution. Your videos are helping change the way I think - thankyou
This is a much underappreciated, important comment! The Leetcode test cases as of August 2023 now time the Neetcode solution at around 1500ms in Python3. By iterating over the set, instead of the nums array, that reduces to around 350ms. Clearly the test cases contain a LOT of duplicates/duplicate sequences. Great comment, thank you!
thank you this makes so much sense when you draw it out
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.
does line 10 (while loop) make it longer than O(n)? And if not can you explain why? Thank you very much for these vids
The inner while loop makes it O(2n) but we don't consider constants for big-O analysis so it's just O(n).
@@johns3641 why is the while loop not O(n)?
I think this is because we are definitely not checking every number (1 to n) against the current number (n). If this was the case, it would have been O(n*n). In video example, we are checking 'm' numbers, where m is subset of n. So it could have been O(m*n). But it is also mentioned in the video, we will go through a particular numbers at most 2 times-
1) When checking left neighbour
2) When checking in Set for creating sequence.
So this makes it n *2 times, thus O(2n)
In the case that every number in the set is consecutive, we'd be going through it 3 times total, if not it's somewhere inbetween 2 and 3 times. So O(3N) -> O(N) worst case
I have not seen this idea in comments. Adding this check at the end of for loop will help a bit.
if longest > len(nums) // 2:
break
bro you are genius !!
very clear solution with time complexity explained, thanks for sharing!
Thank you for the video! Neet explanation
I have 2 questions
1: what's the reasoning behind using the hashset?
2: how does this approach achieve O(n)?
For number 2, I have seen some explanations in comments. I see mentions of the set being a subset of the array, and like if the longest sequence is one, then all elements require going through the while loop only once, thereby yielding O(n). However, it still does not click.
Thank you sir for such an informative and simple video. Have a great day ahead!
How is it linear time if there are nested loops (for and while)?
Basically the inner loop runs as many times as number of sequences with length same as that of the sequence. So if the inner while loop has length of n - 1, meaning the whole array is a single sequence then it only runs once (for the starting value) for the outer for loop. Or if every element is a new sequence then while has a length of 1 for each run of the for loop.
@@akash4393 Yeah so if the while loop executes once per number and each number gets executed once in the for loop wouldn't this be O(n^2)? Worst case scenario each number doesn't have anything on its left hand side which means on every number in the for loop it has to go through every number in the set. Wouldn't this solution have O(n^2) complexity?
If the given input was in reverse order, say [10,9,8,7,6,5,4,3,2,1,0], then this approach will be like
10
9 -> 10
8 -> 9 -> 10
7 -> 8 -> 9 -> 10
goes on
0 -> 1 -> ... -> 10
And it takes O(n logn) i guess
Rather than using set, take map to save its length like {startIndex: length}
and if (num[i]+1) key exists in map means, intake its length.
I was thinking this, and I don't think it's O(nlogn) it's O(n^2) since worst case the it's O(n(n-1)) or O(n^2 - n)
@@ktrize3084 for this instance it is 2n. consider the worst case [5,4,3,2,1]. you will go across the array 5->1(n). when you get to one, you will iterate from 1->5 (n).
for it to n^2, it needs to iterate through each element in the array, and for each element have a nested loop.
in our example: This is not the case. It's only the case for the value 1 (index 4)
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.
What if we heapify the whole array and then pop elements one by one and track the longest sequence?
Time complexity: heapify O(n) + pop O(n) = O(n)
Popping from a heap is a log(n) operation. So in the worst case you would be performing a log(n) operation for each item of the array O(n). In other words O(nlog(n)).
great video. You can loop through the set instead of the list to speed it up. "for n in numSet"
Yeah thats what I was also thinking , it saves a lot of time if duplicates are involved
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.
I think they added additonal test cases for this question which gives Time Limit Exceed error and 68/76 testcases pass. I think the reason why we get that error is because it does an inner while loop for n+length, so it's more like O(nk) where k is max length, which is likely similar to O(nlogn).
Seems like a good solution. For some reason the visualization is not making it clearer for me. Will just have to implement it and see! Was doing the sorting solution and it broken when I didn't consider duplicate items, and I fixed that by using a Set, so seems like I was on the right track there. Thanks for these helpful resources!
Thank you for clear expalantion and the best solution. You do a great job. Keep moving
The goat always coming thru with the awesome explanations!
Nicely explained this hard problem.
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?
Thanks for the solution but I just had 4-5 ads so popup, can you please decrease the number of ads in one video? I have ADD and it's really hard to get back to the explanation after.
I do appreciate all you do but just wanted to offer my perspective.
@NeetCode - thank you for making this video and teaching us how to solve this problem. I have one question for the time complexity. Would it be O(n^2) and not O(n)? Because let's say we have [1,2,3,4,5]. in this case for loop will run n times and while loop will also n times making it the worst case scenario. Is my understanding correct or am i missing on something? thanks a ton again! @others - please also share your thoughts on this. Thanks in advance!
Little bit of change in code can make it more efficient.
public int longestConsecutive(int[] nums) {
Set set = new HashSet(nums.length);
int count = 1;
int maxCount = 0;
for(int i = 0; i < nums.length; i++){
set.add(nums[i]);
}
for(int i = 0; i < nums.length; i++){
if(set.contains(nums[i])){
boolean run = true;
int forward = nums[i] + 1;
int backward = nums[i] - 1;
count = 1;
while(set.contains(forward)){
set.remove(forward);
forward++;
}
while(set.contains(backward)){
set.remove(backward);
backward--;
}
maxCount = Math.max(maxCount, forward-backward-1);
}
}
return maxCount;
}
I got this question in my Google interview I was so happy lol😅
yay happy for you! how did it go? was that for your initial interview?