Problem Breakdown
We are given a list of stone coordinates. A stone can be removed if it shares a row or column with another active stone. The goal is to maximize removals. This implies that within any connected group of stones (where connectivity is defined by sharing an x-coordinate OR y-coordinate), we can remove all but one stone per group.
Intuition
The problem models the 2D plane as a graph where each stone is a node and edges exist between nodes sharing coordinates. The maximum number of removable stones corresponds to removing every node in a connected component except for one “root” or survivor. Therefore, Max Removed = Total Stones - Number of Connected Components. We can efficiently find these components using the Union-Find data structure combined with Hash Maps to track coordinate associations without iterating over all pairs ().
Approach
- Initialize: Create a Union-Find (Disjoint Set) parent array for
nstones and two hash maps (row_map,col_map) to store the index of the last seen stone at each x-coordinate or y-coordinate. - Iterate & Connect: For each stone
[x, y]:- If a previous stone exists in this row (same
y), union them. Note: In coordinate geometry(x,y), sharingymeans same horizontal line/row; sharingxmeans vertical/column. The maps track these dimensions regardless of semantic naming. - Update the hash map to store the current stone’s index at that coordinate. This ensures future stones on this line connect to the existing component via Union-Find path compression logic, effectively merging all connected lines into a single set.
- If a previous stone exists in this row (same
- Count Components: After processing all stones, count how many indices are their own parent (
parent[i] == i). These represent the roots of disjoint components. - Calculate Result: Return
n - number_of_roots.
Complexity Analysis
- Time Complexity: , where is the inverse Ackermann function (effectively constant). We iterate through each stone once () and perform nearly constant-time union/find operations. Hash map lookups are average .
- Space Complexity: for the Union-Find parent array, row map, and column map. This is efficient as it avoids allocating a grid based on coordinate values (which could be up to ).
Solution
class Solution:
def removeStones(self, stones):
n = len(stones)
# Initialize Union Find structure where parent[i] points to itself initially.
# Each index represents a stone in the input list.
parent = list(range(n))
def find(i):
if parent[i] != i:
parent[i] = find(parent[i]) # Path compression for efficiency
return parent[i]
def union(i, j):
root_i = find(i)
root_j = find(j)
if root_i != root_j:
parent[root_i] = root_j
row_map = {}
col_map = {}
for i, (x, y) in enumerate(stones):
# If we've seen this column coordinate before, union current stone with the previous one on that line.
if x in col_map:
union(i, col_map[x])
# Same logic for rows (y-coordinate).
if y in row_map:
union(i, row_map[y])
# Update maps to point to current index.
# Since Union-Find merges sets, storing any valid representative works.
col_map[x] = i
row_map[y] = i
# Count number of connected components by counting unique roots in the UF structure.
num_components = 0
for i in range(n):
if parent[i] == i:
num_components += 1
return n - num_components
Edge Cases Handled
- Single Stone: The loop runs once,
num_componentsbecomes 1. Returns . Correct as no removals are possible with one stone. - Disconnected Stones: If stones share no rows/cols (e.g.,
[0,0], [2,3]), they remain separate roots in the Union-Find structure. The formula correctly subtracts both components from total N (). - Coordinate Sparsity: Using Hash Maps (
row_map,col_map) handles coordinates up to without allocating a massive grid array, keeping space complexity proportional to . - Multiple Stones on Same Line: The map stores the latest index; Union-Find ensures all stones sharing that line are merged into one component regardless of which specific stone is stored in the map.