Find All People With Secret - Leetcode 2092 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🧑‍💼 LinkedIn: / navdeep-singh-3aaa14161
🐦 Twitter: / neetcode1
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
Problem Link: leetcode.com/problems/find-al...
0:00 - Read the problem
0:12 - Drawing Explanation
7:36 - Coding Explanation
leetcode 2092
#neetcode #leetcode #python

[@drkrn]

Can't wait for my interview to have this question so I can code a basic CRUD for a living

[@whetfaartz6685]

LOL

[@zaki_1337]

use binary search to speed it up

[@deadlyecho]

How fucken accurate 😂😂

[@user-vn4jw3ch8w]

why crying and apply for google if you just want to do crud and memorize shit , if you want to be crud and hate LC , just stop applying fang and stop the bs jealousy against it , simple as that

[@mxderntimes]

thast not what OP is saying, but that companies will ask a hard ass problem and then you're struck doing CRUD work far below the level of the interview questions lol@@user-vn4jw3ch8w

[@yang5843]

Whenever I'm struggling with Leetcode, I turn to Neetcode.

[@1vader]

I solved it using union find, using a DFS is so much simpler, for some reason I didn't think about that at all. Took me a bit to remember how to implement union find and I'm probably not doing enough path compression to achieve the expected union find time complexity (I'm only compressing the paths of the second union when merging) but it passes and compares decently well to other Python solutions.

[@MP-ny3ep]

Great explanation as always. Thank you

[@SC2Edu]

Pretty good, thanks!!

[@dipeshprajapat1203]

Great Explanation

[@sherloccode6272]

Thanks @NeetcodeIO

[@Decklun]

I'm about to do something kind of intelligent 🤓☝ but fr great video as usual

[@utibeokodi4997]

@NeetCodeIO very well done

[@karthik_ujjuru]

Thank you bro

[@Munchen888]

Before watching your video completed 39/55 of this current task 😊

[@harshithdesai9989]

Same bro. I got stuck at the case where we have to check for meetings that are occuring at the same time.

[@mfizt2537]

you can obtain the min and max timings and loop that range instead of sorting 🤗

[@pingbaoNRi]

thanks a lot

[@refertechno]

Would you please explain about data engineering and its future?

[@edmonddantes587]

solved with union find but it took me over an hour. In an interview setting, I'd have no chance

[@harshithdesai9989]

90K subscribers for neetcode!! wow!!

[@amitchoraria5737]

Getting TLE in c++. Same approach as in the video. class Solution { public: map timeMap; unordered_set secret; vector findAllPeople(int n, vector& meetings, int firstPerson) { for(auto m:meetings){ timeMap[m[2]][m[0]].push_back(m[1]); timeMap[m[2]][m[1]].push_back(m[0]); } secret.insert(0); secret.insert(firstPerson); for(auto [time,adj]:timeMap){ unordered_set visited; for(auto [src,destinations]:adj){ if(secret.find(src)!=secret.end()) dfs(src,timeMap[time][src],visited,time); } } vector ans(secret.begin(),secret.end()); return ans; } void dfs(int src,vector dst,unordered_set& visited,int time){ if(visited.find(src)!=visited.end()) return; visited.insert(src); secret.insert(src); for(auto d:dst){ dfs(d,timeMap[time][d],visited,time); } } };

[@sunshinesoul73]

class Solution { public: void dfs(unordered_map &graph,int root,unordered_set &st,unordered_map &vist){ if(vist[root]) return ; vist[root]=true; st.insert(root); for(auto x:graph[root]){ dfs(graph,x,st,vist); } } vector findAllPeople(int n, vector& meetings, int firstPerson) { map hm; for(auto x:meetings){ hm[x[2]][x[0]].push_back(x[1]); hm[x[2]][x[1]].push_back(x[0]); } unordered_set st; st.insert(0); st.insert(firstPerson); for(auto time:hm){ unordered_map vist; for(auto uhm:time.second){ if(!vist[uhm.first] && st.count(uhm.first)){ dfs(time.second,uhm.first,st,vist); } } } vector res; for(auto x:st) res.push_back(x); return res; } };

[@amitchoraria5737]

Update: missed the & in the parameter list of the dfs function vector dst ---> vector& dst

[@Munchen888]

Nick, tell please. What programme do you use to draw on 📺 screen ?

[@Rahul-lg1nw]

Epic pen

[@sdemji]

Am i chasing a unicorn here or is it possible to sort the meetings so that whenever there is a tie with the time , we arrange the data per distance from firstPerson or 0

[@dipeshprajapat1203]

can guid where i am going wrong

[@pastori2672]

i used a deque instead of recursion and it gets tle for some reason

[@CS_n00b]

havent done a dfs in a while

[@vikramahuja5352]

What drawing software do you for the explanation??...seems good

[@manuelscott9078]

paint 3d

[@JayMo183]

He’s accessing a set variable , visit, before it’s been assigned in function dfs. How is he avoiding a “local variable 'visit' referenced before assignment” error?

[@zaki_1337]

nicely

[@1vader]

He's not. dfs is only called after visit is defined.

[@anirbandas12]

Can anyone comment the js solution here im a bit stuck ..

[@Yougottacryforthis]

Why not UF it's way cooler and more efficient too

[@lakshmanvengadesan9096]

Same solution gives tle in c++

[@NeetCodeIO]

Can you paste the code here?

[@erkhesnyamsaikhan4385]

I got TLE too. Try to use reference and don't forget to minimize the data structure you are using. map ( I used something like this globally) Update: It seems that many people are experiencing TLE when implementing BFS. Here is my solution: class Solution { public: vector hasSecret; map timeToAdj; vector findAllPeople(int n, vector& meetings, int firstPerson) { hasSecret = vector(n, false); hasSecret[0] = true; hasSecret[firstPerson] = true; for (auto& meeting: meetings) { int x = meeting[0]; int y = meeting[1]; int time = meeting[2]; timeToAdj[time][x].push_back(y); timeToAdj[time][y].push_back(x); } for (auto& el: timeToAdj) { auto adj = el.second; queue q; for (auto edge: adj) { if (hasSecret[edge.first]) q.push(edge.first); } while (q.size()) { int i = q.front(); q.pop(); for (int j: adj[i]) { if (!hasSecret[j]) { hasSecret[j] = true; q.push(j); } } } } vector res; for (int i = 0; i < n; ++i) { if (hasSecret[i]) res.push_back(i); } return res; } };

[@adityaiiitr]

​@@NeetCodeIO class Solution { public: setsecrets; void dfs(map& graph, int source, set& visited) { if (visited.find(source) != visited.end()) return; visited.insert(source); secrets.insert(source); vector& neighbors = graph[source]; for (int neighbor : neighbors) { dfs(graph, neighbor, visited); } } vector findAllPeople(int n, vector& meetings, int firstPerson) { secrets.insert({0,firstPerson}); map time_map; for(auto x:meetings){ int person1 = x[0]; int person2 = x[1]; int time = x[2]; time_map[time][person1].push_back(person2); time_map[time][person2].push_back(person1); } for (auto& t : time_map) { set visited; for (auto& p : t.second) { if (secrets.find(p.first) != secrets.end()) { dfs(t.second, p.first, visited); } } } vector result(secrets.begin(),secrets.end()); return result; } }; This code is not giving TLE. Thanks NeetCode.

[@adityaiiitr]

@@NeetCodeIO class Solution { public: setsecrets; void dfs(map& graph, int source, set& visited) { if (visited.find(source) != visited.end()) return; visited.insert(source); secrets.insert(source); vector& neighbors = graph[source]; for (int neighbor : neighbors) { dfs(graph, neighbor, visited); } } vector findAllPeople(int n, vector& meetings, int firstPerson) { secrets.insert({0,firstPerson}); map time_map; for(auto x:meetings){ int person1 = x[0]; int person2 = x[1]; int time = x[2]; time_map[time][person1].push_back(person2); time_map[time][person2].push_back(person1); } for (auto& t : time_map) { set visited; for (auto& p : t.second) { if (secrets.find(p.first) != secrets.end()) { dfs(t.second, p.first, visited); } } } vector result(secrets.begin(),secrets.end()); return result; } }; can we do this in more optimal way?

[@lakshmanvengadesan9096]

@@NeetCodeIO class Solution { public: class MeetingsComparator { public: bool operator()(vector &meeting1, vector &meeting2) { if (meeting1[2] < meeting2[2]) return true; if (meeting1[2] > meeting2[2]) return false; return false; } }; void dfs(unordered_map adj, int node, unordered_set &visited, unordered_set &peopleWithSecret) { if (visited.find(node) != visited.end()) return; visited.insert(node); peopleWithSecret.insert(node); for(int neighbor: adj[node]) { dfs(adj, neighbor, visited, peopleWithSecret); } } vector findAllPeople(int n, vector& meetings, int firstPerson) { MeetingsComparator meetingsComparator; // sort(meetings.begin(), meetings.end(), meetingsComparator); map meetingsMap; unordered_set peopleWithSecret; peopleWithSecret.insert(0); peopleWithSecret.insert(firstPerson); for(vector meeting: meetings) { int x = meeting[0], y = meeting[1], time = meeting[2]; // if (peopleWithSecret.find(x) != peopleWithSecret.end()) { // peopleWithSecret.insert(y); // } if (meetingsMap.find(time) == meetingsMap.end()) { meetingsMap[time] = unordered_map(); } if (meetingsMap[time].find(x) == meetingsMap[time].end()) { meetingsMap[time][x] = unordered_set(); } if (meetingsMap[time].find(y) == meetingsMap[time].end()) { meetingsMap[time][y] = unordered_set(); } meetingsMap[time][x].insert(y); meetingsMap[time][y].insert(x); } for(auto it1: meetingsMap) { for(auto it2: it1.second) { unordered_set visited; if (peopleWithSecret.find(it2.first) != peopleWithSecret.end()) { dfs(it1.second, it2.first, visited, peopleWithSecret); } } } vector allPeopleWithSecret; for(int person: peopleWithSecret) { allPeopleWithSecret.push_back(person); } return allPeopleWithSecret; } };

[@yang5843]

Java Solution class Solution { Set set = new HashSet(); public List findAllPeople(int n, int[][] meetings, int firstPerson) { set.add(0); set.add(firstPerson); Map map = new TreeMap(); for (int[] m : meetings) { if ( !map.containsKey(m[2]) ) map.put(m[2],new HashMap()); if ( !map.get(m[2]).containsKey(m[0])) map.get(m[2]).put(m[0],new ArrayList()); if ( !map.get(m[2]).containsKey(m[1])) map.get(m[2]).put(m[1],new ArrayList()); map.get(m[2]).get(m[0]).add(m[1]); map.get(m[2]).get(m[1]).add(m[0]); } for (int t : map.keySet()) { Set visited = new HashSet(); // System.out.print(t+" "+map.get(t).keySet()); for (int src : map.get(t).keySet() ) if ( set.contains(src) ) dfs(src,visited, map.get(t) ); } // System.out.println(); List l = new ArrayList(set); Collections.sort(l); return l; } void dfs(int src, Set visited, Map map ) { if ( visited.contains(src )) return; visited.add(src); set.add(src); for (int neigh : map.get(src) ) dfs(neigh,visited,map); } }

[@akshayiithyd]

I did it using BFS, but am getting a TLE. def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]: know = set() know.add(0) know.add(firstPerson) meetings.sort(key = lambda x:x[2]) def bfs(meetings): adj = collections.defaultdict(list) q = collections.deque() for a,b,_ in meetings: adj[a].append(b) adj[b].append(a) if a in know: q.append(a) if b in know: q.append(b) while q: node = q.popleft() for n in adj[node]: if n not in know: q.append(n) know.add(n) idx = 0 while idx < len(meetings): m = [] t = meetings[idx][2] m.append(meetings[idx]) idx += 1 while idx < len(meetings) and meetings[idx][2] == t: m.append(meetings[idx]) idx += 1 bfs(m) return know

[@akshayiithyd]

DFS with the same code works for some reason. I find this strange, can someone explain? class Solution: def findAllPeople(self, n: int, meetings: List[List[int]], firstPerson: int) -> List[int]: know = set() know.add(0) know.add(firstPerson) meetings.sort(key = lambda x:x[2]) def dfs(m): visit = set() adj = collections.defaultdict(list) nodes = [] for a,b,_ in m: adj[a].append(b) adj[b].append(a) if a in know: nodes.append(a) if b in know: nodes.append(b) def _dfs(a): if a in visit: return visit.add(a) know.add(a) for nei in adj[a]: _dfs(nei) for node in nodes: _dfs(node) def bfs(m): adj = collections.defaultdict(list) q = collections.deque() visit = set() for a,b,_ in m: adj[a].append(b) adj[b].append(a) if a in know: q.append(a) if b in know: q.append(b) while q: node = q.popleft() for n in adj[node]: if n not in know: q.append(n) know.add(n) idx = 0 while idx < len(meetings): m = [] t = meetings[idx][2] m.append(meetings[idx]) idx += 1 while idx < len(meetings) and meetings[idx][2] == t: m.append(meetings[idx]) idx += 1 dfs(m) return list(know)