DETONATE THE MAXIMUM BOMBS | LEETCODE 2101 | PYTHON GRAPH SOLUTION

Problem Link: leetcode.com/problems/detonat...
Discord Link: / discord
In this video we are solving another Google interview question: Detonate the Maximum Number of Bombs (Leetcode 2101). I hope this video doesn't get my channel taken down for saying "detonate bomb" enough times...
This question seems like it might be a hard DP question but it's actually surprisingly a graph question. And quite an intuitive one at that.
TIMESTAMPS:
00:00 Intro
00:18 Question Prompt
01:11 Basic Example
02:23 Solution Intuition
04:24 Coding
09:15 Time/Space Complexity
10:45 Outro

[@AshaYalla]

wow. love your dedication of uploading a new problem every day. thanks a lot.

[@cindysu262]

Thank you the the video. Can you please do LC1105 as well. TY

[@jedholtman9075]

Shouldn't line 28 be T: O(N^2) + O(N^2) -> O(N^2) ? In the worst case we have a fully connected graph built, so we run a N-runtime DFS N total times.

[@annalisa_m]

Actually what you say at 1:20 is not correct, you say that because the circles overlap then any of them would detonate the other. However it is not enough that the circle overlap, but the circle has to include the other point in order to detonate it. The example is explained in the problem description: Input: bombs = [[2,1,3],[6,1,4]] Output: 2 Explanation: The above figure shows the positions and ranges of the 2 bombs. If we detonate the left bomb, the right bomb will not be affected. But if we detonate the right bomb, both bombs will be detonated. So the maximum bombs that can be detonated is max(1, 2) = 2.

[@crackfaang]

Yea I misspoke, the solution is based on the radius though

[@annalisa_m]

@@crackfaang Thanks, yes the answer is correct, thank you for posting in btw. Just wanted to mention that little details in case ppl might get confused. Keep posting these great videos please! Thank you!