Detonate the Maximum Bombs - Leetcode 2101 - Python
Vložit
- čas přidán 25. 07. 2024
- Solving Leetcode 2101 - Detonate the Maximum Bombs, today's daily leetcode on June 1.
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/detonat...
0:00 - Read the problem
0:35 - Drawing Explanation
6:12 - Coding Explanation
leetcode 2101
#neetcode #leetcode #python
Hopefully you don’t get raided by the fbi after they read the title
Great explanation as always ! Thank you
Great lecture sir. I couldn't even think of graph solution alone.
It's the best explanation ever
funny thing is, i brute forced my way through this problem once i saw bombs.length
Cna anhbody explain dfs do you write line 15 first or line 23 first?
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.
I love your explanations ,can you Please solve the problem "2127. Maximum Employees to Be Invited to a Meeting" please!!!!:)
Dont watch in airport:p awesome videos
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!!!
bset explanation 🌟
if getting error on 162 test case, ceil() the distance calculated ;)
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
interval problems are generally lies on x axis
Great solution! Can we use disjoint sets for this problem? as we're constructing the graph from nothing
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
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
this problem is crazy >_
Understanding that this is a graph problem is the hard part
if u know it is graph problem, after that it is pretty easy, textbook DFS
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.
This comment should be pinned as a top comment. Thanks
Very good mate.. 👍
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 ?
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.
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).
It's because you have to DFS for every node in the graph.
And DFS itself takes O(n^2) time.
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
AMBATABLOW
Why return 0 if i in visit? I don't understand
You can return `None` if you want. He returned `0` because he may have wanted to use a counter but then decided not to.
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
Don't calculate the root instead compare it with square of radius.
How tf u got the intuition to solve it with a graph 😢
I was asked this question in an interview yesterday. I am not making this up.
Man I can't imagine being given this problem during interview. My brain would black out completely.