Length of Longest Fibonacci Subsequence - Leetcode 873 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve length of longest Fibonacci subsequence very interesting problem today I really like this one actually short and sweet the idea is we are given a array of numbers that is strictly increasing please pay attention to that it's probably the single most important observation in the problem the array is already strictly increasing and you know what that implies right no duplicates so if you are decent at leak code I might have already solved the problem for you if not that's perfectly okay I'll still run through the problem description give you a high level overview with some of the intuition of how to solve the problem do a bit of a dry run and then we'll code it up and then I'll discuss the optimization which I find is pretty interesting and I can actually show you how to easily convert the first solution into the second solution it's pretty much a common trick I use a lot of people don't like that trick for some reason that's harder for people to understand but I'm going to show it to you anyway cuz in my opinion it's just so damn easy once you get used to it but uh anyways so let's consider the very simple example we're given because honestly I think this one is enough to understand this problem and like come up with a solution so let's say this is the input array what we want to know is what is the longest subsequence not subarray it doesn't have to be contiguous so we take like a sequence of elements from left to right we can skip over some of them maybe I take that maybe I take this and then I take that and so these numbers form a Fibonacci like sequence so the requirements of this are also important the sequence has to have at least three numbers now I think the reason they say that is because if they did not say that you could be given literally any array of two elements if I call it like a thousand and I call it 2,000 I mean you can't say this is not a Fibonacci like sequence uh provided like you know what a Fibonacci sequence is I'll try to cover that briefly because if you just have two numbers I mean it's kind of like the base case you could have any two numbers but uh anyways um and then the more important requirement is that like generally the Fibonacci sequence is like this it starts with I think two ones and then you take these two numbers to get the next one you add them together and then you take these two numbers add them together to get the next one and you just kind of keep going 5 8 13 and it just kind of keeps going like that now we don't need this exact sequence we could actually have any starting point for example you see a four does not show up in the sequence if I start with four I start with five add these together I get nine this is not the Fibonacci sequence but this is a Fibonacci like sequence so now I could just kind of keep going add these 14 23 37 just keep going so this is what we care about in this problem and from this array we're looking for a subsequence so now if you understand everything up until this point and now you don't know how to solve the problem you're probably getting kind of nervous if you were in a real interview you'd probably start sweating you'd probably think okay I don't quite know what the Brute Force solution even is I mean we're dealing with subsequences if you've solved some subsequence problems you know to enumerate all subsequences it actually takes backtracking to do that and you know that's a possibility that's probably going to at least be an exponential solution and then you're probably thinking well dang then maybe I cannot optimize it with dynamic programming and maybe we could get it down to some kind of like linear or n squ solution it might be difficult to do that and you know this is not like a bad line of thinking the hard thing about this is that this is kind of valid like there's nothing wrong with this I I don't actually know if you can like take the backtracking solution and then optimize it to DP I didn't actually do that but when you given a problem like this one that's one idea I had but I saved that idea like this is how my brain works I put that idea on hold and I wanted to explore maybe there's other solutions that are easier or more efficient I think there probably might be a DP solution just cuz I've seen this pattern of problem before Fibonacci subsequence it seems like there might be DP and it might be like related to the backtracking solution but then I also asked myself maybe there's some kind of pattern or shortcut with this problem that typically comes into like greedy Solutions and so that's the first thing that I explored maybe I can come up with some kind of greedy solution I saw it strictly increasing so maybe just maybe I can actually come up with something like an N2 solution because one thing I know for sure is this once I pick my two starting values of like the Fibonacci 2 and five at this point every number that comes after it is already determined I mean I don't know if there's like an equation to calculate the I Fibonacci Sequence there might be or not but at the very least I know this is deterministic there's no probability involved or anything like by choosing this elements we have determined what the next elements are going to be so my line of thinking was this I get a couple nested Loops for I for J and I pick every single pair of starting elements so like maybe for this and this I uh start there or I could start like this or I could start like this etc etc and then maybe this is my first element and then I start here or here or here and just kind of keep going like that uh for that then maybe the rest of this I can scan through that maybe with like an extra Loop or something and I think you could with like another loop just kind of determining like keep going until you find the next num so let me kind of just show possibly what that would look like let's say we started with one and then we started with two as well okay now I have my third pointer I I don't know what to call it I'll call it K and then I have this number it's three it is the sum of the two previous numbers that's good okay so now my two previous numbers are two and three so now I look at the next number four it is not the sum of the next two numbers so skip it okay now I look at five it is the sum of the two previous numbers so we're good that's one solution you might be already noticing there's a little bit of repeated work here because we're going to kind of keep going like now I have three and five and then I'm going to skip six I'm going to skip seven but eight does count so that's good and now I'm going to try the next thing starting from here starting from two and three I'm going to have another pointer okay four skip it okay five includ it okay skip these two and eight include it okay so now I found another subsequence with 1 2 3 four elements the previous one had five elements that one was the longest one and the way I've described this solution it's going to be n cubed but remember there's no duplicates so actually there is a slight optimization we can make here like this once again I'll have like two nested Loops for I and for J I'll start here and here and now that I know the sum of these two all I need to check is does the number 1+ 2 let's call it the next number let's call this the previous number and this the current number does the next number which is the sum of these two does it exist anywhere because if it does we already know the elements are in increasing order we kind of already know that this uh is somewhat satisfied as long as the existence of the number is confirmed so uh yeah that's all we check so how can we check that efficiently probably with some kind of hash based data structure hashmap or hash set will do so that's what we're going to do so then we check okay that number does exist three does exist that's great so now we update the numbers this becomes my previous this becomes my current now the next number I'm looking for is the sum of these two which is five I confirm the existence of it with my hash set maybe then this becomes my previous number this becomes my current number my next number will become eight and then I just check for the existence of it so now um it does exist this has gotten kind of messy now my previous number is going to be five my current number is going to be eight my next number is going to be 13 and we find that 13 does not exist in the array or rather in our hash set that's how we would do the lookup and so if that's the case then we can stop and then maybe we'll try a new starting point we have to try a new starting point because I mean maybe like three and four maybe somehow that can form the longest subsequence and maybe like we had an 11 over here and something like that so we do kind of have to check all of those but there is a little repeated work I'll show you how to eliminate that repeated work after I show you this solution that I just talked about it is not quite n cubed it's actually n sared and like the way Fibonacci numbers work you could kind of think of it as like two numbers that are like the the Fibonacci sequence is roughly doubling every single time like I think it goes from five to 8 to 13 to 21 so you could kind of think of it as like roughly doubling and thus um you could say that like how many elements are we actually going to visit through that array I think it's roughly equivalent to log base 2 of the I guess you could say the length or you could say the max number but again like this is a rough approximation I think we'd have to get into a lot of math to give like a more precise answer and I think I won't do that for this video I don't think you'll be asked to do that in your coding interview so let's code this one up so the first thing I do is just throw all the elements into a set and that will convert that into a hash set in Python I'm also going to declare my result which is zero that's going to have the length of the longest Fibonacci subsequence that's what we're going to end up returning and so now I want to go through every pair so I'm going to have my first index go through the entire array except the last element because I want to have at least two elements so I'm going to do length minus one and then I'm going to do for J in range starting from I + one I always want this element to be after the previous one and then going up until the end of the array because this element is allowed to do that that way we have at least two elements in the subsequence so there's that and now I'm just going to have a couple variables to make this readable I'm going to have my previous and current have that uh set to I have that set to J and I'm going to calculate the next number previous plus current I'm going to say while the next number is in the hash set let's shift the pointers I mean that's like the obvious thing to do here let's uh set previous to Cur C is going to be set to next next is going to be set then to previous plus Cur but while we're doing this we should also kind of just keep track of the length so what I'm going to do is here initially we have at least two elements we can say our length is two and then every time like this evaluates to True increment the length by one once that stops we can potentially update our result and so this is where you might have a bug you might think to put this statement here result equal Max of result and length but what that would do assuming that this Loop never executed and this never evaluated to True This would run regardless so the result would always be at least two but that's actually not what they want us to do in this problem remember how they said that they want only Fibonacci sequences there are at least three elements long so for that reason we put this inside the loop you could put it down here you could put it up there just make sure you put this after the increment I believe that's the whole code I mean you could call this a Brute Force solution but I don't know if that's quite accurate because a more Brute Force solution would be to use backtracking and this is more of a greedy solution in my humble opinion and so you can see here it does work it's pretty efficient I'll show you another solution that's technically more efficient in terms of the Big O runtime it's less efficient in terms of the memory and I think in terms of the real performance it's actually less efficient at least when I ran it so back to the drawing board and just to give you a bit of the intuition of what I'm talking about I'll show you how to think about this problem I don't know how indepth I want to do in terms of drawing out the entire like DP grid because I feel like for this problem it might actually just end up over complicating things but the biggest piece of intuition I want you to recognize is when we started here and here then we found that this was the subsequence right that element and that element we skipped some elements in between when we started over here and here it's kind of the exact same if we ever get to a point where current and previous are the or sorry I sh put previous here and current and it's the exact same I mean we're just going to be repeating the exact same thing we did except it's going to be shorter potentially missing some elements that came before it so at this point you should recognize that this is dynamic programming if you don't know what dynamic programming is I would honestly stop watching this video right now unless you're just curious of how I code this up uh you can head over to n code. there's a lot of resources on there to learn dynamic programming I would specifically look at some of the subsequence problems or you could just go on uh YouTube watch my video on the Fibonacci sequence but I think that probably won't be enough you should probably practice more dynamic programming use other resources if you prefer just somehow get a decent grasp of this and then maybe come back and watch this video but for now I will say that like that's kind of the intuition and so when I identify that I recognize that we can solve this in some kind of bottom up fashion maybe there's a way to do it top down as well but I immediately recognize that the solution that we already coded up is identical or almost identical to what we need except we're going to do this in reverse order because what I can do is if I had solved this orange sub problem first I do that first then I come back to this problem because at that point I will already recognize that if my I is here and my J is here the longest subsequence we can get is going to be of length four so then when I come back here and my I is over here and my J is over here and I'm asking well from here what's the problem well I'm going to say okay well if you add these two together then they add up to three three is at this index and so since we're using like ijs we're using the indexes to determine the sub problem we might need to have some kind of mapping where we take each number and map it to the index so that then we can say okay now 1+ 2 does exist it exists at this index and so now the sub problem I'm looking for is I'm going to take my J and assign it to I and I'm going to take J and assign it to the index of the number that we summed to you could call it the next number and so now I'm going to say well this sub problem what is the length of it it's already been computed it's four so what I can do is say okay I had one number one plus DP of i j the new I and J once I like shift them here and here and the result of this was that four that I'm talking about over here and I add one to it now I get five so that's pretty much it other than that like I said I'm going to iterate through these in reverse order instead of like having my inj initialized there I'm going to work backwards I'm going to put my I over here and my J over here I'm going to find that okay this subsequence is of length two okay then I'm going to start at the next spot I'm over here my I is there my J is going to be over here like I said going in reverse order okay the length of this subsequence is also two of course 14 the sum of these two numbers does not exist so we skip that okay then my J is going to be shifted over here I got 13 does 13 exist nope so once again this subsequence is of length two those uh sub problem lengths will be stored in our either hash map or we could use a two-dimensional grid but either way we'll just kind of keep going eventually my I will be over here my J over there okay 13 does not exist either eventually we'll get I think to this point where my I is over here J will be here we'll I've skipped this one we'll just kind of keep going eventually we'll get here J is there okay I got these two add them up it's eight hey eight actually exists for once okay then I'm going to ask with this element as my I and this element as my J what was the longest subsequence we were able to form well this one is of length two so I'm going to say 1 + 2 = 3 fantastic okay I'm just going to kind of keep going now now my ey pointer might be over here J is going to start there it's just going to kind of work its way backward eventually it'll get here 2 + 3 that's five five is over there so now I'm going to say my I is over here J is over there these two add them up and you get eight but actually uh we don't need to do that we don't need to add them up we're just going to get the length of this sub problem which we already stored in DP and that'll tell us the length starting at these two elements the longest subsequence will be 1 2 3 so I'll take that three add it to this element and that'll be four and then finally eventually I'll have my I pointer here J pointer here we'll find that adding these two up we get three and the result of that sub problem when I is here and J is there uh is 1 2 3 4 so that four will be added to this we'll get 1 + 4 we'll get five so the downside of this is that our DP grid is going to be like this and like those elements kind of going that way so it's going to be n SAR in terms of the space in terms of the time complexity though you can see that this is also n^ s so that's the Improvement we're not doing any repeated work by working through this backwards uh so let's code this up now so I'm actually not going to change or not get rid of this code I'm going to show you how easy it is to just change a couple things first of all take this python makes life so easy I'll never understand why people use a language other than python I used to be a C++ person and then I switched to python took me like 4 hours to learn it and I never looked back uh but anyways okay I'll reverse that and then I'll reverse this it'll do the exact same thing it's just going in reverse order and so now I'm going to do this calculation the next calculation I'm getting rid of length and I'm going to get rid of this Loop but not quite get rid of it I'm just going to change it into an if statement and then I'm going to say okay if the next number is in there fantastic so then we can say our length is going to be uh this one plus uh now let's create DP like the thing that's going to be storing all of our sub problems so let's make it a hashmap just to make it easy for ourselves so this will basically take I J and map it to length of longest subsequence starting from I and J and so assuming we have that stored in here we could do something like this um using uh the key so we know that the elements right now that we're starting at are I and J but the sub problem is going to be when J becomes the first key and then we want to know the index of the next element so right now I'm just going to assume we have a way to do that I'm going to call it array map and I'm going to say okay pass the next value in and that'll give us the index of that element so now I have my two indexes of the two elements and then this will give me the length of the subsequence starting at those elements I take that added to one I get the length I don't really need to do these two things here anymore um but I will leave this line of code right there now after that's done we can then also do this store in DP so let's say for I and J and notice I didn't actually change I these are the original indexes that we had so not like this sub problem over here but actually the original problem and for that we just computed the length um actually to make that more clear let me initialize length here as two and potentially we end up reassigning it here any value stored in here will never be less than two so um either it'll be two or it'll be greater than two but whatever length happens to be we will assign it here into that and now I think the last thing for us to do is array map and um I'm basically just going to get rid of this array set so this lookup can also be performed within a hashmap so that's why I'm doing that and then here I'll just rename it to array map and life is so easy in Python map a number to its index for I in enumerate the array and I believe this is the entire code unless I'm forgetting something let's just run it I guess very unfortunate I put brackets around here when we wanted to hash map this is called uh dictionary comprehension by the way it's something I cover in Python for coding interviews but uh I think that should be good and so yep looking over here you can see it does work uh funny enough obviously the memory got worse but the runtime actually did as well I think one way to mitigate this would be instead of using a hash map use a two-dimensional array so I'll do that so 0 * length of array for underscore in range length of array this is a nested list comprehension I think this is also something I definitely cover in Python for coding interviews um but okay so now that we made this a two-dimensional array we change uh this over here so J will be the first Index this will be the next one just get rid of that and then over here it's pretty simple just do I and J and I think I'm not missing anything so let's give give it a run and uh yeah so you can see that actually both runtime and memory improved a little bit I think it's like three times as quick without all the hashing going on but still I think this is slower than the previous solution that we had this is uh dynamic programming by the way anyways if you found this helpful check out NE code. for a lot more this was a pretty difficult problem so don't feel bad if you struggled with it or feel bad if you feel like I made it look easy it's not easy the only reason it looks easy is because I've practiced a decent amount