Problem Statement

You have a 2D grid where you place n stones at specific integer coordinates, and each coordinate can have at most 1 stone.

A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.

Given an array stones of length n, where stones[i] = [x_i, yi_i] is the location of the i^th stone, return the maximum number of stones that can be removed.

Examples

Example 1:

• Input: stones = [[1, 1], [2, 2], [3, 1], [3, 2], [4, 4]]
• Expected Output: 3
• Justification: You can remove stones from [1, 1], [3, 1], and [3, 2] positions.

Example 2:

• Input: stones = [[0, 0], [0, 1], [1, 0], [1, 1], [2, 2]]
• Expected Output: 3
• Justification: You can remove stones from [0, 0], [0, 1], and [1, 0] positions.

Example 3:

• Input: stones = [[0, 1], [3, 4], [4, 3], [4, 4], [5, 5]]
• Expected Output: 2
• Justification: You can remove stones from [4, 4], and [3, 4] positions.

Constraints:

• 1 <= stones.length <= 1000
• 0 <= x_i, y_i <= 10⁴
• No two stones are at the same coordinate point.

Solution

To solve this problem, we can use the Union-Find algorithm, also known as Disjoint Set Union (DSU). The Union-Find algorithm helps us manage and merge sets efficiently. We treat each row and column as nodes and use the stones to connect these nodes. By merging sets where stones share rows or columns, we can determine the number of connected components. The size of the largest connected component gives us the maximum number of stones that can be removed.

This approach works efficiently because it optimizes both the union and find operations, making it suitable for large inputs.

Step-by-Step Algorithm

1. Initialization:

   • Define a constant K = 10001 to differentiate between row and column nodes.
   • Initialize two arrays, parent and size, each with size 2 * K + 1.
   • Set parent[i] = i and size[i] = 1 for all i in the range 2 * K + 1.

2. Union-Find Setup:

   • Define a helper function find(parent, x) to find the root representative of node x:
     • If x is its own parent, return x.
     • Otherwise, recursively find the parent of x and perform path compression by setting parent[x] to the root representative.
   • Define a helper function union(parent, size, x, y) to unite the sets containing x and y:
     • Find the root representatives of x and y.
     • If they are already in the same set, return 0.
     • Otherwise, unite the sets by size and update the parent and size arrays accordingly. Return 1 if a union operation was performed.

3. Component Counting:

   • Initialize a variable components = 0.
   • Use a hashmap seen to keep track of unique rows and columns encountered:
     • For each stone [xi, yi] in stones:
       • If xi is not in seen, increment components and add xi to seen.
       • If yi + K is not in seen, increment components and add yi + K to seen.

4. Union Operations:

   • For each stone [xi, yi] in stones:
     • Perform union operation between xi and yi + K.
     • If a union operation was successful, decrement components.

5. Result Calculation:

   • The maximum number of stones that can be removed is len(stones) - components.

Algorithm Walkthrough

Let's walk through the algorithm with the example stones = [[1, 1], [2, 2], [3, 1], [3, 2], [4, 4]].

1. Initialization:

   • Define K = 10001.
   • Initialize parent and size arrays:
     • parent = [0, 1, 2, ..., 20002]
     • size = [1, 1, 1, ..., 1]

2. Union-Find Setup:

   • Define the find and union helper functions.

3. Component Counting:

   • Initialize components = 0.
   • Initialize an empty hashmap seen.
   • Process each stone:
     • For stone [1, 1]:
       • 1 is not in seen -> components = 1, seen[1] = 1
       • 1 + K = 10002 is not in seen -> components = 2, seen[10002] = 1
     • For stone [2, 2]:
       • 2 is not in seen -> components = 3, seen[2] = 1
       • 2 + K = 10003 is not in seen -> components = 4, seen[10003] = 1
     • For stone [3, 1]:
       • 3 is not in seen -> components = 5, seen[3] = 1
       • 1 + K = 10002 is already in seen
     • For stone [3, 2]:
       • 3 is already in seen
       • 2 + K = 10003 is already in seen
     • For stone [4, 4]:
       • 4 is not in seen -> components = 6, seen[4] = 1
       • 4 + K = 10005 is not in seen -> components = 7, seen[10005] = 1

4. Union Operations:

   • For stone [1, 1]:
     • Perform union(1, 10002) -> parent[1] = 1, parent[10002] = 1, size[1] = 2
     • Union successful -> components = 6
   • For stone [2, 2]:
     • Perform union(2, 10003) -> parent[2] = 2, parent[10003] = 2, size[2] = 2
     • Union successful -> components = 5
   • For stone [3, 1]:
     • Perform union(3, 10002) -> parent[3] = 3, parent[1] = 3, size[3] = 3
     • Union successful -> components = 4
   • For stone [3, 2]:
     • Perform union(3, 10003) -> parent[3] = 3, parent[2] = 3, size[3] = 5
     • Union successful -> components = 3
   • For stone [4, 4]:
     • Perform union(4, 10005) -> parent[4] = 4, parent[10005] = 4, size[4] = 2
     • Union successful -> components = 2

5. Result Calculation:

   • The maximum number of stones that can be removed is len(stones) - components = 5 - 2 = 3.

Code