Domain 2MediumMEDIUM

Most Stones Removed with Same Row or Column

Uses Union-Find with Hash Maps to group stones into connected components based on shared rows/columns; result is total stones minus number of disjoint groups.

Domain: medium•Updated: 2026-09-04
#Union-Find#Hash Map#O(N)#Graph Connectivity

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 (O(N2)O(N^2)).

Approach

  1. Initialize: Create a Union-Find (Disjoint Set) parent array for n stones and two hash maps (row_map, col_map) to store the index of the last seen stone at each x-coordinate or y-coordinate.
  2. 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), sharing y means same horizontal line/row; sharing x means 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.
  3. Count Components: After processing all stones, count how many indices are their own parent (parent[i] == i). These represent the roots of disjoint components.
  4. Calculate Result: Return n - number_of_roots.

Complexity Analysis

  • Time Complexity: O(N⋅α(N))O(N \cdot \alpha(N)), where α\alpha is the inverse Ackermann function (effectively constant). We iterate through each stone once (NN) and perform nearly constant-time union/find operations. Hash map lookups are average O(1)O(1).
  • Space Complexity: O(N)O(N) 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 10410^4).

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_components becomes 1. Returns n−1=0n - 1 = 0. 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 (N−2N - 2).
  • Coordinate Sparsity: Using Hash Maps (row_map, col_map) handles coordinates up to 10410^4 without allocating a massive grid array, keeping space complexity proportional to NN.
  • 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.