Detonate the Maximum Bombs | DFS | BFS | GOOGLE | Leetcode-2101 | Live Code + Explanation 🧑🏻💻
Vložit
- čas přidán 1. 06. 2023
- This is the 29th Video on our Graphs Playlist.
In this video we will try to solve a very good Graph Problem with amazing problem statement "Detonate the Maximum Bombs " (Leetcode - 2101)
We will solve it using :
1. DFS
2. BFS
I am promising you, this problem will become easy once you are done with this video.
If you have been following my "Graph Concepts & Qns" playlist , then these Qns will become very easy. Find the Link for that below.
We will do live coding after explanation and see if we are able to pass all the test cases.
Problem Name : Detonate the Maximum Bombs
Company Tags : GOOGLE
My solutions on Github : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/detonat...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips
#interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook
Ur content is very good , please continue ur work
Thank you so much
Indeed
True
Wow brother no one explains like you
Thanks a lot Shaam ❤️❤️
You have a gifted talent to make Qns look easy. The way you explain is just unmatchable.
MIK Sir this video rocks...Best Video Intitutions was very awesome 😃
Thank you so much ❤️❤️❤️
very nice explaination
This channel is unbelievably good. I am shocked very few people know this legend. Let’s make this guy famous 🔥🔥🔥
great explanation one thing to add for each node there may be (n-1) edges ( i.e Complete graph) in worst case so dfs would take n^2 time and we need to run dfs for each node so time complexity would be n^3 in worst case
Exactly.
Thanks for sharing Anand ❤️❤️❤️
You stand alone. No one explains like you
Great Video as always ❤
Thanks a lot ❤️❤️
very nice explanation
The best😊
thank you !
One of the best explanations
Thanks a lot
Thanks
Java implementation:
BFS:
class Solution {
private int BFS(Map adj, int i) {
Queue q = new LinkedList();
Set visited = new HashSet();
q.offer(i);
visited.add(i);
while(!q.isEmpty()) {
int u = q.peek();
q.poll();
//if(!adj.containsKey(u)) return visited.size();
for(int v : adj.getOrDefault(u, new ArrayList())) {
if(!visited.contains(v)) {
q.offer(v);
visited.add(v);
}
}
}
return visited.size();
}
public int maximumDetonation(int[][] bombs) {
Map adj = new HashMap();
int n = bombs.length;
//build the graph
for(int i=0; ij
adj.computeIfAbsent(i,k->new ArrayList()).add(j);
}
}
}
int result = 0;
//from each node find the maximum nodes that can be visited
for(int i = 0; inew ArrayList()).add(j);
}
}
}
int answer = 0;
//from each node find the maximum nodes that can be visited
for(int i=0; i
There is similar question asked in Google interview but instead of bomb they gave routers and devices but concept is same
4k :)
really good explanation thanks
Thanks a lot Vineet ❤️
Bhaiyaaaaaa aap ek baar topic wise divide kar do na is playlist ko aapka explanation bada accha lagta hai but ek baar topic wise playlist bana doge to accha rahega
Hi Dheeraj,
If you check my playlist section,
There are topic wise different playlists.
I am sure that will help ❤️❤️❤️
@@codestorywithMIK yes got it bhaiya... Thank you so much 🙏❤️👑
Gold content
❤
Let circle1 => x1=2, y1=2, r1=2
and circle2 => x2=5, y2=2, r2=2.
Distance between centres: sqrt(3*3 + 0) = 3
Here, r1 (2
Note that the detonation doesn’t take place if the circle intersects.
A bomb (say B1) will detonate another bomb (say B2) only if the coordinate of centre of the bomb B2 lies inside the range of Bomb B1
@@codestorywithMIK Got it. Thanks.
class Solution {
public:
int dfs(int root,vector&visited,vector&adj){
visited[root] = true;
int result = 0;
for(int node : adj[root]){
if(!visited[node])result += dfs(node,visited,adj);
}
return 1+result;
}
int maximumDetonation(vector& bombs) {
vectoradj;
int n = bombs.size();
for(int i=0;i
sir one doubt , i made a unidirected graph , jaise example me b1 and b2 agr b2 b1 ke andar arha ahi toh b1 wil destroy b2 and if b2 radius is small he won't be able to detonate b1 but b2 is already inside b1 there is some common part so we can't say that b2 will destroy b1 also ?
Hi Sidharth,
Any bomb (say Bomb1) will be destroyed by other bomb (Bomb2)
IF,
The Bomb1 comes INSIDE or ON the radius of Bomb2
@@codestorywithMIK got it sir
Hi everyone can someone tell me why if we find distance btw two centers and store it in long long and compare it with radius ( radius >= dist ) it fails for the second last test case , but if we use double to store distance it gives the correct output can someone tell me why it happens
Bc sqrt will be calculated in double and if you turn it to long long some values will be lost which are after the decimal point . Just like floor divison. This will give wrong answer.
@@Coding4211 mitr hm to radius >= dist le rhe to jade se jade dist km hoke radius ke equal ho jaega tb v to condition true h correct me if I'm wrong?
Yhi toh problem h equal nhi ana h. Distance agr jyada h toh usse km karoge toh answer increase nhi hojayega.
The bombs which should not be included will also come in the range
@@Coding4211 agar radius > dist use kre (dist ko double lene ke baad v) to ye nhi work krega fine? To Maan lo agar mera dist 7.8069 aa rha and radius 7 hai to agar mai dist ko long long me v lelu tb v to wo atleast radius ek equal hoga
taking the sqrt to calculate the distance is giving a wrong answer. I also tries Manhatan Distance. It is also giving a wrong answer. But I tries a different approach to calculate number of connected nodes using DFS. Can you please tell me where I went wrong.
```
class Solution {
public:
int cnt = 0;
void DFS(int node, unordered_map &adj, vector &visited)
{
visited[node]=1;
cnt++;
for(auto child: adj[node])
{
if(!visited[child])
DFS(child, adj, visited);
}
}
int maximumDetonation(vector& bombs) {
int n = bombs.size();
unordered_map adj;
vector visited(n, 0);
for(int i = 0; i
Hey Tauquir.
You missed to reinitialize the visited array for other nodes after you call DFS for a node.
Just add
visited = vector(n, 0);
After your DFS call.
It will work like a charm
@@codestorywithMIK ohhhk.... Thanks a lot ❣️
Hello sir. I was facing a problem in this question. Actually my code is passing 161/162 test cases...don't know why the last test case is failing. Can you kindly help me point out the mistake in my code. Thanks for a wonderful explanation though:)
void dfs(int&node,vectoradj[],vector&visited,int&c)
{
visited[node]=true;
c++;
for(auto &it : adj[node])
{
if(!visited[it])
dfs(it,adj,visited,c);
}
}
int maximumDetonation(vector& bombs) {
int n= bombs.size();
vectoradj[n];
for(int i=0;i
Time complexity?
We call BFS/DFS for each n node --- (i)
For each node , we will have to visit n edges in worst case .
Worst case, the number of edges can be (n-1)
So it makes T.C = n*(n-1) ~ n^2 --- (ii)
From equation (i) and (ii)
TC ~ O(n^3)
Bahi questions ka input samjh nhi ayaa 😢😢
Sir can you also upload that PDF that you are making in video in GitHub?
There You written very nice it will be useful when we have to revise the concept.
Hi there,
Actually i have not yet prepared the PDF yet.
But i put all my code on Github, and have also mentioned the youtube link in the top of every solution.
So that anyone sitting anywhere just open my github repo, open the problem in my github repo, see the code and also open the youtube link mentioned in the top of the code to see the video also
@@codestorywithMIK but at the time of revising we have to again watch the video.
Yes,
I will later try to create PDF for sure ❤️❤️