Longest Consecutive Sequence In An Array - Coding Interview on Whiteboard Thursday

hey guys welcome again to today's video before I get into it I just wanted to thank you guys I have read a lot of you messages saying that these videos are helping you not just in your interview processes but a lot of you are just learning data structures and algorithms from it so it makes me really happy so today's problem is how to find the longest consecutive sequence inside of an array so let's see how we solve it so let me draw the problem out so it's a bit more clear let's say I have an array that looks something like this I have two one six nine four and three so in this case the longest subsequence if there's the input then the longest subsequence would be one two three four and the length which I'll be outputting would be four right so output would be four because it is one two three and four okay perfect so I think there are a few different ways we can approach it the first one which I think I'll go ahead with right now is I would want to input all of this array all the numbers in this arena set or a hash map so let me just do that first or before before I even do that let me tell you what the logic is now I will have a set that looks something like this I'll have two let's call it two one two six through nine true for true and three true right and obviously this will disregard all the duplicates now this set when I iterate over all of its elements I will say hey do I have a number that is smaller than this element in the set if it is then I'll know that it's not the starting point in my subsequence right so I probably shouldn't start out there I should start out elsewhere and I'll keep a log of whatever longest subsequence or the length of the longest subsequence is at any given time right so let's say I'm starting out at two I say hey is two minus one in this set it is in the set right so I don't need to iterate and say hey do I have 2 plus 1 n plus 1 n plus 1 so I will go ahead in my tray Chanel I'll be at one now so I'll say hey is 1 minus 1 which is 0 in this set it's not so this is a good contender to be the first one in my subsequence and then I'll go about checking let's say in a while loop that says hey do I have 1 plus 1 I do do I have one do I have 2 plus 1 I do do I have 3 plus 1 I do so I will keep going till I don't find the plus 1 that way I'll figure out what the longest subsequence is right and then I'll move on in this iteration and I'll go to 6 I'll say hey do I have 6 minus 1 in this case I don't have 5 so I will start at 6 but I don't have 7 either so that'll be the longest subsequence as 1 right at the end of that two I loop you know I'll say whatever the max of the current subsequence in the one I just counted take that as the longest one and then move on in our iteration right so at the end I will have the answer in linear time complexity in obviously linear space complexity as well so let me write down a function for it if you don't mind I will say a function yes want to make sure to the frame yes all right function let's call it longest SU BS subsequence let's say the input is in array now the first thing I need to do is transfer all the array elements into a set so let me say let me call it just set it's a new hash map and I say array or I can have a for loop doesn't matter so for I or for num in array set that's not only one I also want to make sure that the time complexity it doesn't go into quadratic right for each element I don't want to trade over the entire right just to just make just to find it so I say set nummy comes true now the next thing I'll do is I'll be trading over the sets right so let's say for let me say I in set now what do I do I say whenever I encounter one I say array of AI is or not array of I I let's say is the number itself right so just to just to make sure we are very clear what's the index what's not so let me just say number in set I will check whether the number Y minus one exists if it does then I don't do anything if it doesn't then I go into my while loop right so I'll say if set num minus 1 let's say if not if it doesn't exist do this yeah so I'll see a while set let me before I go into while loop let me just set the current number that I'm at as the as the number itself right so cur equals num then I'll say a while set num plus 1 yeah we need to do two things we need to increment the counter and then increment cards as well right so let me keep a log of the counter here car equals num and count equals 1 right then I'll say count plus plus and ker plus plus right yeah and that's it so after I'm done with the while loop I know that I need to check whether my current longest or the longest the count over here is greater than the longest subsequence that I have up till now oh yes you're right I should actually check for cur plus 1 not num plus 1 good point so I have the while loop here right now at the end of it what do I do I just have a comparison so over here somewhere when I have set over here let me just say longest equals 0 to start out with and I'll say longest equals maybe math dot max longest and the count right yeah perfect so at the end of this if statement I will have I will have whatever is the longest one in that variable and then what am i doing I'm already trading through this for loop right so I don't need to do anything I think at the end this would take care of all of it and I can just return longest let me just make sure that this logic actually works so at the end I will have longest that I'm updating inside of the for loop at every iteration where this if stay mint is is evaluating - false right yeah that's good this looks good to me yes this is rating over all these keys yeah yeah perfect thanks so much for watching guys I hope this was beneficial if you liked it please hit the like button below it will tell YouTube that this video is worth watching for others so show it to other people as well and also make sure you subscribe right there and hit the little bell icon so you get notified every time a new video comes out and if you're looking for more such videos check out the ones right there or if you're looking for more advanced data structures and algorithms problems check out some information I've linked to in the description box below if you're watching from the states then I hope you have a very happy Thanksgiving and if you're watching from elsewhere I hope you have an equally amazing week and I'll see you soon

Channel: Irfan Baqui

Views: 62,960

Rating: 4.7184391 out of 5

Keywords: Coding interview, interview problems, whiteboard coding interview, data structures, algorithms, irfan baqui, longest consecutive subsequence, longest consecutive sequence, whiteboard thursday, Arrays, Hashmap, Hash Map

Id: VeJOswJTDos

Length: 9min 47sec (587 seconds)

Published: Thu Nov 23 2017