Find All People With Secret - Leetcode 2092 - 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 😂😂

[@電腦騙徒剋星]

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@@電腦騙徒剋星

[@yang5843]

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

[@Decklun]

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

[@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.

[@pastori2672]

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

[@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); } }

[@deepaksingh7042]

SIMPLEST Approach: 1. Sort meetings in ascending order of time. 2. Push first person in hashset. 3. Iterate the meetings in ascending order of time. If any person in meeting knows secret (i.e. if anyone of them is already in hashset), then add other person also in hashset. 4. After iterating all meetings , the size of hashset gives the number of people having secret.

[@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

[@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.

[@edmonddantes587]

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

[@Munchen888]

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

[@Rahul-lg1nw]

Epic pen

[@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

[@refertechno]

Would you please explain about data engineering and its future?

[@dipeshprajapat1203]

can guid where i am going wrong

[@anirbandas12]

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

[@mfizt2537]

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

[@Yougottacryforthis]

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

[@harshithdesai9989]

90K subscribers for neetcode!! wow!!

[@vikramahuja5352]

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

[@manuelscott9078]

paint 3d

[@sherloccode6272]

Thanks @NeetcodeIO

[@CS_n00b]

havent done a dfs in a while

[@utibeokodi4997]

@NeetCodeIO very well done

[@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.

[@MP-ny3ep]

Great explanation as always. Thank you

[@pingbaoNRi]

thanks a lot

[@UrsKarthikHere]

Thank you bro

[@SC2Edu]

Pretty good, thanks!!

[@dipeshprajapat1203]

Great Explanation

[@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; } };

[@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)