# Most Stones Removed with Same Row or Column
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/most-stones-removed-with-same-row-or-column)
Canonical: https://scaleengineer.com/dsa/problems/most-stones-removed-with-same-row-or-column
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Hash Table, Graph
**Companies:** [Tekion](https://scaleengineer.com/companies/tekion), [PhonePe](https://scaleengineer.com/companies/phonepe), [thoughtspot](https://scaleengineer.com/companies/thoughtspot)
---
## Problem
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.

# Approaches
## Brute-Force Graph Traversal (DFS)
This approach models the problem as a graph problem. Each stone is a vertex, and an edge exists between two stones if they share the same row or column. The problem then becomes finding the number of connected components in this graph. For each component of size `k`, we can remove `k-1` stones. Thus, the total number of removable stones is `N - C`, where `N` is the total number of stones and `C` is the number of connected components. We can build an explicit adjacency list for the graph and then use Depth-First Search (DFS) to count the components.
**Time:** `O(N^2)`. Building the adjacency list requires checking `N*(N-1)/2` pairs, which is `O(N^2)`. The DFS traversal takes `O(V+E) = O(N+E)`. In the worst case, the number of edges `E` can be `O(N^2)`, making the total time complexity dominated by `O(N^2)`. · **Space:** `O(N^2)`. The adjacency list can store up to `O(N^2)` edges in a dense graph. The `visited` array and recursion stack for DFS take `O(N)` space.
**Pros:** Conceptually straightforward, directly translating the problem into a standard graph traversal problem.
**Cons:** High time complexity of `O(N^2)` due to building the graph by checking all pairs.; High space complexity of `O(N^2)` in the worst case for the adjacency list if the graph is dense.
### Explanation
### Graph Construction
We first build an adjacency list representation of the graph. We iterate through every pair of stones. If two stones `stones[i]` and `stones[j]` have the same x-coordinate or the same y-coordinate, we add an edge between vertex `i` and vertex `j`. This takes `O(N^2)` time.

### Counting Components with DFS
We use a `visited` array to keep track of visited stones (vertices). We iterate through all stones from `0` to `N-1`. If a stone `i` has not been visited, it means we've found a new connected component. We increment our component counter and start a DFS traversal from stone `i`. The DFS function will recursively visit all neighbors of the current stone, marking them as visited. This ensures that all stones in the same component are visited together.

### Final Calculation
After iterating through all stones, the component counter will hold the total number of connected components, `C`. The maximum number of stones that can be removed is `N - C`.

```java
import java.util.*;

class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        // Build adjacency list - O(N^2)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    adj.get(i).add(j);
                    adj.get(j).add(i);
                }
            }
        }

        boolean[] visited = new boolean[n];
        int components = 0;
        // Count connected components using DFS - O(N+E) which is O(N^2)
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, adj, visited);
                components++;
            }
        }

        return n - components;
    }

    private void dfs(int u, List<List<Integer>> adj, boolean[] visited) {
        visited[u] = true;
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                dfs(v, adj, visited);
            }
        }
    }
}
```
### Algorithm
- Create an adjacency list `adj` for `n` stones.
- Iterate through all pairs of stones `(i, j)`.
- If `stones[i]` and `stones[j]` share a row or column, add an edge between `i` and `j` in `adj`.
- Initialize a `visited` array of size `n` to `false`.
- Initialize `components = 0`.
- Iterate from `i = 0` to `n-1`:
    - If `visited[i]` is `false`:
        - Increment `components`.
        - Call a DFS function starting from `i` to mark all nodes in the component as visited.
- Return `n - components`.

## Union-Find on Stone Indices
This approach also identifies connected components but uses a more space-efficient data structure, the Disjoint Set Union (DSU) or Union-Find. Each stone is an element in a set. We iterate through all pairs of stones and if they are connected (share a row or column), we `union` their sets. The number of connected components is the final number of disjoint sets. The result is `N - (number of components)`.
**Time:** `O(N^2 * α(N))`, which is effectively `O(N^2)`. The dominant factor is the nested loop iterating through all pairs of stones. The `union` and `find` operations are nearly constant time, `O(α(N))`, where `α` is the inverse Ackermann function. · **Space:** `O(N)`. We need an array of size `N` for the DSU's parent pointers.
**Pros:** More space-efficient than the explicit graph approach, using only `O(N)` space.; The DSU data structure is highly optimized for component-finding problems.
**Cons:** The time complexity is still `O(N^2)` because of the nested loops to check every pair of stones for connectivity.
### Explanation
### DSU Data Structure
We implement a DSU data structure with two main operations: `find` (to find the representative/root of the set an element belongs to) and `union` (to merge two sets). Path compression and union by size/rank optimizations are used to make these operations nearly constant time.

### Algorithm
Initialize a DSU structure for `N` stones. Each stone `i` is its own parent, so we start with `N` components. Iterate through all pairs of stones `(i, j)`. If `stones[i]` and `stones[j]` share a row or column, we check if they are already in the same set using `find(i) != find(j)`. If they are in different sets, we merge them using `union(i, j)` and decrement the component count.

### Final Calculation
The final count of components is used to calculate the result: `N - components`.

```java
class Solution {
    class DSU {
        int[] parent;
        int components;

        DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            components = n;
        }

        int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]); // Path compression
        }

        void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
                components--;
            }
        }
    }

    public int removeStones(int[][] stones) {
        int n = stones.length;
        DSU dsu = new DSU(n);

        // O(N^2) loop to connect stones
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    dsu.union(i, j);
                }
            }
        }

        return n - dsu.components;
    }
}
```
### Algorithm
- Initialize a DSU structure for `n` elements, with each element in its own set. The number of components is `n`.
- Iterate through all pairs of stones `(i, j)`.
- If `stones[i]` and `stones[j]` share a row or column, perform `union(i, j)`. The `union` operation will merge the sets if they are different and decrement the component count.
- Return `n - (final component count)`.

## Optimized Union-Find with Coordinate Mapping
This is the most efficient approach. It avoids the `O(N^2)` pairwise comparison by using hash maps to quickly find stones that share a row or column. We iterate through the stones just once. For each stone, we check if we've already seen a stone in the same row or column. If so, we union the current stone with the previously seen stone. This reduces the time complexity to be nearly linear.
**Time:** `O(N * α(N))`. We iterate through `N` stones once. Inside the loop, hash map operations are `O(1)` on average, and DSU operations are `O(α(N))`. · **Space:** `O(N)`. The DSU structure requires `O(N)` space. The hash maps, in the worst case, can store up to `N` distinct rows and `N` distinct columns, leading to `O(N)` space.
**Pros:** Highly efficient time complexity, close to linear.; Optimal space complexity, depending only on the number of stones `N`.
**Cons:** Slightly more complex to conceptualize than the direct graph-building approaches.
### Explanation
### Core Idea
Instead of comparing every stone with every other stone, we can process stones one by one and connect them to a "representative" for their row and column. If we encounter a stone at `(r, c)`, and we've already seen another stone in row `r`, we know these two stones are connected and should be in the same component. The same logic applies to column `c`.

### Algorithm
Initialize a DSU structure for `N` stones. Create two hash maps: `rowMap` to map a row index to the index of a stone in that row, and `colMap` to map a column index to the index of a stone in that column. Iterate through each stone `i` from `0` to `N-1` with coordinates `(r, c)`. For the current stone's row `r`: if `rowMap` does not contain `r`, map `r` to the current stone's index `i`. If `rowMap` already contains `r`, it means we've seen a stone in this row before. We union the current stone `i` with the stone previously stored for this row, `union(i, rowMap.get(r))`. Do the same for the current stone's column `c` using `colMap`.

### Final Calculation
After iterating through all stones, the number of components is tracked by the DSU structure. The result is `N - (number of components)`.

```java
import java.util.*;

class Solution {
    class DSU {
        int[] parent;
        int components;

        DSU(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            components = n;
        }

        int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]);
        }

        void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                parent[rootI] = rootJ;
                components--;
            }
        }
    }

    public int removeStones(int[][] stones) {
        int n = stones.length;
        DSU dsu = new DSU(n);
        Map<Integer, Integer> rowMap = new HashMap<>();
        Map<Integer, Integer> colMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int r = stones[i][0];
            int c = stones[i][1];

            if (rowMap.containsKey(r)) {
                dsu.union(i, rowMap.get(r));
            } else {
                rowMap.put(r, i);
            }

            if (colMap.containsKey(c)) {
                dsu.union(i, colMap.get(c));
            } else {
                colMap.put(c, i);
            }
        }

        return n - dsu.components;
    }
}
```
### Algorithm
- Initialize a DSU structure for `n` stones.
- Initialize two hash maps, `rowMap` and `colMap`.
- Iterate through the stones from `i = 0` to `n-1`:
    - Let the stone's coordinates be `(r, c)`.
    - If `r` is in `rowMap`, `union(i, rowMap.get(r))`. Otherwise, `rowMap.put(r, i)`.
    - If `c` is in `colMap`, `union(i, colMap.get(c))`. Otherwise, `colMap.put(c, i)`.
- Return `n - (final component count)`.

# Solutions
### Java

```java
class Solution {
private
  int[] p;
public
  int removeStones(int[][] stones) {
    int n = 10010;
    p = new int[n << 1];
    for (int i = 0; i < p.length; ++i) {
      p[i] = i;
    }
    for (int[] stone : stones) {
      p[find(stone[0])] = find(stone[1] + n);
    }
    Set<Integer> s = new HashSet<>();
    for (int[] stone : stones) {
      s.add(find(stone[0]));
    }
    return stones.length - s.size();
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  int removeStones(vector<vector<int>> &stones) {
    int n = 10010;
    p.resize(n << 1);
    for (int i = 0; i < p.size(); ++i)
      p[i] = i;
    for (auto &stone : stones)
      p[find(stone[0])] = find(stone[1] + n);
    unordered_set<int> s;
    for (auto &stone : stones)
      s.insert(find(stone[0]));
    return stones.size() - s.size();
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    def removeStones(self, stones: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] n = 10010 p = list(range(n << 1)) for x, y in stones: p[find(x)] = find(y + n) s = {find(x) for x, _ in stones} return len(stones) - len(s)

```