LeetCode 947. Most Stones Removed with Same Row or Column

[@ryanfu8593]

To anyone wondering why the bfs solution is O(n^2) even with the visited set. The two for loops in the while stack are actually very inefficient. For example in this 1D graph a->b->c, starting from a, b and c will be added to the stack. We'll pop b and we'll still try to add a and c, similarly when we pop c we'll still try to add a and b, though we don't since they have been visited already. The key is trying to add the elements still contributes to the time complexity.

[@ValeryMikheenko]

Thank you!

[@rajatmodi1573]

mr cheng has made a fine use of ~ operator to maintain the separation of (i,j) indexes of a stone. This showed me how my code was lengthy and bad. A naive implementation [which i did] would have to instead unify over rows and cols separately. will try not to make this mistake again.
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
#dfs solution was bad, because for each stone i was looking at all the stones in the row or col, to check which one to add. This leads us to o(n^2)
#the question then becomes: can we come up with the approach to query the neighbors of a stone in a shorter amount of time.
#the idea of union find is that stones in the same row, must be unified, and stones in the same col also. Finally, query the individual components you have
#thus
hash_row = defaultdict(list)
hash_col = defaultdict(list)
parent = {}#to keep track of parents in the union find, the element has to be an individual (x,y) coordinate
for i,stone in enumerate(stones):
x,y= stone[0],stone[1]
hash_row[x].append((x,y))
hash_col[y].append((x,y))
stones[i]= tuple(stone)
parent[tuple(stone)]= tuple(stone)
#find the parent of a stone, via path compression
def find(x,y):
if parent[(x,y)]!=(x,y):
parent[(x,y)]=find(parent[(x,y)][0],parent[(x,y)][1])
return parent[(x,y)]
#union of two points
def union(x_1,y_1,x_2,y_2):
r1= find(x_1,y_1)
r2 = find(x_2,y_2)
if r1!=r2:
parent[r1]=r2
#union along rows
for row in hash_row.keys():
#perform union of elements in the list
row = hash_row[row]
p1 = row[0]
for p2 in row[1:]:
union(p1[0],p1[1],p2[0],p2[1])
#union along cols
for col in hash_col.keys():
#perform union of elements in the list
col = hash_col[col]
p1 = col[0]
for p2 in col[1:]:
union(p1[0],p1[1],p2[0],p2[1])
#contains the coordinate which is the root of each unique cluster
group = set()
for point in parent.keys():
cluster_root = find(point[0],point[1])
group.add(cluster_root)
return len(stones)-len(group)