Largest Divisible Subset - Leetcode 368 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem largest divisible subset I really like this problem we're given a set of distinct positive integers and we want to return the largest subset answer such that every pair of values satisfies this condition one of the numbers is a factor of the other that's pretty much all that this means cuz this is saying that if we have a pair of numbers like four and 2 four modded by 2 is equal to zero if we take the reverse of that if we took two moded by four it would end up being not zero it would end up being two the remainder of this would be two but they tell us we can arrange this in either way like if we have a pair of numbers we can either do it this way or that way if either of these ends up being equal to zero then it satisfies the condition so this is basically a glorified way of saying that one of the numbers is a factor of the other one number multiplied a certain amount of times can equal the other number this would also be a factor if we had 8 and 2 so 2 * 4 would be eight so this is the first key observation that you really need to make for this problem if you can't it's difficult to solve it once you recognize this though you realize that we can try to save ourselves having to do both of these wouldn't it be nice if we sorted the numbers kind of like they have in both of these examples if we sorted the input then as we are iterating over the numbers let's say 1 2 3 and we have two pointers I and J then we don't have to try both of these we can always take the bigger number three and try to mod it by the smaller number two and if this ends up being equal to zero then it satisfies the condition in this case it doesn't I think it'd be equal to one so it doesn't work so this will be easy for us and another thing to notice here is when they ask us for an answer what we have to guarantee for the output in this case let's say it's 1 2 4 and 8 what we have to guarantee is that every possible pair is divisible by the other but this second example kind of indicates that we don't necessarily need to do that what I'm saying is if we know that one is a factor of two in other words 2 modded by 1 is equal to zero and we also know that four modded by 2 is equal to Zer so 1 is a factor of two 2 is a factor of four do we really have to check that 4 moded by 1 is also equal to zero no we don't cuz that's just how math works now one is kind of a misleading example because one is a factor of everything but forget the one if two is a factor of four and four is a factor of eight then we know for sure that two is going to be a factor of eight I don't want to bore you with the math but if you're still not sure let me just show off my algebra skills if two is a factor of four we know for sure 2 * X is equal to 4 if we know 4 is a factor of 8 then we know for sure 4 * Y is equal to 8 and now we just take this part and replace it with the four over here and we would get 2 * x * Y is equal to 8 so basically what we found is that 2 multiplied by some integer is equal to 8 so this will help us eliminate some repeated work now we still kind of have to brute force it and let's look at an example to show you why consider this example let's say we look at the first pair of numbers as we naturally would we find two is divisible by 1 so this is our result so far now when we look at the next pair of numbers we don't need to compare five with one we just compare these two so we can in other words keep track of the previous number that we have added to our answer great but I'm trying to prove to to you we can't be greedy here because what you're going to find is five is not divisible by two okay so now we're done is that the best result we could have possibly found no just because a pair of numbers is divisible doesn't mean we can't consider the alternative we can consider the alternative where we skip two and then we would find 1 and five it's also divisible so next we'd go to the next pair of values 5 and 15 this is also divisible next pair of values 45 5 ID 15 is going to be 3 also divisible this is the result this is the longest it's of length four we do have to brute force it and the way we're going to do that is kind of how I just showed you right now we're going to keep track of two variables the current index that we're at and a second variable called previous which is the previous number we added to our sequence technically we are allowed to skip the first number as well by the way so just keep that in mind because of that the way we can start our sequence is by starting the index at zero and having previous always be set to some default value one because one will always be a factor of any number because we know that every number in the sequence is going to be positive so this is just like a trick to make this work out it's not like a super important detail let me kind of show you what the tree would look like though starting at 01 we can consider where we include the one in the sequence our sequence would look like this then we would move to index one and what would the previous element be in the sequence it would be one still so we can also consider skipping this first one then our sequence would stay empty and we would move to index one and our previous element would still be considered one I know this part is kind of confusing it's a minor detail so please don't try to waste too much time on it and we know that this side is not going to lead us to the answer this side was basically to enumerate all possibilities where we don't include that but I won't draw this out because we already know it's not going to lead us to the answer for here though let me show you you we can either include the two which our sequence would look like this 1 2 or we can skip the two our sequence would look like this it would stay at one and then we'd go to the next position at two where our previous element remains one on this side we'd move to index 2 but our previous element would now be two our previous element in the sequence let's continue down this path where we can include the five or skip the five and we know that this will end up leading us to the result so this is essentially the logic of the tree the base case of course is going to be when I reaches the end of the input and this is actually a perfectly valid way to code this up Brute forcing this it's obvious that the height of this tree is going to be n in the worst case and we have two branches each time time complexity is going to be 2 the^ of n but we have two variables we can use these variables for caching so the size of our cache will be bounded by these two variables I is going to be the size of the input the the number of possible values for previous is also going to be the size of the input so memory complexity is going to be n^2 and you can consider the time complexity as being N2 as well the reason is because on each recursive step we're not looping or anything we're just doing a constant operation we're doing a recursive call here and a recursive call there and we're caching the result of each recursive call there's just one catch if we're caching a list doesn't that mean the memory complexity is actually going to be n^2 times the size of that list which could get pretty inefficient n cubed right the answer is no and it's not easy to figure out I actually first coded up this solution and I was surprised that it passed so then I looked into it and I realized that the max size of a sequence is actually not going to be n in the worst case it's actually bounded by 32 that's a special number isn't it you might now be able to figure out why it's bounded by 32 without me even having to explain it but if you can't let me show you let's say we start at one then the next number would be two then the next number would be four 8 16 because we want the next number to always be a factor of the previous number so the easiest way to do that is to double them we could triple them as well but actually that will lead us to a smaller sequence because the limit of this sequence is going to be bounded by 2 to the power of 32 because that is roughly 4 billion first of all it'll overflow in most languages in Python it probably won't overflow but they do tell us that the max size of any element in the input is going to be I think roughly 2 billion or something like that so basically none of the sequences will ever be longer than 32 which is technically constant so that's how I'm getting this time and space complexity from so this is the code for that solution and there's a reason I'm not coding it up in front of you cuz I'm actually going to code up a different variation of this solution in just a second but I just wanted to give you this in case you wanted to pause the video or something you can see here's the logic where we skip the element here's the logic where we include the element and we try to maximize the length on each time we added caching here technically this does pass on leak code but there happens to be a better way there is a way for us to actually make it so that we don't need to pass two parameters in we can only pass a single parameter why would do that because the time complexity will still remain n s but the memory complexity will be Big O of n CU we won't need a cache of size n squ it'll be of n we just have one key for the cache now how do we do that variation of this solution well we're going to change the logic cache at I is going to be the longest sequence starting at I and including the number at I the way we're going to do that is basically instead of now having two variables and just making two decisions each time we're actually going to take one of those variables remove it and now we're going to have to actually make many decisions we're going to have to make a loop of decisions logically it's going to look like this we start at index I let's say we're at zero we know we have to include this element in our sequence so our sequence looks like this now we go through every possibility we can either go to index one we can go to index 2 we can go to index 3 and we want to find which one of these is going to lead us to the answer and the reason we're doing this is because we do have to consider skipping elements we have to consider maybe we skipped two elements maybe we ski three elements our previous solution did account for that and we have to make sure this solution does as well what we're going to find is that the sequence from here is just going to end up being two the sequence from here is going to end up being this whole sequence the sequence from here would have ended up being this and the sequence from from here would have just ended up being this among all of those which one is the longest I think it was this one and that's the one that corresponds to this decision so among all of these we would find the maximum and then return it that's the idea recursively we'd probably do the same thing like from two we would consider going to three and we'd consider going to four which among these two is the longest probably the one from here so we'd find the maximum and you know that's kind of how the recursion will work so let's code up this variation of the solution because it's more memory efficient so let's code it up the first thing let's not forget we do need to sort the input it's not necessarily going to be sorted but this won't really affect the time complexity because it's going to be n^2 regardless now I'm going to write the recursive function we just take a single parameter I and the main base case is if we reach the end of the input we can return now we're not going to return zero because we know that this recursive function is meant to return a list so I'm going to return an empty list as the default value next let's consider every Poss ability well we know we're going to be starting at nums of I so we can initialize our result instead of being an empty list we know we're going to include this element regardless so let's go ahead and do that and we can write the return statement we know that's what we're going to return but we actually have to compute it so now is the part where we Loop we will consider every possibility we go through every decision so starting from I + 1 all the way until the end of the list we want to consider this but we have to make sure that this number is divisible we have to make sure nums of J is divisible by the current number nums of I otherwise it's not valid so we do this then we check DFS at J we recursively find the longest sequence starting at J so this will be assigned to Temp but since we know I can be included in that we can basically add this to the beginning of this list there's a way to do that with a method but the easiest way to do that in python at least is like this we can basically create a list with this element and then add these two lists together and you might be thinking isn't that big O of n no remember the max size of this is always going to be 32 and usually it's going to be pretty small it's probably going to be a lot less than that so this is usually going to be pretty efficient it's possible that this temp is greater the length of this temp is greater than the current result if that's the case let's reassign the result to Temp so this is The Brute Force solution I guess there's only one catch that I didn't go over if I call DFS from zero now it's probably not always going to give us the correct answer because DFS of zero would only calculate the longest sequence starting at zero but what if the longest sequence actually starts at a different number so for that reason we kind of have to do another loop out here so I have to say for I in range we have to consider every starting position so I'll just do line length of nums and I'm going to declare a result out here it's going to be an empty list that's what we're going to try to return and we're always going to set DFS to a temporary variable and then we'll always check if the length of temp is greater than the length of result then let's assign the result equal to Temp there is some duplicated code here there might be a better way to code this up but the idea here is that this is memorization but we are saving space compared to the previous solution that I showed you which in my opinion the previous solution was more simple looks like I forgot to actually add the caching so let's do that so we'll declare our cach up here and we'll add a second base case for the cache so if I is in cach let's I want to save space so I'm going to do this on the same line let's return cach at indexi I'm also going to move this to the same line I want all the code to fit on the screen so here lastly before we return let's just make sure to Cache the result so cache is going to be equal to result this is the entire code but actually it looks like there is one bug and I actually made this multiple times as I was trying to solve it myself when we check if this is divisible by the other we have to check that this is equal to zero not that it's non zero which is what we were doing before so sorry about that and there's one other error over here we're hardcoding this to always call DFS on zero we should probably change this to I again sorry about that now let's run the code and as you can see on the left it does work it's about as efficient as we can get it but if you're interested in seeing the tabulation solution I will go ahead and show you that now so we're going to basically apply the same idea here except we're going to do it without recursion I'm going to follow the same logic and for us to do that we are actually going to allocate some space equal to the size of the array so the cache is going to be of the same size I'm going to go ah ahead and just draw that down here our cache is going to represent the same thing as it did before and because of that I'm actually going to iterate in this array in reverse order rather than front to back because if we were to go front to back we'd have to change what this represents some people like doing that but I think it makes it harder to go from the recursive solution to the tabulation so I'll be doing it this way but again it's your preference so what this is going to mean is we're going to go and compute the longest starting here first because we know if we want to get the longest sequence that starts here and includes this value we have to go to all of the sub problems but how can we go to all of the sub problems if we haven't even computed them yet because we're not doing it recursively remember so for us to do that we have to first compute all these sub problems before we can fill in the value that goes here well the first sub problem is pretty easy 45 what's the longest sequence starting at this index it's just the list with 45 okay to compute this one we might need to look at the sub problem and starting here let's just compare the elements first let's just check that the longest sequence that starts here is valid for this guy for us to do that we have to check that this is divisible by this remember the array is sorted so we know the larger element is always on the right this is our J pointer this is our I pointer and these are divisible 15 is a factor of 45 so this works so now to fill in the value that goes here we create a list with 15 and then we take all elements that are in this list and add them to here as well so we would just take 45 and put it here and this would go in there I'm probably going to run out of space to put the actual list so sorry about that now just quickly repeating this five we're going to look at two sub problems now I'm going to redraw the pointers so our ey pointer would would be here we're going to consider if J pointer was here check if these are divisible yeah they are so what we do is create an array with five take all the elements from this array atom here 1545 and now we have an array of three elements we would also consider the opposite case where J would actually be over here and this technically works as well so we could create an array with 5 and 45 but this array is obviously not longer so we uh keep the first array 5 15 and 45 at this point you probably get the idea idea two we're going to find that I is here and we would consider J for all of these but two is actually not a factor of any of these three numbers so two by itself is going to be the array that goes here and lastly we know what's going to happen when I is over here we're going to look at this and we're going to find that five is divisible by one and then we're going to take all three of these elements add it to one and then we'll have an array over here with four elements that will be the result and this is what I'm going to code up now so I'm actually going to leave the code here for the recursive solution because you'll see how easy it is to go from the recursive to the tabulation so I'm going to create that array that we were kind of looking at and I could do it this way where we have an empty array for every number in the input nums and so this would represent DP of I is going to be equal to the longest sequence that starts and includes I but just like how in the recursive solution we always initialized the result to the number itself a list with the number itself cuz we know it's always going to include that number we can apply the same logic up here we can always include n cuz if the sequence starts at I we know that at least the sequence will look like this of course it might be longer as well now I'm going to go in reverse order just like I talked about so for I in range length of nums and a trick in Python you can do to go in reverse order is actually just wrap this in a reversed call so this is a a function as well and this will basically iterate over the indices in reverse order it's just a cleaner way to do it and then we want to consider all possibilities consider all sub problems so for J in range from I + 1 until the end of the list we will look at this and before we even consider the sequence let's just make sure that the numbers work out let's make sure nums of J is divisible by nums of I and let's not make the same mistake let's make sure this is equal to zero and so if that's the case let's create a temporary array kind of like we did in the sub problem over here I'm actually just going to copy and paste this because I want to show you how similar it is copy and paste instead of calling recursive function the sub problem is stored in DP up above so we can just say this we can actually change this from a function call to being a lookup in our DP array here we're going to do pretty much the same thing I've done down here here except we're going to store the result in DP of I cuz that's what we're trying to compute that's the problem we're trying to compute here we were Computing the same problem but we stored it in result because that's what we were returning and we also stored it in the cache as well so we're kind of doing the same thing so DP of I is going to be equal to Temp if the length of temp is greater than the length of result otherwise let's set it equal to DP of I it'll stay the same in the otherwise case that's pretty much the entire code now we've computed all of the longest sequences starting at every single index but where does the result go the result doesn't necessarily start at the beginning DP of zero isn't always going to contain the result so to get around that we could just look through here and find the largest one or we could just maintain the longest one as we are building that array I'm going to choose the ladder so here I'm going to declare result it's an empty array array that's what we're going to return so for us to do that let's populate it after we have found the longest one that goes in DP ofi and we know we found the longest after this whole Loop is finished out here we can say result is equal to DP of I if the length of DP of I is greater than the length of result otherwise let's leave it as is so this is the entire code unfortunately looks like I did have another typo I don't know why I took the length of result here I guess we were almost making it too similar to the recursive solution let's not forget that in this case in this context the result is actually DP of I so we only want to reassign this if temp is longer than it otherwise it stays the same sorry about the confusion now though we can run this code and you can see on the left that it's pretty much as efficient as the previous solution if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon