Video Explanation - Math to Graph to DFS clear explanation [Java]
Approach\nhttps://youtu.be/hTqokf-HCqg\n\n# Similar Problems:\n\n- 463. Island Perimeter\n- 657. Robot Return to Origin\n- 200. Number of Islands\n- Number of I
# Approach\nhttps://youtu.be/hTqokf-HCqg\n\n# Similar Problems:\n\n- [463. Island Perimeter](https://leetcode.com/problems/island-perimeter/)\n- [657. Robot Return to Origin](https://leetcode.com/problems/robot-return-to-origin/)\n- [200. Number of Islands](https://leetcode.com/problems/number-of-islands/)\n- [Number of Islands II](https://leetcode.com/problems/number-of-islands-ii/)\n- [547. Number of Provinces](https://leetcode.com/problems/number-of-provinces/)\n- [2316. Count Unreachable Pairs of Nodes in an Undirected Graph](https://leetcode.com/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/)\n- [Number of Distinct Islands](https://leetcode.com/problems/number-of-distinct-islands/)\n- [Number of Connected Components in an Undirected Graph](https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/)\n- [130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)\n- [2658. Maximum Number of Fish in a Grid](https://leetcode.com/problems/maximum-number-of-fish-in-a-grid/)\n- [994. Rotting Oranges](https://leetcode.com/problems/rotting-oranges/)\n- [695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/)\n- [529. Minesweeper](https://leetcode.com/problems/minesweeper/)\n\nI suggest you also solve the above mentioned problem. They can be solved using dfs, bfs or union find algorithms.\n\n# Complexity\n- Time complexity: $$O(N^3)$$\nBuilding the graph takes $$O(N^2)$$ time. The time complexity of a typical DFS is $$O(V+E)$$ where $$V$$ represents the number of nodes, and $$E$$ represents the number of edges. More specifically, there are $$n$$ nodes and $$n^2$$ edges in this problem. We need to perform $$n$$ depth-first searches.\n\n- Space complexity: The space complexity of DFS is $$(N^2)$$. \nThere are $$(n^2)$$ edges stored in **graph**.\n\n# Code (DFS):\n``` Java []\nclass Solution {\n    int n;\n    public int maximumDetonation(int[][] bombs) {\n        int res = 0;\n        n = bombs.length;\n        for(int i=0; i<n; i++) {\n            int[] bomb = bombs[i];\n            boolean[] seen = new boolean[n];\n            seen[i] = true;\n            res = Math.max(res, dfs(bombs, i, seen, 1));\n        }\n        return res;\n    }\n\n    int dfs(int[][] bombs, int bombIndex, boolean[] seen, int detonate) {\n        int[] curBomb = bombs[bombIndex];\n        for(int i=0; i<n; i++) {\n            if(i==bombIndex || seen[i]) {\n                continue;\n            }\n            int[] bomb = bombs[i];\n            int x1 = curBomb[0];\n            int y1 = curBomb[1];\n            long r1 = curBomb[2];\n\n            int x2 = bomb[0];\n            int y2 = bomb[1];\n            int r2 = bomb[2];\n\n            long dx = (x1-x2);\n            long dy = (y1-y2);\n            if(r1*r1 >= dx*dx + dy*dy) {\n                seen[i] = true;\n                detonate+=dfs(bombs, i, seen, 1);\n            }\n        }\n        return detonate;\n    }\n}\n```
['Depth-First Search', 'Java']