{x}
blog image

Most Stones Removed with Same Row or Column

On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one 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] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.

 

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation: One way to remove 5 stones is as follows:
1. Remove stone [2,2] because it shares the same row as [2,1].
2. Remove stone [2,1] because it shares the same column as [0,1].
3. Remove stone [1,2] because it shares the same row as [1,0].
4. Remove stone [1,0] because it shares the same column as [0,0].
5. Remove stone [0,1] because it shares the same row as [0,0].
Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Explanation: One way to make 3 moves is as follows:
1. Remove stone [2,2] because it shares the same row as [2,0].
2. Remove stone [2,0] because it shares the same column as [0,0].
3. Remove stone [0,2] because it shares the same row as [0,0].
Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.

Example 3:

Input: stones = [[0,0]]
Output: 0
Explanation: [0,0] is the only stone on the plane, so you cannot remove it.

 

Constraints:

  • 1 <= stones.length <= 1000
  • 0 <= xi, yi <= 104
  • No two stones are at the same coordinate point.

Solution Explanation for 947. Most Stones Removed with Same Row or Column

This problem asks to find the maximum number of stones that can be removed from a 2D plane, given that a stone can be removed if it shares the same row or column with another stone that hasn't been removed yet. The optimal solution leverages the Union-Find data structure for efficient connected component analysis within a graph implicitly represented by the stone coordinates.

Approach 1: Union-Find

  1. Union-Find Data Structure: A Union-Find data structure is crucial for efficiently tracking connected components. Each stone initially represents its own component. We'll use it to merge components when stones share a row or column.

  2. Iterating through Stone Pairs: The algorithm iterates through all pairs of stones. For each pair:

    • If they share the same row or column, we use the union operation of the Union-Find to merge the components representing those stones.

  3. Counting Remaining Components: After processing all pairs, the number of disjoint sets (components) in the Union-Find structure represents the number of stones that cannot be removed (because they are isolated).

  4. Calculating Removed Stones: The maximum number of stones removed is the total number of stones minus the number of remaining components.

Time Complexity: O(N^2 * α(N)), where N is the number of stones and α(N) is the inverse Ackermann function, which is very slow growing and practically constant for all realistic input sizes. The nested loop iterates through all pairs of stones, dominating the complexity. Union-find operations have amortized constant time complexity due to path compression and union by rank optimizations.

Space Complexity: O(N) to store the Union-Find data structure.

Approach 2: Optimized Union-Find

This approach refines the Union-Find method by using a clever trick to reduce the number of elements in the Union-Find data structure.

  1. Coordinate Mapping: We use the x-coordinate of a stone directly as one index and map the y-coordinate to a different index range (e.g., adding a large offset, like 10001, to the y-coordinate). This allows us to treat rows and columns as nodes in the same Union-Find structure.

  2. Union by Row and Column: When processing a stone (x, y), we perform a union operation between x and (y + offset). This cleverly links stones sharing a row or a column.

  3. Counting Remaining Components (Simplified): We count the number of unique root nodes found among the x-coordinates of all stones. This directly gives the number of remaining components (unremovable stones).

Time Complexity: O(N * α(M)), where N is the number of stones, and M is the maximum coordinate value (which is a constant in this problem, 10001). This is significantly faster than the first approach because it avoids the nested loop.

Space Complexity: O(M) to store the Union-Find data structure.

Approach 3: Depth-First Search (DFS)

This approach is less efficient than Union-Find but provides an alternative way to solve the problem.

  1. Build Adjacency Graph: We construct an adjacency graph where nodes represent stones and edges connect stones that share a row or column.

  2. DFS to Find Connected Components: We perform DFS starting from each unvisited node to identify connected components. Each DFS traversal visits all stones within a connected component.

  3. Calculate Removed Stones: The number of removed stones is the total number of stones minus the number of connected components found.

Time Complexity: O(N^2) due to the construction of the adjacency graph, where N is the number of stones.

Space Complexity: O(N) to store the graph and the visited set.

Code Examples (Python, Java, C++, Go, TypeScript): The provided code snippets demonstrate the implementation of the Union-Find approaches (both the basic and optimized versions). A TypeScript example of the less efficient DFS solution is also included. Note that the Java and C++ code also efficiently uses a HashSet to count unique root nodes. The optimized Union-Find solution is generally preferred because of its better time complexity.