947. Most Stones Removed | BFS | DFS | Leetcode POTD Explained

[@codeby_naruto]

Code :- class Solution { public: // Function to check if two stones are in the same group (same row or column) bool areSameGroup(vector& stone1, vector& stone2) { return stone1[0] == stone2[0] || stone1[1] == stone2[1]; } // Depth-first search to mark all stones connected to the current stone void dfs(vector& visited, vector& stones, int idx) { visited[idx] = 1; for (int i = 0; i < stones.size(); i++) { if (!visited[i] && areSameGroup(stones[idx], stones[i])) { dfs(visited, stones, i); } } } // Main function to find the maximum number of stones that can be removed int removeStones(vector& stones) { int numStones = stones.size(); vector visited(numStones, 0); int groups = 0; // Iterate over each stone and perform DFS if it's not visited for (int i = 0; i < numStones; i++) { if (!visited[i]) { groups++; dfs(visited, stones, i); } } // The maximum number of stones that can be removed is total stones minus the number of groups return numStones - groups; } };

[@shubhamjaiswal7645]

[@MP-ny3ep]

Beautiful explanation bro

[@codeby_naruto]

Thank you ❤️❤️