Stones Sharing A Line
Problem
Stones sit on distinct points of an integer grid. You may take a stone off the board if at least one other stone still on the board shares its row or its column. Return the largest number of stones you can take off by choosing the order well.
Examples
Input: stones = [[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]
Output: 5
Why: all six stones are linked through shared rows and columns, so one remainsInput: stones = [[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]
Output: 3
Why: the centre stone shares nothing, and the four corners reduce to oneInput: stones = [[0, 0]]
Output: 0
Why: edge case, a lone stone has no partnerHints
0 / 3
Try a small cluster of stones that share lines. However large it is, how many of its stones can you remove, and which one must stay?
Stones that are linked by shared rows or columns, directly or through other stones, form a group. Every group can be reduced to exactly one stone by always removing a stone far from the one you intend to keep, so the answer depends only on the number of groups.
Treat every row and every column as a node, and let each stone join its row node to its column node in a disjoint-set structure. Count the distinct roots among the nodes that were used; the answer is the number of stones minus that count.
Solution
Within a connected group of stones, removing them in reverse order of a traversal from any chosen stone always leaves the removed stone a partner, so each group shrinks to one stone and no further; the answer is the number of stones minus the number of groups. Rather than comparing stones pairwise, each stone merges its row with its column, so two stones end up in the same set exactly when a chain of shared lines links them. Union by size keeps the trees shallow and path halving flattens them further. Time is O(n times the inverse Ackermann function) and space is O(n).
def removable(stones):
parent, size = {}, {}
def find(x):
parent.setdefault(x, x); size.setdefault(x, 1)
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
def union(a, b):
a, b = find(a), find(b)
if a == b: return
if size[a] < size[b]: a, b = b, a # hang the smaller tree under the larger
parent[b] = a; size[a] += size[b]
for r, c in stones:
union(("row", r), ("col", c)) # a stone links its row and its column
groups = len({find(x) for x in parent})
return len(stones) - groups
print(removable([[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]])) # -> 5
print(removable([[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]])) # -> 3
print(removable([[0, 0]])) # -> 0Stuck on the idea rather than the code? Union by Rank or Size covers it.