Find All People With Secret - Leetcode 2092 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find all people with secret we're given an integer n which represents people numbered from 0 to n minus one we're also given an array of meetings where a meeting consists of one person let's call that X and another person let's call that Y and a third parameter T which tells us the time that that meeting takes place at now before I explain this parameter in depth we're given a third parameter called first person so basically the way this problem works is that initially person zero which they mention over there and the first person which is a second parameter to us so let's say in this example here the first person is one so initially these two people zero and one have a secret the secret is going to be spread via these meetings that is the other parameter here looking at the example down here we have person one is going to have a meeting with person two at time equals 5 among all of these meetings this is the first meeting that is taking place we know initially these two people have the secret and when we have a meeting like this one it means that the secret is now going to be communicated from person one to person two you can almost think of this as like a graph rather than like the meeting interval problems that we would see even though there is definitely a time element to this now one quick clar ification I want to make is that this is actually not directed they mention it in the fine print right over here I actually missed it when I was first trying to solve the problem if we had put these in the opposite order if we had put person two first and then person one second the secret can still be communicated in this direction as well so think of this as an undirected edge so that's very important to note now let's look at the second meeting over here we can see a second meeting takes place at time 8 communica with these two people now you tell me does a secret spread via this meeting well either person two communicates it with person 3 or person 3 communicates it with person two from the first meeting that occurred we actually increased our set of people with the secret from just these two and now we've added this other person as well so yes person two now communicated the secret with person 3 and this is only because the time here happened after after the time here if these meetings happened in the opposite order if this meeting happened at time equals 8 and this one happened at time equals 5 well this meeting happens first person two and three neither of them know the secret so nothing happens here and this happens at time 8 well person one does know the secret so they tell person two so this is different if the meetings were in the original order that I showed we actually end up like this we end up two knowing the secret and now three also knows the secret so this is now the set of people with the secret our goal is just to by the end of all of these meetings return all the people with the secret and there's one last thing because right now believe it or not the problem is relatively trivial but there's one little twist that they throw at us and that is the secrets are shared instantaneously let me show you what they mean by that I think it's already pretty clear that we'd probably want to iterate over the meetings in sorted order based on the time because of course the order that the meetings happen in does matter but when they say that Secrets can be shared instantaneously that means that a person who receives the secret at a certain point in time can share the secret at that exact same time so take a look at this example over here all of these meetings occur at time equals 5 let's go through them in this particular order that I've listed person two and three share the secret well neither of them know the secret person three and four share the secret at the same time neither of them know the secret now person one and two share the secret and one has the secret so they share it with person two so now our set ends up looking like this theoretically since this meeting happens at the same time as these two meetings now person two should be allowed to share it with three so we should be able to add three here and then person three should be able to share it with person four so we can add it here as well but that is only if we go through the elements in a particular order we have to do this one then this one and then this one well when we sort based on time there's no guarantee that the elements are going to show up in that order so we have to think about this in a different way and believe it or not no matter how you sort it it won't matter it won't guarantee anything so the best way to do this is to think about it in terms actually of a graph think about it like this this is our set of people with the secret one shares the secret with two think of it like this two shares the secret with three lastly three shares the secret with four now I've drawn this like a directed graph but it actually is undirected yeah this is what the real graph looks like and now when we go through these I'm going to do something kind of intelligent what I'm going to do is I'm going to check do either of these people know the secret nope they don't so skip it do either of these people know the secret nope so skip it do either of these people know the secret yes yes one does so run a graph traversal starting at one because this is the graph of communications that happen at time equals 5 basically at every single time point we're going to build a graph such as this one and now starting from time equals 1 we know that person one can communicate with person two so okay now this person knows the secret as well let's add them to the result and now person two knows the secret they can communicate with person three that information was provided to us from the first Edge and now from person 3 we can share the information with person 4 which was provided to us via this Edge and we'll add these two to the solution set three and four so now we are allowed to run a traversal starting from any of these and in case there are additional edges in here we will make sure to Mark these as visited as we Traverse them because we don't want to visit them again anytime we visit somebody they have been marked in the secret result and the way I'm actually going to be storing the secret like the people with the secrets is not a list I'm actually going to use a hash set because we can still insert in constant time and we can search that hash set in constant time as well to check if somebody is in the sorted or in the secret hash set or not now before I code this up let me just quickly show you what the graph would look like suppose if these were like disjointed maybe here we have a five and a six at time equals 5 and maybe here we have a seven and an 8 at time equals 5 in this case the graph would be pretty simple we'd have 2 to 3 we'd have 5 to 6 and then we'd have 7 to 8 so the graph doesn't necessarily need to be connected it could be disjointed like this this is why another approach to solving this problem is with the disjoint set data structure AKA Union find that's how I usually refer to it you know DFS is relatively simple in this case and I'll be analyzing the time complexity of DFS at the end it's relatively efficient I think the bottleneck is actually just going to be sorting the meetings based B on time which is going to be I think roughly M log M where m is the number of meetings but now let's just code this up I'm going to initialize first a hashset called secrets that's kind of the result that we're going to be returning and so this is just people with the secret and we know initially zero is always going to have the secret so I'm going to have a zero here and we know this person is also always going to have the secret so let's add them as well so I'm just passing a list into this set which will convert that list into a hash set but before we actually return it you can see they want us to return a list so when we take secrets we are actually going to turn it into a list before we return it now I'm actually going to split the uh meetings based on time so I'm going to have something called a Time map maybe the name could be better but basically this is going to map every single time to an adjacency list of the meetings that occur at that time so that'll make it pretty easy for us to run the DFS on each of those adjacency lists we can initialize this like this for every Source destination time in the meetings so we're unpacking all three of these from each meeting and then we're going to check well if this time is not in the time map yet let's go ahead and insert it like this so we're mapping this time to a hashmap which in our case is going to be a default dictionary where the default value is going to be an empty list so then we can go like this time map for this particular time let's go ahead and say to the source let's append the destination and to the destination whoops let's append The Source basically this is the part where the edges are undirected that's really important when I was first coding this up I missed the second part and I couldn't figure out why it wasn't working always make sure to read the fine print in the problem description okay now before I actually implement the DFS I'm going to show you how we're going to call the DFS first we want to go through the times in sorted order but I haven't even sorted them yet well I'm going to do it conveniently like this first I'm going to take all the keys in the time map so that will give us the unique times cuz remember time was the key here so we won't have any duplicates here I'm going to take this and I'm going to sort it after I turn this into a list I'm not even sure if we actually need to turn it into a list I think we probably don't I don't know the type that this returns I don't think it's a list but I think we can probably just do it like this without transforming it so let's stick with this so we're going through the times in sorted order first let's think of it this way let's get the time map at time T this is an adjacency list so in this adjacency list we kind of have every single edge within that adjacency list so we want to consider every single key in this ad jcy list and consider it as the source node and for every single Source node we want to contemplate should we run a DFS from this Source or not and remember we only run a DFS if the source is in the Secret's hashset because only then can the secret be spread from the source to the other nodes so then we will here run a DFS we don't want to have duplicates be Revisited that would make the DFS inefficient we want to guarantee we only visit each node in that graph at most once so we will declare a visit hashset up here the fact that we do it here is very important do not declare it in here because then you'll basically be creating a new visit hash set every time we run a DFS but we want to share that among all of the dfs's for this particular adjacency list so for the DFS I'm going to pass in the source node and I'm going to pass in visit this is actually op in Python to cut down how many variables we pass in how many parameters or arguments we pass in here I'm actually not going to pass visit in you can if you want to but this DFS will have access to every variable out here and here I'm only going to pass in the source I'm not going to pass in visit but I am going to pass in Time map at time equals T we technically don't need to do that but I think it just makes it significantly more readable if we have DFS here and and we have this other variable called adg basically short for adjacency list rather than from here having to refer to Time map at T So this just makes it a bit more readable that's why I'm doing this for the actual implementation here it's not going to be super crazy we don't want to visit the same node more than once so if source is in visit then return don't do another traversal from there but if it's not been visited then make sure to add it to the visit hash set and also let's make sure to add this to the Secrets because the secret has just been communicated to this node it's possible that the secret was already communicated to it which in that case we won't end up adding duplicates here because we intelligently used a hash set rather than a list so there we go there now for the recursive step we're going to go through every neighbor of the source node and we can do that really easily like this in the adjacency list get all of the neighbors of the source node for every single neighbor run a DFS on on that neighbor and also pass in the adjacency list this DFS has access to the visit hashset that was declared over here before we call DFS it also has access to Secrets which was declared up there now if you want to you could pass those variables in to the function it's up to you whatever makes more sense but zooming out you can see that this is the entire code on the left you can see it does work and it is pretty efficient so let me actually analyze the time complexity here we're building a hash map but the size of the hash map is going to be proportionate to the number of meetings so you can think of the space complexity as being Big O of M technically you could say it's also Big O of n where n is the number of people we could technically have more people than there are meetings if every single meeting has two people but I think they're proportional so it doesn't really matter too much in my opinion and of course the space complexity partially comes from the visit hash set but the bottleneck I think is going to be Time map so you could think of this as the space complexity in terms of time complexity going through every meeting that's definitely not the bottleneck because we're actually sorting the time keys in the worst case so we could have a time for every single meeting so you can say the time complexity is Big O of M log M and we also will potentially go through every single person even with the graph traversal even though there's no repeated work so you could think of this as being M log M plus n but again I think this is actually sufficient for the time complexity because m is going to be proportionate to to the number of people we have if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon