Sponsored
Sponsored
This approach models the problem as a graph problem, where each stone can be a vertex and there is an edge between two vertices if the stones share the same row or column. We can perform a DFS to count the number of connected components. The maximum number of stones that can be removed from each connected component is the size of the component minus one.
Time Complexity: O(N^2) where N is the number of stones, due to the pairwise comparison to build the graph. Space Complexity: O(N), due to the space needed for the graph and visited tracking.
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4using namespace std;
5
6void dfs(int node, unordered_map<int, vector<int>>& graph, unordered_set<int>& visited) {
7 visited.insert(node);
8 for (int neighbor : graph[node]) {
9 if (visited.find(neighbor) == visited.end()) {
10 dfs(neighbor, graph, visited);
11 }
12 }
13}
14
15int removeStones(vector<vector<int>>& stones) {
16 unordered_map<int, vector<int>> graph;
17 int N = stones.size();
18 for (int i = 0; i < N; ++i) {
19 for (int j = i + 1; j < N; ++j) {
20 if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
21 graph[i].push_back(j);
22 graph[j].push_back(i);
23 }
24 }
25 }
26 unordered_set<int> visited;
27 int connected_components = 0;
28 for (int i = 0; i < N; ++i) {
29 if (visited.find(i) == visited.end()) {
30 dfs(i, graph, visited);
31 ++connected_components;
32 }
33 }
34 return N - connected_components;
35}This C++ solution constructs a graph connecting stones by shared rows or columns. It uses DFS to explore each connected component of this graph, counting how many such components exist. The result is calculated by subtracting the number of components from the total stones.
This approach models the problem using the Union-Find data structure to group stones that belong to the same connected component. By unioning stones that share the same row or column, we can determine the number of connected components and calculate the maximum number of removable stones by reducing the total number of components from the total stones.
Time Complexity: O(N) average time complexity due to efficient union-find operations. Space Complexity: O(N) for the storage of parent pointers in the union-find structure.
1class UnionFind:
2 def __init__
The code utilizes a Union-Find to manage the connections between stones by mapping an x-coordinate as is, and applying ~ to the y-coordinate to separate row and column spaces uniquely. The solution of maximum removable stones results from the difference between the total stones and the number of unique components.