Problem of The Day: Most Stones Removed with Same Row or Column
Problem Statement
Intuition
When I first approached this problem, I recognized that the goal is to remove as many stones as possible while adhering to the rules. The problem essentially boils down to identifying connected components, where stones are considered connected if they share the same row or column. With this in mind, I realized that this problem could be effectively solved using a Union-Find (Disjoint Set) data structure, which is well-suited for handling connected components.
Approach
To solve this problem, I implemented the Union-Find data structure. Here’s how I tackled the problem:
-
Initialization: I started by initializing a Union-Find object with each stone initially considered as its own component.
-
Union Operation: I then iterated through each pair of stones. If two stones shared the same row or column, I used the union operation to connect them in the Union-Find structure. This process allowed me to group all stones that could be connected through their rows or columns.
-
Counting Connections: Each time I successfully connected two stones (i.e., they were not already in the same component), I incremented a counter. This counter ultimately represents the maximum number of stones I could remove while still maintaining at least one stone in each connected component.
-
Result: The result is the total number of union operations, which corresponds to the maximum number of stones that can be removed.
Complexity
-
Time complexity:
The time complexity of this approach is (O(N^2)), where (N) is the number of stones. This is because I compare every pair of stones to check if they share a row or column. -
Space complexity:
The space complexity is (O(N)) due to the space required to store the Union-Find data structure, including therootandrankarrays.
Code
class UnionFind():
def __init__(self, n):
self.root = [i for i in range(n)]
self.rank = [1 for _ in range(n)]
def find(self, x):
if x == self.root[x]:
return x
x = self.find(self.root[x])
return self.root[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
if self.rank[root_x] > self.rank[root_y]:
self.root[root_y] = root_x
self.rank[root_x] += 1
elif self.rank[root_x] < self.rank[root_y]:
self.root[root_x] = root_y
self.rank[root_y] += 1
else:
self.root[root_y] = root_x
self.rank[root_x] += 1
return 1
return 0
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
N = len(stones)
uf = UnionFind(N)
res = 0
for i in range(N):
x1, y1 = stones[i]
for j in range(i + 1, N):
x2, y2 = stones[j]
if x1 == x2 or y1 == y2:
res += uf.union(i, j)
return res
Editorial
Approach 1: Depth First Search
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
n = len(stones)
# Adjacency list to store graph connections
adjacency_list = [[] for _ in range(n)]
# Build the graph: Connect stones that share the same row or column
for i in range(n):
for j in range(i + 1, n):
if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
adjacency_list[i].append(j)
adjacency_list[j].append(i)
num_of_connected_components = 0
visited = [False] * n
# DFS to visit all stones in a connected component
def _depth_first_search(stone):
visited[stone] = True
for neighbor in adjacency_list[stone]:
if not visited[neighbor]:
_depth_first_search(neighbor)
# Traverse all stones using DFS to count connected components
for i in range(n):
if not visited[i]:
_depth_first_search(i)
num_of_connected_components += 1
# Maximum stones that can be removed is total stones minus number of connected components
return n - num_of_connected_components
Approach 2: Disjoint Set Union
class Solution:
def removeStones(self, stones):
n = len(stones)
uf = self.UnionFind(n)
# Populate uf by connecting stones that share the same row or column
for i in range(n):
for j in range(i + 1, n):
if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
uf._union(i, j)
return n - uf.count
# Union-Find data structure for tracking connected components
class UnionFind:
def __init__(self, n):
self.parent = [-1] * n # Initialize all nodes as their own parent
self.count = (
n # Initially, each stone is its own connected component
)
# Find the root of a node with path compression
def _find(self, node):
if self.parent[node] == -1:
return node
self.parent[node] = self._find(self.parent[node])
return self.parent[node]
# Union two nodes, reducing the number of connected components
def _union(self, n1, n2):
root1 = self._find(n1)
root2 = self._find(n2)
if root1 == root2:
return # If they are already in the same component, do nothing
# Merge the components and reduce the count of connected components
self.count -= 1
self.parent[root1] = root2
Approach 3: Disjoint Set Union (Optimized)
class Solution:
def removeStones(self, stones):
uf = self.UnionFind(
20002
) # Initialize UnionFind with a large enough range to handle coordinates
# Union stones that share the same row or column
for x, y in stones:
uf._union_nodes(
x, y + 10001
) # Offset y-coordinates to avoid conflict with x-coordinates
return len(stones) - uf.component_count
# Union-Find data structure for tracking connected components
class UnionFind:
def __init__(self, n):
self.parent = [-1] * n # Initialize all nodes as their own parent
self.component_count = (
0 # Initialize the count of connected components
)
self.unique_nodes = (
set()
) # Initialize the set to track unique nodes
# Find the root of a node with path compression
def _find(self, node):
# If node is not marked, increase the component count
if node not in self.unique_nodes:
self.component_count += 1
self.unique_nodes.add(node)
if self.parent[node] == -1:
return node
self.parent[node] = self._find(self.parent[node])
return self.parent[node]
# Union two nodes, reducing the number of connected components
def _union_nodes(self, node1, node2):
root1 = self._find(node1)
root2 = self._find(node2)
if root1 == root2:
return # If they are already in the same component, do nothing
# Merge the components and reduce the component count
self.parent[root1] = root2
self.component_count -= 1
