Detonate the Maximum Bombs - Leetcode 2101 - Python

[@aq6910]

Hopefully you don’t get raided by the fbi after they read the title

[@kartikeyrana3736]

funny thing is, i brute forced my way through this problem once i saw bombs.length

[@arvindsingh7275]

Time Complexity: Assume N as the vertex Creation of adjacency list: O(N^2) DFS function: O(N^2) according to the above video implementation but it can be brought down to O(N) if we use visited check inside for loop. We call the DFS function for N times So, Overall time complexity: O(N^3) but it can brought down to O(N^2) OR Theta(N^2 + N^3) if improved using above suggestion then it will be Theta(2N^2) Space will be O(N^2) because we are storing adj.get(i).add(j) and adj.get(j).add(i)

[@Frank-pg7xx]

ln 5 and 6 to create none duplicate pairs while taking out when i == j is magic. It makes sense when you see it however in an interview I wouldn't be able to find this solution.

[@mohithadiyal6083]

It's the best explanation ever

[@Pegasus02Kr]

Great lecture sir. I couldn't even think of graph solution alone.

[@uptwist2260]

I fell into a trap of trying to cache the number of visited nodes for each node but it didn't work. I figured out why in the end but I had a very difficult time understanding why. If you want to know, lets say we have node 0 mapping to node 1 and 2. And we have node 1 mapping to node 0. 0 => [1, 2] 1 => [0] If we recursively go through node zero, we would cache 0 => 3, 1 => 1, and 2 => 1. The cache meaning `node => number of visited nodes`. After node 0, If we start recursively going through node 1, we would check our cache and see that node 1 only visits 1 node, and then return 1, WHICH IS INCORRECT, because node 1 maps to node 0 and node 0 maps to 1 other node. This was annoying for me to wrap my hand around at first but yeah, caching in this problem does not work. I tried other ways of caching also, but they did not work as well for a similar reason. My intuition from the start was that maybe you can also solve this using union find, but I have not tried it yet. If anyone knows if it works or doesn't, please let me know. edit: union find will not work. quoting from discussions: `will not work.consider a small circle in range of two big circles.but both big circles not in range of each other.union find gives 3 but correct answer is 2 .because a big circle can detonate a small circle but small circle cant detonate the other big circle` also according to discussions and google: `Union-Find is NOT applicable on DIRECTED Graphs`. oops.

[@mahimanzum]

This comment should be pinned as a top comment. Thanks

[@deadlyecho]

Very good mate.. 👍

[@pranshu_awasthi]

Can we do a workaround here , where the cache value of all the nodes in a strongly connected component is equal. For eg. 1 -> 2,3 2 -> 3 -> 2, 4 4 -> 2, 3, 5 5 -> 2, 3, 4 If we start traversing from 3 /4 / 5 , we'd be able to cover 4 nodes , so we'll naturally cache them as 4 But , we'll also cache 2 -> 4 because that does not mean we can move to 3 other nodes from 2 but that would mean that 2 is a part of a component in which 4 nodes are present. This way , when we start the traversal from 1 , and move to 2 It'll get the cache as 4 & return. Would this work ? Any suggestions ?

[@ihsannuruliman4005]

It's simple, dp won't work if there's no recurrence relation. you have to determine if it's possible to get the value of a node without traversing. in that the node has to have all the information needed to get the value directly. in this case it can't, because you need information about the nodes that are already visited before going to this node. You can try hard to also cache the visit set as well (for example using bitmasking), but performance speaking will not change the overall TC. I never think about using DP for this kind of problem. The concept is clear once you really understand dp.

[@suneosama939]

Cna anhbody explain dfs do you write line 15 first or line 23 first?

[@MP-ny3ep]

Great explanation as always ! Thank you

[@working7343]

if getting error on 162 test case, ceil() the distance calculated ;)

[@kb-ru4md]

Dont watch in airport:p awesome videos

[@YT.Nikolay]

ok, I watched till 3:15 and then I solved the problem by myself, but graph... I would not solve it without a hint, I was thinking this is an interval problem, or heap

[@babai2196]

interval problems are generally lies on x axis

[@yolo3659]

I do not understand how the time complexity is O(n^3). For every starting node you will at max visit every other node exactly once in a dfs. So the time complexity is O(n^2).

[@hemanth.alluri]

It's because you have to DFS for every node in the graph.

[@hemanth.alluri]

And DFS itself takes O(n^2) time.

[@user-le6ts6ci7h]

Nope the time complexity is o(n^2) no matter what you are not going to visit more than n node for a start jode

[@TheSmashten]

You don't actually have to make an adjacency list, though. Otherwise great code

[@sumanshukumarshaw8157]

I love your explanations ,can you Please solve the problem "2127. Maximum Employees to Be Invited to a Meeting" please!!!!:)

[@Walid-Sahab]

bset explanation 🌟

[@AMX0013]

I want to solve this with union find but failed for a testcase. Base idea being whenever ther is an edge, we create an union. And based highest ranked component is the max bombs detonated. I tried with chatgpt to understand why its not possible but im not satisfied yet. Can you please help me with this itch!!!

[@dakshir1124]

Did you figure out why?

[@DrSilvey]

AMBATABLOW

[@champion5946]

For C++ Coders Maybe getting OverFlow (Because I Was Getting 😥😥) While Calculating DISTANCE for(int i = 0; i < n; ++i) { long long x1 = bombs[i][0], y1 = bombs[i][1], r1 = bombs[i][2]; for(int j = i + 1; j < n; ++j) { long long x2 = bombs[j][0], y2 = bombs[j][1], r2 = bombs[j][2]; double distance = sqrt((long long)((x1 - x2) * (x1 - x2)) + (long long)((y1 - y2) * (y1 - y2))); if(distance

[@Btcrock00]

Don't calculate the root instead compare it with square of radius.

[@sushantsrivastav]

I was asked this question in an interview yesterday. I am not making this up.

[@johnnychang3456]

Man I can't imagine being given this problem during interview. My brain would black out completely.

[@suneosama939]

Why return 0 if i in visit? I don't understand

[@binfos7434]

You can return `None` if you want. He returned `0` because he may have wanted to use a counter but then decided not to.

[@YT.Nikolay]

this problem is crazy >_

[@lakshmanvengadesan9096]

Understanding that this is a graph problem is the hard part

[@ankurgoswami4441]

if u know it is graph problem, after that it is pretty easy, textbook DFS

[@mathew5659]

Great solution! Can we use disjoint sets for this problem? as we're constructing the graph from nothing

[@16avikasgupta70]

Ya even I was thinking the same because it can be thought of finding the max number of nodes in connected component but the problem is how we are going to apply dsu

[@umeshhbhat]

No, we ca not as the graph wont be bidirectional. For eg: if A can detonate mean does not necessarily mean that B can detonate A

[@venky3639]

How tf u got the intuition to solve it with a graph 😢