Maximum Distance in Arrays - Leetcode 624 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum distance in arrays this one isn't super crazy at least for a medium I think it's a reasonable difficulty question the idea is we're given a list of arrays where each array is sorted in ascending order wow they actually gave us ascending order arrays rather than non-decreasing order that's pretty rare and so we want to return the maximum distance and the only way that we can compute the maximum distance is by picking an element from one subarray and then picking another element from another array and then calculating the absolute value difference between them so a couple observations to immediately make the arrays are sorted in ascending order so obviously we only care about the minimum and maximums from each array so we don't even need to look at the entire array we're only ever going to care about the Min and Max from every single array and we can get those in constant time from each array you just get the first element and the last element that's one observation another observation is that we can't pick two elements from a subarray or just like one of the individual arrays I guess so the most Brute Force approach to this problem would be nested Loops right N squared for this particular subray let's say we would just take the minimum element from that subray and then go through every array that comes after it and then compute the difference from the max Max element from each list and then we would repeat that except we would pick the max element from the current list and then go through the minimums of all the remaining lists and then we would repeat that so for each array we would only compare it to the arrays that come after it and that's to ensure that we don't pick two elements from one of the lists and also let me kind of show you like I said the root force is nested Loops so for this array we'd look at all arrays that are after it and then for this array we'd look at all arrays that are after it why don't we need to look at all arrays that come before this one and then compare it to that because we already did that remember we're looking at every pair of sub Rays if we already picked this one then we went through everything that came after it which includes that one so we're going to use this same logic to get to the linear time solution because remember how we only care about the minimums and the maximum so if we have all of these we want to pick among all of these which one is the smallest so that's going to be far to the left and then we pick the maximum which is going to be far to the right and then you just calculate the distance between those the problem is you have to make sure that you don't pick two from the same one so how do we do that well the idea is actually very similar to how we solve the problem to some in one pass it's this we know like we have this array here but imagine we had an even bigger one we know that somewhere in this array there's going to be a subarray somewhere and then another subarray this it's going to be two different sub rays that form the solution it could be the minimum from this subray and the maximum from this one or it could be the Max from this and the Min from that one so we'll have to kind of try to compute it both ways so what am I going to do well I'm going to do this for every array we're going to compare it to the minimum and maximums we have collected so far so with the first array there's not much to compare but with the second array we're going to say okay whatever minimum we have so far and the max that we have so far from all the previous subarrays let's try Computing the result obviously we would get the result by taking the last element from this and subtracting from it the Min from the other array and the other way we'd compute It Is by taking the max that we've collected so far minus the minimum from this current subay that's how we would update the result and the Min and Max we collected so far would definitely not include this array and then we'd kind of do the same thing moving to the next array now we would update the minimums and maximums that we have you know collected up until this point and then we compute the result this way and then this way as well we would keep doing that and suppose that these are the two arrays that form the solution by the time we get here we would take the max subtract from it the minimum that we collected so far maybe that's what came from this array or we would take the max that we have collected so far which might have been the one from this array minus the minimum element from this array So eventually we will find that solution so by collecting the minimums and maximums that we have seen so far up until this point we kind of solve the problem in a greedy way we only need a couple variables and we only need a single pass so the time complexity is going to be n let's say where n is the number of arrays that we're given because remember we don't have to actually iterate through every single one of the arrays one last tip that I want to mention it's not really a tip I guess but consider this the minimums and maximums that we have collected so far are always going to follow this the max we Ed so far is always going to be greater than or equal to the minimum so if that's the case when we're Computing the result we're going to do it like two different ways one is by taking this element let's just call that array of n or you know I I don't know the last one in Python we're going to do NE 1 so that's the last element and we're going to subtract from it the minimum that we've seen so far and the other way is going to be by taking the max we've seen so far and subtracting from it the first element in the array I just want to show you that we actually don't need to compute the absolute value of both of these because consider this what if the first one turns out to be negative somehow like the sum this computation is negative well that would only be the case if this number somehow is smaller than the minimum that we've seen so far which technically yes that is possible so basically we're saying that this element is less than array or the minimum element so let's say that over here this could be possible but if that's the case then the the second one this one is always going to be positive because remember the arrays are sorted in ascending order this element is going to be smaller I guess even if it was equal it would still be the case but this is always going to be smaller than that and if the minimum is less than or equal to the maximum therefore this is always going to be positive and if you were to consider well what if this was negative that would only be the case if this element array of zero was greater than this one therefore this one would have been positive so that's not really something you NE neily need to know but it just shows you why we actually don't need to take the absolute value of either of these I'm going to initialize the result to be zero that's what we're going to ultimately return we're also going to keep track of a couple things the current minimum and the current Max an easy way to initialize it actually is just take the first array here so we can get that like this and then we can take the first element from that array uh we can initialize to be the current minimum and we can do the similar thing for the current maximum we'll get the last element from the first array these are just some good default values to use since we know that this array is going to be sorted in ascending order so now we go through every array in the arrays list and we always want to update the current minimum so we'll always try to minimize it so current Min as well as the smallest element from the current array and we'll do the same thing or the similar thing with the maximums this will be the last element in the array this will be the current maximum and this will also be the current maximum and this will be taking the maximum of both of these but remember before we update this we want to try to update the result so that's going to be set to the max of itself as well as the two equations I was talking about so I don't know if I want to make this nested and then put these on a different line because at that point this might get a little less readable so here I'm going to take the last element from the current array which we can get like this and subtract from it the current minimum the other case is if we have the current Max and subtract from it the smallest element in the current array so this is pretty much the entire solution I don't know if maybe I should just put this on one line if that's more readable or not but I'm going to run this to prove it to you that it works okay it would I swear if we used this variable correctly we created a new variable I guess that's the downside of python that we don't need like a keyword to declare a variable and also I had a very trivial bug actually remember how I said we'd never want to take the current Min and Max from the same array and try to like compute the result that way well I literally did that because I started from the beginning of the array but I already initialized the current Min and Max from the beginning of the array so can you think of what I can do to correct this if so you're doing my job for me I should have started at the second element and so I'll do that like this rather than taking a slice of the array I think it's better to just do it this way spacewise get the length of arrays and let's set array equal to arrays at index I so a pretty simple fix thankfully and now you can see it works and it's pretty efficient I think there is one little thing that we can do in Python I think the max function actually will accept multiple parameters more than two so here we actually could have just gotten rid of that and then had three of these that's the nice thing about python so I think this will also work yep as you can see it does if you found this helpful check out n code. for a lot more and like And subscribe if you want to see more