Minimum Time Difference - Leetcode 539 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum time difference the idea is we're given a 24hour clock just given the hour and the minute so these are some relatively simple examples now for Simplicity let's think of time not as a circle I mean we could draw like the clock we could draw it as a circle and it would probably make sense to do that but let's keep in mind that this is zero and technically we could put like the 24-hour Mark here but a clock will never have 24 hours that itself is actually back to zero so technically the last minute that we can land on remember we're not even keeping track of second so that's actually relatively simple the last minute we could land on is going to be 2359 kind of like the example that they gave for us here and so plus one would make us back here now there could be all sorts of time all through here they gave us again a relatively simple example and I think that's actually an example worth going through because it shows us something very interesting so there's this minute and then there's this minute what we want to know between any two points in time what is the minimum different so let's step back for a second imagine we had an array like this 1 2 3 4 6 whatever it's basically saying what's the minimum difference between two adjacent positions if the array is sorted remember time is technically sorted but that doesn't necessarily mean that the time points that they gave us are sorted so that's something maybe we will have to handle ourselves there's one interesting thing though about this with this example you might think well the difference between these two is going to be 23 hours and 59 minutes but remember that time is a circle plus one will bring us here so that actually does count if I were to draw this as a circle suppose this is minute Z and I'm putting space between them just so it's easier to draw but suppose that this is 2359 there are two distances for these two points one distance is this one and another distance is this one so that's another thing we're going to have to keep in mind that calculating the difference between any two given points there's going to be two possible calculations for that and of course uh this one is a very long distance this is the smaller one that's only one so that's the minimum distance between these two points and so what we return is the difference in minutes so in this example we would return one now let's look at potentially a more interesting example suppose we take all those minutes and sort them let's say we have like three for Simplicity let's say this one is 11 10 I'm just going to try to keep the numbers simple like the numbers themselves don't matter too much and I'll kind of show you why um and then this one I'll just call it 10 10 at a high level the algorithm could be going through every adjacent pair and Computing the difference so what's the difference between these two and when I say difference not just this difference but also like the other difference as well and then just find the minimum between them so this way and doing it this way and then we're done but notice how there's one thing we actually missed potentially just going through one linear pass like let's say we have end points in this example there's three points the way I kind of showed it we're going to have two iterations within our loop we're going to have this iteration and we're going to have this iteration but actually we want one extra can you see which one it is it's possible that this one and this one actually have the minimum distance as well so if we have three points we want to iterate three times one way to handle that the way I'm personally going to handle that is let's say I'm going to have my current pointer here it's going to start at the first point and I'm going to have my previous pointer as well and on the first iteration of the loop I'm going to set my previous pointer to the last element in the list so this way this is what the first iteration of the loop is going to be it's going to compute the distance this way and it's going to compute like the other distance the second iteration of the loop I'm going to take my current pointer shift it over here my previous pointer is just going to go wherever the current pointer was so this is the second iteration of the loop and then the third iteration of the loop is going to be this so that will work out now there's a couple other things I want to mention how are we going to compute the distance well there's two things I want to do one is talk about the conversion cuz dealing with hours and minutes is kind of kind of confusing especially when the return value that we actually care about the way we're Computing the distance itself we only care about the minute so possibly we can convert this to a minute value that's the first thing we're going to cover and the second thing is going to be the fact that we're dealing with two distances for every adjacent pair and I'm going to show you that Computing those distances is actually not that difficult and the reason for that is we actually don't need to do two distances so first for the conversion given a time like this let's say an time 3 hours 49 minutes what do you do you want to convert it to minutes well first of all this is a string you split it by this delimiter the colon most languages have support for this I know python does and so you split it you get two strings 3 and 49 49 is a string convert it into an integer that's pretty easy in Python and I think most languages second thing is we have three hours I mean yeah we're going to need the integer value of it but this doesn't tell us the minutes take this multiply it by 60 and you get the minutes 180 so 180 + 49 is going to give us 229 every string like this can be converted into a minute the smallest minute obviously is going to be zero the largest possible minute is going to be this given that there's 24 hours in a day 24 * 60 is I believe this is going to be 1,200 plus 240 so that's going to be 1440 but remember that the last minute is technically the first minute so the last last minute is really going to be this minus one but anyways like you don't actually need to know what these numbers are I thought it was worth kind of illustrating to you you do need to kind of know that this is going to be the last minute every hour has 60 minutes okay so now that we did the conversion and that two-pointer thing I was talking about why is it that we don't need to actually convert that circular distance well let me show you why remember we're doing this with two pointers we'll have a previous pointer and a current pointer all we have to do actually is just compute the distance between these and then compute the distance between these and remember we're also going to have an iteration for when the current is here and the previous is there that is going to be our first iteration and if we do that for like the two end points that's all we need to do just to make it very clear let me draw the circle just drawing some random points on it we're going to compute this distance suppose this is index zero this is index one this is index 2 and this is index 3 in this example we're dealing with like an Nal 4 example so we're going to compute this distance then we're going to compute this distance and we're going to compute this distance and I did mention that we're going to have one extra iteration to compute the First with the last so which one did we not cover you tell me if we're Computing this distance why would we also want to compute the distance that goes the other way and the reason we don't have to do that is because there actually are additional time points there's no reason to go the long way because we know that there's actually a time that comes before that the fact that we computed this distance means that that one would have been longer anyway and so this works because there are multiple points here there's more than two points now if we only had two points then it would be a little bit more tricky suppose we only had these two points in that case like going this way we're not going to hit anybody first we do have to go all the way around from here and from here we do have to compute that distance we don't necessarily know which one of these is going to be smaller so keeping these points in mind we can solve this problem by taking the times sorting them which is going to be n log n time and depending on the algorithm it could be constant space or it could be linear space but then after that we're just going to do a single pass through the input the first thing I'm going to do is sort the time inputs and since remember like each string is going to be in like the form of this the fact that it's a string it'll sort it automatically cuz this will be the largest precedence and like even if there's a leading zero or something the number of digits will still be the same so like if we were dealing with 10 minutes I'm pretty sure it'll look something like this therefore like the sorting by default will work we're good there don't need any custom sort but we do need to convert times into minutes so given some time T I'm going to do that like this so I'm going to split this now splitting this string based on this delimiter it would give us if we unpack it the hour and the minute this this is going to be a relatively simple function regardless so I might as well show you some little tricks with this one these are strings we want to convert them into integers we could do that on the next line but you can actually do a little functional programming if you want to get fancy we can use the map function and so what this is going to accept is this in iterable this is going to be a list of two strings I believe it's a list it could be another data type but either way it's iterable two strings and then this is going to be the function we want to use to map these strings to something else and right here I'm going to put integer int this will return the hour and the minute in integer form now you might be confused because you see the in word here and you also see it up here here it's kind of confusing this is actually just a type hint in Python this is kind of like the integer type this is not the integer type this is actually a built-in function in Python int is a buil-in function in Python so when we're doing this we're passing in a function so now we're going to return that calculation 60 time the hour plus the minute so we're good there and now I'm actually going to change my Approach just a tiny bit than what I told you before what I told you is we're going to iterate over like the time points and I said we're actually going to iterate for like the entire length of the input not minus one but I'm actually going to do the minus one just because I think it's slightly easier to code up I could show you the other one it's going to be a little bit more confusing so the reason we're only going to iterate minus one is because we're actually going to have another calculation done on the the outside of this so I'm going to return the result what is the result going to be I could initialize it with a really large value I could initialize it to like infinity or something I could also initialize it to 24 * 60 cuz no difference is ever going to be larger than that I'm going to get a little bit clever and remember how we have a list of points like let's say these are our points x y z these are our times with this loop we're going to be able to compute this and we're going to be able to compute this the one that we're not going to be able to compute is going to be the last one with the first one might as well use that calculation and initialize my result with it so that's exactly what I'm going to do now how do we do that calculation think of it like this I'm just going to draw a bunch of zeros like let's say we had an X over well I'm going to put a one here and I'm going to put let's say a one over here we're trying to compute the distance from here to there like in the circular way so in other words we're trying to compute like the length minus this that will give us this portion plus uh this so in other words we take like the total amount of minutes in our timeline subtract from it the right value so the rightmost time the largest time so I'm going to subtract from it I'm going to do the conversion to time to a minute the rightmost in Python that's really easy to get you can do time points at index1 so that's the last one and with that I want to add the beginning portion so I'm going to do plus I'm going to do the conversion as well time to minute time points um at index zero so I'll put this like this just to format it that's what this is doing it's going to be doing the circular part and so this Loop will take care of the rest now you might be thinking about the edge case where we actually only have two points to begin with well in that case the loop is going to be the one that computes this distance from like y - x that distance and then this part is going to be the one that computes how much does it take for y to reach like 24 hours and then with that add the X part like how many minutes do we have to actually get to just in case this isn't clear let me just give you a very concrete example suppose these are the minutes that we're dealing with minute 10 and minute 1430 remember that the max minute is 1440 so what this calculation up here would do is it would say 1440 minus 1430 that's how much it would take 10 minutes is what it would take for us to reset back to zero and once we reset back to zero we just need to reach the 10 minute Mark so do 10 + 10 that would give us 20 just wanted to make this clear but now let's finish things up I'm going to set current equal to time to minute of time points at index I + 1 we're starting at index 0 and then I'm going to set a previous equal to the one to the left of that instead of doing these conversions on every single iteration of the loop one thing we could have done is created a new array where we store the minutes that that would have taken extra space though we could have also overwritten the input array but that might not be allowed so that's why I'm doing it this way like it's not that much more expensive in terms of Big O time complexity at least that said though doing the conversions every single time isn't super efficient since we're doing two for every iteration alternatively we could store like the previous one outside but I don't really care that much to be honest now to compute the difference between these is going to be easy we're going to do right minus left current minus previous and then we're going to try to minimize it result is equal to the minimum of itself as well as the diff that we just computed so this is the entire solution let's run it as you can see it works it's relatively efficient and log in we can technically do better though for very large inputs the fact that there's potentially going to be like a lot of duplicates in here is something we can actually do something about like it looks like the length of time inputs could be up to 20,000 whereas the number of distinct points is probably going to be 1440 so one optimization I guess we could make here is if the result is ever zero if result is equal to zero we can return early so I'll Implement that here and just run it to see how it affects the time so it looks like actually that optimization was enough to bring us to 95% I will still show you the next solution the bucket sort solution let's get into that so just taking everything we kind of learned so far and removing the need for doing a built-in sort which is and login the fact that the constraint is that every time point is going to be in the range from zero up until 14 39 where that's like the minute I'm considering the minute I'm not really worried about the strings anymore so every value is going to be in this range therefore we can Implement sorting like the bucket sorting which is a pretty standard algorithm if you're a beginner I Do cover it on my algorithms for beginner course just thought that was worth mentioning I think these are pretty detailed lessons but to give you the abbreviated version this is what we're going to do I'll just dry run through it cuz it's a pretty simple algorithm we're going to have an array of size this like we're going to have an index for every single minute so index zero all the way up until index 1439 initially we just want to know which minutes exist like initially these will all be false it'll be a Boolean array we could also use an integer array and use zero for false and one for true but this is generally more space efficient I'm not sure how python implements it though now if all of these are false what we're going to do is take each of these convert it to the minute I believe this is going to be 70 or something so at minute 70 we're going to set this to True at minute whatever that happens to be I think it's one 40 that's going to be true as well and then this minute is also going to be true so imagine we have this array it's sparsely populated with TRS most of them are probably going to be falses then we're going to do pretty much the same thing I did earlier we're going to have like two pointers let's call it previous and current we're going to keep Computing like the Delta between these now in this case these are actually going to be indices because previous is going to correspond to the minute let's say minute 70 current is going to correspond to minute 140 and we're going to compute the difference between those those for every adjacent position that has true within it one thing that this solution actually doesn't account for is what if we actually had multiple minutes with 70 well this array doesn't capture that information we can't set true like multiple times in this position it doesn't really do anything so if when we're populating this array if we ever encounter a point where the same minute is set multiple times we immediately return zero cuz if it is then the Delta between those is going to be zero anyway so this is going to be a pretty efficient solution because of that fact alone we also can't like easily get the first and last minute that is set in this array so it'd be hard to kind of compute the circular part there's multiple ways to handle that part I'm honestly not sure which one to show you like I prefer the one where for every two adjacent points we literally compute both we compute this distance and we compute the other distance I prefer that one I'm not really sure what people are going to prefer but in terms of code I kind of think that one's nice and concise and consistent so I might just do that by the way this solution is more efficient because once we've done this conversion it's true that building this array we're going to have to go through every point in the input so that's going to be a linear time operation but then when we scan through the second part that's going to be pretty efficient technically a constant value 1440 and technically a constant amount of space too because it's always going to be a fixed size so let's code this one up so I'm going to start with some of the original code just kind of the starter stuff and I do here have an array which is of length 60 * 24 and it's initially set to false in every position and so what I'm going to do is go through T in time points I'm going to convert that time into the minute so that we can get the index of our array so t to the minute and then what we want to do is something like this exist of this minute is set to True before we can do that though let's check if it's already been set if exists of this minute is true then just immediately return zero cuz the Delta between those two minutes is going to be zero and I also just realized I have this time sorts up here when we actually don't need it that's the whole point of the solution you don't need to sort the input I'm sorry if that was confusing and actually just to keep this solution consistent with the previous one what I'm going to do is something slightly clever I'm going to keep track of the first and the last minute we have remember since we're not sorting time points it's not straightforward to get that so I'm going to take advantage of the fact that we're already looping through them here and I'm going to do something like this the first minute is always going to be the minimal minute that we are uh seeing every single time so from the first minute and the current minute that we have and same thing with the last except we're going to try to maximize that so among all the time points that we have we should be able to get the minimum and Max a minute the first and last minute and the initial values we put here are important if we're trying to minimize the minute if we set it to zero it's never going to go above that so let's make sure to initialize the first minute to 1440 or 60 * 24 and the last minute can be initially very small so that it's maximized and also don't forget to change this to last minute and now we can keep things consistent so I'm going to compute the result the same way I kind of did earlier 60 * 24 subtracted by the last minute or the last Point um plus the first minute or the first point so just like that and now it's kind of interesting what we do here though we could go for minute in range 1440 or the length of our exists array which are both the same the length of this is going to be 1440 but if we do that now the way I want to code this up I want to kind of do the two-pointer approach I want to keep track of the previous minute which I'm going to initialize as the first minute and so we don't want M to also be the first minute at any point cuz if they are if this is then the difference between those is going to be zero so let's make sure to start at first minute + 1 so now this will become very trivial remember this minute may or may not exist we know it exists if it's true in this array so if that's the case we can compute the diff we can say the current minute minus the previous minute and then we can try to minimize that with our result and don't forget to update the previous minute to what the current minute is right now so this kind of two-pointer approach I prefer it you might not you might have your own variation that's perfectly fine feel free to add add it in the comments and now we can just return the result so this is a pretty consistent solution I think it's as consistent as I could make it with the last solution the main difference is going to be this chunk of code over here this is the bucket sort portion and then we initialize the solution and then just the two pointers let's run it very sloppy mistake on my part this should not be time to points this should be time to minute sorry so while this is a linear time solution you can actually see that the runtime just because probably of the overhead of having this array doing the bucket sorting part this is actually not any more efficient than the previous one at least for this relatively small data set which I think the time points is going to be roughly like 10,000 in size if you found this helpful check out NE code. for a lot more thanks for watching and I'll see you soon