Leetcode 128 - LONGEST CONSECUTIVE SEQUENCE

[@NeetCode]

🚀 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]

Can you explain how this code time complexity is O(n), coz I see inner loop.

[@MrHarryGaming]

@@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

[@gugolinyo]

@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.

[@ilyes914]

@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)

[@imaginebreaker2414]

@@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)

[@shashankmishra484]

Leetcode watched your explanation and switched this question from 'hard' to 'medium' :D

[@bsguru84]

LOL

[@stardust3579]

I also noticed 🤕

[@starlingroot]

😂😂

[@user-pp3zp5hq1x]

True XD

[@ajayreddy9219]

leetcode thought they pulled a sneaky on us. but they know only half about us.

[@wh264]

Very clear explanation with illustrations without jumping into the code immediately. One of me favorite channels.

[@NeetCode]

Thanks!

[@zakgeddes5560]

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.

[@Saotsu1]

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

[@div0007]

Nice observation my dude. It's almost hilarious how much the running time improved with a small change. Thanks.

[@qwertmom]

Makes sense. I was wondering why it was taking so long to run

[@lokeshrmitra]

My java solution changed from 1104ms to 28ms with this change. Thanks!

[@DrPwn-jl8ly]

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!!

[@abudhabi9850]

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

[@steveohbandito]

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!

[@protogionlastname6003]

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.

[@dabocousin]

"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

[@abudhabi9850]

@@dabocousin depends on the occasion. If there are a lot of duplicates, then it makes a big difference.

[@atmadeeparya2454]

Thanks a lot. I was facing TLE and this solved it. Kudos mate.

[@ghostvillage1]

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.

[@aaqibjavedz2569]

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.

[@sawyerburnett8319]

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.

[@premjeetprasad8676]

@@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.

[@ameetmonty]

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

[@ktrize3084]

For a sorted array it would be great but how about something like (10, 9, 8, ... 0) wouldn't this be O(n^2)?

[@saravanaavelpari7713]

I was wondering , thanks for the explanation

[@brecoldyls]

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!

[@andrewfakhry3943]

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."

[@luisady8990]

So are hashtables just called sets in python? similar to how arrays are called lists?

[@andrewfakhry3943]

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.

[@luisady8990]

@@andrewfakhry3943 ty!

[@tsevibright7323]

But since the worst case for a lookup is O(n), doesn’t that make this O(n^2)?

[@omarelnaggar9940]

thx man, I appreciate this note cuz i was so confused

[@johnvanschultz2297]

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.

[@fwan0697]

Same!!

[@Milan-vi1bq]

wouldnt that make you feel worse?? lol

[@liam6335]

same

[@EE12345]

should feel worse, this means old Hards are becoming Mediums and new Hards are even harder now lol.

[@fwan0697]

@@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.

[@halcyonramirez6469]

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!

[@Tobias-bv8yc]

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.

[@hwang1607]

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

[@del6553]

@@hwang1607 If two sequences have the same number, that means they are parts of one complete sequence.

[@911wasaninsidejob]

Thank you ! This help with runtime quite a lot. But I'm still struggling with the deletion part as it messes up the iterator

[@rhosymedra6628]

Your explanations always help! Interesting that Leetcode has downgraded this problem to medium now.

[@brent78900]

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.

[@nisargshah9861]

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

[@troyjones9344]

This. If this was O(n), every sorting algorithm where space is not important, would use this behind the scenes.

[@EngineeringComplained]

Yep, iterating through numSet instead of nums takes care of the test with a bazillion zeroes

[@The2Coolest2]

Exactly! I was like this isn't O(n)?

[@javierclement3047]

@@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).

[@Betadesk]

​@@troyjones9344 But it just counts upwards by 1, it wouldnt be performant on an array like [1, 100000000]

[@oleonortt]

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]

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%

[@ask_vfx]

@@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

[@SteeleJackson2]

same, i had to switch it from nums to num_set. Idk how he got 87% using nums😂

[@DankMemes-xq2xm]

@@SteeleJackson2 the problem apparently used to have shorter test cases, now they have ones with hundreds of duplicate zeroes in them

[@ALueLLah]

Super clear solution, but you can actually change the for loop: for n in nums --> n in numSet to avoid looping duplicates

[@EngineeringComplained]

This allows the test with a bazillion zeroes to pass in time, too...Nice, simple optimization

[@sapien153]

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.

[@wanderingcatto1]

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.

[@ryancaldwell6615]

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.

[@philipputkin8236]

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

[@usernamesrbacknowthx]

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.

[@This.Object]

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👏

[@Maverick0813]

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!

[@KH-sf5pu]

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

[@bellxlilies9913]

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.

[@ijaspreet]

@@bellxlilies9913 thank you!

[@syedabdulwahab4729]

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

[@spamonly]

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.

[@rahuldey1182]

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.

[@Josh-ej9zm]

Incredible explanation, so simple when you know to look at the left neighbor, and awesome walkthrough. Keep it up!

[@rishabbhattachaya6676]

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 :)

[@linguisticgamer]

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; }

[@shenzheng2116]

This is the BEST explanation on the entire Internet! Awesome!

[@charliej3624]

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.

[@KostyaZinoview]

Could you explain pls what you mean

[@GreyWinds]

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?

[@nikhil199029]

Nope it 2n. Books down to n

[@prabhatmishra7784]

yes, this looks like o n^2.

[@Betadesk]

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)

[@Betadesk]

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)

[@MrShag23]

@@Betadesk but what about the case [4,3,2,1]

[@Ayanshandseals]

Time complexity : O(n) Although the time complexity appears to be quadratic due to the while loop nested within the for loop, closer inspection reveals it to be linear. Because the while loop is reached only when currentNum marks the beginning of a sequence (i.e. currentNum-1 is not present in nums), the while loop can only run for nnn iterations throughout the entire runtime of the algorithm. This means that despite looking like O(n⋅n) complexity, the nested loops actually run in O(n+n)=O(n) time. All other computations occur in constant time, so the overall runtime is linear.

[@mansimemnagar7654]

7:34 , doesn't converting a vector(or list) to set take n-square time complexity???

[@aryangoyal4495]

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.

[@viniciusmonteiro2514]

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!

[@kofinartey6348]

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

[@cipher01]

@@kofinartey6348 I can confirm the same.

[@cipher01]

There is no need to check duplicates when we are trying to find the longest sequence.

[@fawadaliq]

Your solutions are so intuitive. Thanks for making these videos!

[@goldfishbrainjohn2462]

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!

[@madhumithakolkar_]

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.

[@---el6pq]

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.

[@ankitchaturvedi2941]

can you show your code here

[@brunosdm]

I did exactly this and it's exceeding the time limit in Java

[@SharunKumar]

This improved the performance by a lot! even though its just a one line set.delete (javascript)

[@yu-changcheng2182]

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.

[@bawa1169]

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

[@carloscarrillo201]

That's how I coded after seeing his drawing explanation..

[@aminafounoun]

[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.

[@chenyangwang7232]

@@aminafounoun it should be [1,2,3,4] not [1,2,2,3,3,4], so loop through the set is correct

[@Florent04]

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

[@darya_zi]

Really awesome explanation, thank you! I am able to code it up just by following your drawing

[@kirylbah]

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

[@ngneerin]

In short: add to set. Set count = 0.Iterate, where num-1 not in set. Set curr_count=1. Set n as num. while n+1 is there in set, increment curr_count. Set count to Max of count and curr_count. Return count

[@Oliver-nt8pw]

Ths graph is a very good explanation on why we need to look for nums-1 in the hash set / set.

[@nafisnawalnahiyan5032]

Hello SIr ! Thank you for the explanation. I just had a question. The inner while loop , how is it not increasing time complexity?

[@TheGuywithnolife]

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)

[@meowmaple]

@@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)

[@fufuto]

@@TheGuywithnolife thank you, well explained 🌸🌸

[@ankitdesai496]

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

[@anhngo581]

"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)

[@usernamesrbacknowthx]

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!

[@bree9895]

anaha same

[@Dipubuet]

I am wondering how you can come up with such nice intuitive, easily understood solution without using any fancy algorithm to explain! Kudos!

[@iamnoob7593]

no wonder he got into GOOGLE

[@MAK_007]

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

[@MashedLinux]

I think you are right

[@shubham_poco]

searching for an element in a set is o(1)

[@MrShag23]

@@shubham_poco but you are searching for m elements

[@Betadesk]

@@MAK_007 keep in mind that you only go through that while loop once per sequence, and that sequences don't overlap. You can express n as m1 + m2 ... mk, where m1 the length of the 1st sequence, etc. Since you go through each sequence exactly once, counting the length of every sequence has complexity O(n). O(n^2) would mean that you go through each sequence n times, but you don't

[@guray00]

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?

[@ajkeebs4373]

because the while loop only runs if the number is at the start of the sequence

[@newuser689]

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

[@arda8206]

Hey everyone, I am not sure the following solution does it in O(n): class Solution: def longestConsecutive(self, nums: List[int]) -> int: setNums = set(nums) if len(nums) == 0: return 0 max_count = 1 while len(setNums) != 0: ct = 1 min_of_set = min(setNums) while min_of_set + 1 in setNums: ct = ct + 1 setNums.remove(min_of_set) min_of_set += 1 setNums.remove(min_of_set) max_count = max(max_count, ct) return max_count Do you guys have any ideas?

[@NidraxGaming]

It seems that converting the set back to a list, then sorting it and finally runing a single iteration on that list to determine the longest chain is twice as time-effective as proposed solution of constantly searching for next values in the set (156 ms vs 311 ms) - at least in C#. Proposed solution: ``` public int LongestConsecutive(int[] nums) { if(nums.Length == 0) return 0; var n = new HashSet(nums); int longest = 0; for(int i=0; i

[@kingKabali]

It will be more efficient to iterate through numSet instead of nums. Very clear explanation though, thanks a lot.

[@ashkanbashiri]

great video. You can loop through the set instead of the list to speed it up. "for n in numSet"

[@vishwasaikarnati9099]

Yeah thats what I was also thinking , it saves a lot of time if duplicates are involved

[@vineetbatthina]

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.

[@snehakandukuri429]

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?

[@ahmetcemek]

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).

[@achillestroy3122]

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?

[@danny65769]

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).

[@div0007]

@@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.

[@qingyangzhang6093]

So the key is convert the list nums to.a set. We have a (if n - 1 is in nums) statement nested in a for loop. The if statement has O(n) complexity if nums is a list, but O(1) complexity if nums is a set.

[@3042640426]

Why this method is not O(n * n)? if input is [1,2,3,4,5] We have to iterate once and then nest while loop for calculate consequence. the most bad situation should be O(n^2)

[@danielc4267]

Thank you for solving and explaining it in an intuitive way!

[@Cruzylife]

I was able to code it up once you showed the left neighbor deduction. Genius mister neetcode

[@satyadharkumarchintagunta3793]

Sir ,You made problem very simple . Neat and clean explanation!!

[@andrianarivonirintsoa7051]

Hi NeetCode, it's been a while since you made this video and leetcode updated this problem. This solution won't work using Ruby. Even with python it takes 4+ seconds to execute, and in Ruby, it's timeout. Would appreciate an update to this particular problem. As always, amazing videos NeetCode!

[@davidbuderim2395]

Line 6 could be for n in numSet. Excellent solution. Your videos are helping change the way I think - thankyou

[@endian675]

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!

[@tomonkysinatree]

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!

[@thelonearchitect]

Using a MinHeap it's possible to have O(n) + O(logn) as first pass and then again O(n) + O(logn) over the Minheap to assemble. Meaning O(2*(n+logn)) => O(n). A bit less performant though.

[@safwankhan199]

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.

[@rabbyhossain6150]

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)

[@jacksonprice6324]

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)).

[@ajinkyapahinkar6463]

Recursive Sol: def longestConsecutive(self, nums: List[int]) -> int: hashset_num = set(nums) def dfs(num): if num not in hashset_num: return 0 hashset_num.remove(num) left = dfs(num - 1) right = dfs(num + 1) return 1 + left + right maxLen = 0 for num in nums: maxLen = max(maxLen, dfs(num)) return maxLen

[@sawyerburnett8319]

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!

[@shapethetechworld]

Why this approach is taking more time on Leetcode as compared to the sorting technique? I implemented both solutions in JavaScript. What am I doing wrong in the 2nd approach? ********* Sorting Technique ********* ``` nums = nums.sort((a, b) => a - b); let maxLength = 1; let i = 0; while(i < nums.length) { let j = i + 1; let redundantNums = 0; while(j < nums.length) { if(nums[j - 1] === nums[j]) { redundantNums++; } else if(nums[j - 1] + 1 === nums[j]) { } else break; j++; } maxLength = Math.max(maxLength, j - i - redundantNums); i = j; } return maxLength; ``` ******** Your Approach ************ ``` const set = new Set(); for(const num of nums) { set.add(num); } let maxLength = 1; for(let num of nums) { if(!set.has(num - 1)) { let localLength = 1; while(set.has(num + 1)) { localLength++; num = num + 1; } maxLength = Math.max(maxLength, localLength); } } return maxLength; ```

[@PabitraPadhy]

This will check for each of the element, even if the longest is equal to the size of the array. As there cannot be a sequence longest than the array size, I would break the loop, to make it more efficient.

[@BBRR442]

I like the way he talked about this problem, like so nonchalantly

[@rishabhpatel263]

How is this Solution O(N). The inside while loop is not going to be run in constant time since we are checking all the numbers that are present in the set by incrementing 1. I thought of a similar approach. But interviewer wanted me to solve in O(N).

[@mearaftadewos8508]

explanation at it best! I just coded it up with such a flow after you clarified the problem

[@ronifintech9434]

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!

[@divyanshchaudhary7063]

Thanks buddy def longestConsecutiveSubsequence(arr, n): numSet = set(arr) longest = 0 start = end = 0 for n in arr: # check if its the start of a sequence if (n-1) not in numSet: lenght =0 while (n+lenght) in numSet: lenght +=1 if lenght > longest: start = n end = n + lenght-1 longest = max(longest,lenght) return (start,end)

[@sureshgarine]

you made a complicated process looks so simple. thanks for the explanation and approach

[@valentinrafael9201]

You just convinced me to go back to pen and paper when solving anything ( not just programming).

[@ramcharanim4171]

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]

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)

[@jiwachhetri7317]

@@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)

[@DragonStoneCreations]

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 :)

[@cosepeter2197]

yeah. I was also thinking the same

[@bufdud4]

yup :(

[@PremPal-uy4nm]

@@cosepeter2197 why sad?

[@crisi6754]

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. :)

[@creativeshorts9914]

Bro, i think Leetcode made some changes on tests cus now it exceed time limit after iterating through the duplicates and i think changing an array to numset would be more efficient

[@dolphinextreme48]

You don't need a separate set. Just do nums=set(nums) and use nums for a jump in memory complexity.

[@SW-yz6gg]

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]

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.

[@ktrize3084]

​@@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]

@@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)

[@snehakandukuri429]

@@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?

[@AnhNgo-oh8hv]

@@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.

[@JohnIdlewood]

Set is a hashtable. In worst case scenarios, it's search is O(n). Or you create a hashset size of the hashcode and guarantee there're no collisions, but it's size is definetely not M(n)

[@anushibinj]

You are a genius! You explained a Hard problem like it was nothing!

[@frankdu0207]

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?

[@airysm]

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

[@johns3641]

The inner while loop makes it O(2n) but we don't consider constants for big-O analysis so it's just O(n).

[@olayemii]

@@johns3641 why is the while loop not O(n)?

[@sahildhawan22]

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)

[@sonydominates]

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

[@Sinders]

So I wasn't understanding why my runtime was like 5x the normal runtime, you need to make sure after converting to set you iterate through the numSet not the original array

[@pushlin806]

this code is not linear, there are counterexamples, like 1, 2, 3, 4, 5, 6, 7, ... n / 2, 1, 1, ... 1, but as already mentioned, iteration through set fixes the problem

[@sahildhawan22]

Hi guys, for computing time complexity here, please see if my method is correct: I think this is definitely not O(n*n) because we are not checking every number (1 to n) against the current number (n). In this 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). Correct me if I wrong!

[@ajitham5975]

o(2n) = o(n)

[@Vipr728]

Thanks for the clarification! I thought it was O(N^2) since it was two loops nested, but didn't understand that the while loop only loops through a subset of n, m, thanks!

[@alienfunbug]

Thanks for the explanation, I'm trying to wrap my head around this... maybe its because I was assuming worst case scenario: contiguous sorted list, you will loop N times and check N/2 numbers (referred to as M in your explanation). So.... we're looking at O(n^2) in worst case scenario or I'm missing something? Maybe generalizing the average case? Thanks!

[@abd-ulbasit]

can it be O(n*longest) as while loop runs for the longest sequence ?

[@tripletduo]

very clear solution with time complexity explained, thanks for sharing!

[@georgeimus6102]

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 🦍

[@g0nz1337]

Why is it linear if it has nested loop?

[@rustam199639]

Thank you for the video! Could you explain to me why this solution is O(n)? if we have an array/set of even numbers like: [0,2,4,6,8,10], so, finding for every element in this array/set if it has a predecessor like for 0 to find if there is -1 will take O(n)(worst case for lookup is O(n) and not O(1)(its for average case)) and for every element there will be O(n), Doesn't it mean that it will take O(n^2) for the whole algorithm? Or am I wrong somewhere here?

[@kamilamukailova872]

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.

[@jamiewang8043]

Best explanation, clear enough to understand, really helps!