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.
1def removeStones(stones):
2 from collections import defaultdict
3
4 def dfs(x, y):
5 for nx, ny in graph[(x, y)]:
6 if not visited[(nx, ny)]:
7 visited[(nx, ny)] = True
8 dfs(nx, ny)
9
10 graph = defaultdict(list)
11 for i, (x1, y1) in enumerate(stones):
12 for j, (x2, y2) in enumerate(stones):
13 if i != j and (x1 == x2 or y1 == y2):
14 graph[(x1, y1)].append((x2, y2))
15
16 visited = defaultdict(bool)
17 connected_components = 0
18
19 for x, y in stones:
20 if not visited[(x, y)]:
21 visited[(x, y)] = True
22 dfs(x, y)
23 connected_components += 1
24
25 return len(stones) - connected_componentsThe code uses DFS to explore each cluster of stones by recursively visiting every stone that shares a row or column with the current stone. The graph is constructed where each stone's coordinates map to a list of other stones it is directly connected to (either via the same row or column). By counting the number of unique connected components (rooted at stones we start a DFS on), we subtract the number of components from total stones to get the maximum removable 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.
1import java.util.*;
2
This Java solution implements a Union-Find structure to join stones, marking components that are determined through shared rows and columns. The unique connected components' roots reduce the total number of stones to provide the answer.