Leetcode 947. Most Stones Removed with Same Row or Column

Problem Description

In this problem, we are given a 2D grid where the positions of stones are marked as coordinate points stones[i][j]. We are supposed to perform a move which involves removing a stone that shares either a same row or column with any other stone in the grid. The goal is to determine the maximum possible number of moves we can make.

Example:

Consider stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]], the maximum number of moves would be 5. This is because you could carry out removals in the following pattern:

Remove [1,2] -> Remove [1,0] (shares the same row with [1,2]) -> Remove [0,0] (shares the same column with [1,0]) -> Remove [0,1] (shares the same row with [0,0]) -> Remove [2,1] (shares the same column with [0,1]). Thus, the max number of moves possible is 5.

Approach

The idea to solving this problem is to treat it as a graph and apply depth-first search (DFS) on it. The stones sharing a column or a row can be treated as connected nodes. Each stone is a node and the connection is due to having a common row or column. To find all connected components/stones, we use DFS and build a graph for the given nodes.

After we have the stones grouped in their connected components, the idea is simple. The maximum moves we can make is total number of stones minus the number of groups(which we took as islands in the code). This is because in each group, we can remove all stones leaving one behind.

Let's take a look at the solutions in different programming languages.

PYTHON Solution

1
2python
3class Solution:
4    def removeStones(self, stones: List[List[int]]) -> int:
5        # Preprocess the stone positions
6        rows, cols, seen = defaultdict(list), defaultdict(list), set()
7        for x, y in stones:
8            rows[x].append(y)
9            cols[y].append(x)
10            
11        # DFS Function
12        def dfs(node, seen):
13            if node not in seen:
14                seen.add(node)
15                for y in rows[node]:
16                    dfs(y, seen)
17                for x in cols[node]:
18                    dfs(x, seen)
19                return 1
20            return 0
21
22        islands = 0
23        for x, y in stones:
24            islands += dfs(x, seen)
25            islands += dfs(y, seen)
26
27        return len(stones) - islands // 2
28  

The python solution also uses a Depth First Search(D.F.S) approach. We create a default dictionary for both rows and columns with each stone's x-coordinate or y-coordinate as keys linking to its other coordinate. This can help us keep track of all the stones in a particular row or column. Next, we construct a Depth First Search function that navigates through our data and groups it accordingly. Finally, we calculate the maximum possible moves made and return it as the solution.

JAVA Solution

1
2java
3class Solution {
4    public int removeStones(int[][] stones) {
5        int[] fathers = new int[20000];
6        for(int i = 0; i < 20000; i++) {
7            fathers[i] = i;
8        }
9        for(int[] stone : stones) {
10            union(fathers, stone[0], stone[1] + 10000);
11        }
12        Set<Integer> seen = new HashSet<>();
13        for(int[] stone : stones) {
14            seen.add(find(fathers, stone[0]));
15        }
16        return stones.length - seen.size();
17    }
18    public void union(int[] fathers, int x, int y) {
19        fathers[find(fathers,x)] = find(fathers,y);
20    }
21    public int find(int[] fathers, int x) {
22        if(x != fathers[x]){
23            fathers[x] = find(fathers, fathers[x]);
24        }
25        return fathers[x];
26    }
27}

This Java implementation uses a union find data structure. The row and column indices of each stone are encoded into a single index and merged together using the union function. The find method is used to return the ultimate parent (or disjoint set representative) of an index. It utilizes path compression to optimize future lookups. The number of removable stones is calculated by subtracting the number of disjoint sets from the total number of stones.

C++ Solution

1
2
3class Solution {
4public:
5    int removeStones(vector<vector<int>>& stones) {
6        vector<vector<int>> graph(stones.size());
7        unordered_set<int> visited;
8        int islands = 0;
9        for(int i = 0; i < stones.size(); i++) {
10            for(int j = i + 1; j < stones.size(); j++) {
11                if(stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
12                    graph[i].push_back(j);
13                    graph[j].push_back(i);
14                }
15            }
16        }
17        for(int i = 0; i < stones.size(); i++) {
18            if(visited.insert(i).second) {
19                dfs(graph, i, visited);
20                ++islands;
21            }
22        }
23        return stones.size() - islands;
24    }
25    void dfs(const vector<vector<int>>& graph, int u, unordered_set<int>& seen) {
26        for(const int v : graph[u]) {
27            if (seen.insert(v).second) {
28                dfs(graph, v, seen);
29            }
30        }
31    }
32};

The C++ solution is similar to the Python solution where we again perform DFS after building a graph from stones. The number of islands give us the number of separate groups we have formed after DFS. We then subtract the islands from total number of stones, which give us maximum number of stones we can remove.

JavaScript Solution

1
2javascript
3class Solution {
4    removeStones(stones) {
5        let UF = new UnionFind(20000);
6        for (let stone of stones)
7            UF.union(stone[0], stone[1] + 10000);
8        var pointSet = new Set();
9        for (let stone of stones)
10            pointSet.add(UF.find(stone[0]));
11        return stones.length - pointSet.size;
12    }
13
14    class UnionFind {
15        constructor(n) {
16            this.parent = new Int32Array(n);
17            for (let i = 0; i < n; i++)
18                this.parent[i] = i;
19        }
20
21        find(x) {
22            if (this.parent[x] !== x) 
23                this.parent[x] = this.find(this.parent[x]);
24            return this.parent[x];
25        }
26
27        union(x, y) {
28            this.parent[this.find(x)] = this.find(y);
29        }
30    }
31}

In the JavaScript solution, we implement the union find structure for the stones and create separate groups if the stones are in the same row or column. The union function merges two disjoint sets while the find function returns the ultimate parent of a node. The number of stones that can be removed is the total number of stones minus the unique ultimate parents.Different solutions have different time complexities due to various optimizations. Hence, the programmer should always weigh the pros and cons of each approach, considering aspects like space and time complexity, readability, and maintainability of the code.

All the above solutions provide efficient ways to solve the problem using concepts such as Depth-First Search(DFS) and Disjoint Set Union (DSU) or Union-Find. One common theme across these solutions is the grouping of stones into islands or clusters(rightly visualized as graph nodes), and then calculating the maximum number of moves based on the total stones and these groups.

To improve on the given solutions, one could consider employing iterative versions of Depth-First Search as opposed to the recursive versions for cases when the input size is large, and there's the potential risk of a stack overflow.

In conclusion, the understanding and application of graph theory concepts effectively solve this problem. As we have seen, different languages and the utilization of language-specific constructs can lead to varying solutions. Therefore, always strive to engage the most suitable language and constructs that align with the requirements of a problem for the most optimal solution.