947. Most Stones Removed with Same Row or Column
Problem Solving - Day 44
Hello, reader 👋🏽 ! Welcome to day 44 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.
Today, I will be picking up LeetCode's daily challenge problem: 947. Most Stones Removed with Same Row or Column.
🤔 Problem Statement
- On a 2D plane, there are 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.E.g.:
stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]=>5stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]=>3stones = [[0,0]]=>0
💬 Initial Thought Process
- I'm kind of embarrassed to admit that I did not think this as a graph problem. There were multiple hints in the question that this was a graph problem:
- share same column/ row
- No two stones are at the same coordinate point -> hinting that there cannot be loops
After going through some vague solution where I list down coordinates that share same x and y points, I looked at the related topics since I got stuck. Then I saw that it had
Union Find,DFSandGraphs.All in all, I can conclude that this was not a medium problem (at least for me). In an interview unless the interviewer gives a hint, I wouldn't be able to look at it as a graph problem.
💬 Thought Process - DFS
- The approach is similar to finding 200. Number of Islands.
- But the only difference from that question is the definition of connected components. In that problem. And example of connected component: nodes
(i+1,j), (i-1,j), (i, j+1), (i, j-1)are connected to(i, j). - In this problem, connected components means nodes that share the same row or column.
- In other graph problems, we know the neighbours before hand, but in this problem, at every dfs call, we would traverse all the stones and figure out the connected nodes.
- Once we traverse through all the nodes via dfs call, we will have the total number of islands -> every dfs call represents one island.
- From intuition, since all the components are connected in an island, we will have to remove all the nodes except one in the island.
- For e.g. if there are n nodes and two islands, we will only have 2 nodes remaining and will remove
(n-2)nodes.
👩🏽💻 Solution - DFS
Below is the code for the DFS approach.
class Solution { public int removeStones(int[][] stones) { if(stones == null || stones.length == 0) return 0; int n = stones.length; Set<int[]> visited = new HashSet(); int islands = 0; for(int i = 0; i<n; i++) { int[] stone = stones[i]; if(!visited.contains(stone)) { islands++; dfs(i, stones, visited); } } return n - islands; } private void dfs(int row, int[][] stones, Set<int[]> visited) { int[] stone = stones[row]; int n = stones.length; visited.add(stone); for(int i = 0; i<n; i++) { int[] s = stones[i]; if(!visited.contains(s)) { if(stone[0] == s[0] || stone[1] == s[1]) { dfs(i, stones, visited); } } } } }Time Complexity: O(n^2) - n = number of nodes - For every node, we will be traversing every other node. Space Complexity: O(n) - n = number of nodes - Auxiliary space for the visited set
💬 Thought Process - DSU
- Another approach to solving this is disjoint union set. But here the union is formed not among the coordinates of the same stone, rather it is formed between two stones.
- But the catch each stone is an array. So how do we store parents of every stone?
- To tackle this, we will form union by indices. Rather than forming union between coordinates, we will form the union based on the index of the coordinates that are connected.
- For e.g.
[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]], for stones[0,0]and[0,1], we will form union of 0 and 1 since the stones are present in indices 0 and 1 respectively. - So we will traverse through every pair of stones and form a union if they are connected, i.e., they share either row or column.
- Also to optimise union find, we'll be using path compression and union by rank to bring down the time complexities of find and union to amortised O(1).
- To calculate connected components, we'll keep track of the number of components in the DSU class.
- Initially there will be n components. As we keep making unions, the components would reduce by 1.
- By the same intuition in the last solution, the number of removals would be
total number of nodes - number of connected components.
👩🏽💻 Solution - DSU
- Below is the code for the DSU approach.
class UnionFind {
int[] parent, rank;
int n;
int connectedComponents;
UnionFind(int n) {
this.n = n;
parent = new int[n];
rank = new int[n];
connectedComponents = n;
for(int i = 0; i<n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
private int find(int x) {
if(x == parent[x]) return x;
return parent[x] = find(parent[x]);
}
public void union(int x, int y) {
int parX = find(x);
int parY = find(y);
if(parX == parY) {
return;
}
if(rank[parX] < rank[parY]) {
parent[parX] = parent[parY];
rank[parY]++;
}
else {
parent[parY] = parent[parX];
rank[parX]++;
}
connectedComponents--;
}
public int getNumConnectedComponents() {
return connectedComponents;
}
}
class Solution {
public int removeStones(int[][] stones) {
if(stones == null || stones.length == 0) return 0;
int n = stones.length;
UnionFind uf = new UnionFind(n);
for(int i = 0; i<n; i++) {
int[] s1 = stones[i];
for(int j = i+1; j<n; j++) {
int[] s2 = stones[j];
if(s1[0] == s2[0] || s1[1] == s2[1]) {
uf.union(i,j);
}
}
}
return n - uf.getNumConnectedComponents();
}
}
Time Complexity: O(n^2)
- n = number of nodes
- For every node, we will be traversing every other node.
Space Complexity: O(n)
- n = number of nodes
- Auxiliary space for holding rank, parent nodes
💬 Thought Process - DSU Optimised
- The issue in the above approach is that even though we have avoided the recursion space that's needed for DFS solution, we are still forming pairs of stones.
- Another smart way of doing this is to map stone indices to the row and column they belong to.
For e.g.:
[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]], the mapping for this is as follows:// common x 0 -> [0, 1] 1 -> [2, 3] 2 -> [4, 5] // common y 0 -> [0, 2] 1 -> [1, 4] 2 -> [3, 5]What do these mappings mean?
0 -> {0, 1}means that the stones at indices 0 and 1 share the same x coordinate0 -> {0, 2}means that the stones at indices 0 and 2 share the same y coordinate
Now we will use the above two mappings to form unions. We'll traverse the key sets and form mapping of the first index and every other index
E.g.:
0 -> [0, 1]=>union(0,1)1 -> [1, 4]=>union(1,4)
This brings down the overall time complexity to
O(n)and this is the best we can do!- Let's look at the code now.
👩🏽💻 Solution - DSU Optimised
Below is the code for the DSU optimised approach. ``` class UnionFind { int[] parent, rank; int n; int connectedComponents;
UnionFind(int n) {
this.n = n; parent = new int[n]; rank = new int[n]; connectedComponents = n; for(int i = 0; i<n; i++) { parent[i] = i; rank[i] = 0; }}
private int find(int x) {
if(x == parent[x]) return x; return parent[x] = find(parent[x]);}
public void union(int x, int y) {
int parX = find(x); int parY = find(y); if(parX == parY) { return; } if(rank[parX] < rank[parY]) { parent[parX] = parent[parY]; rank[parY]++; } else { parent[parY] = parent[parX]; rank[parX]++; } connectedComponents--;}
public int getNumConnectedComponents() {
return connectedComponents;} }
class Solution { public int removeStones(int[][] stones) { if(stones == null || stones.length == 0) return 0;
int n = stones.length;
UnionFind uf = new UnionFind(n);
Map<Integer, List<Integer>> rows = new HashMap(), cols = new HashMap();
for(int i = 0; i<n; i++) {
int[] stone = stones[i];
int row = stone[0], col = stone[1];
if(!rows.containsKey(col)) {
rows.put(col, new ArrayList());
}
rows.get(col).add(i);
if(!cols.containsKey(row)) {
cols.put(row, new ArrayList());
}
cols.get(row).add(i);
}
for(int col: rows.keySet()) {
List<Integer> list = rows.get(col);
int parentIndex = list.get(0);
for(int i = 1; i<list.size(); i++) {
int childIndex = list.get(i);
uf.union(parentIndex, childIndex);
}
}
for(int row: cols.keySet()) {
List<Integer> list = cols.get(row);
int parentIndex = list.get(0);
for(int i = 1; i<list.size(); i++) {
int childIndex = list.get(i);
uf.union(parentIndex, childIndex);
}
}
return n - uf.getNumConnectedComponents();
}
}
Time Complexity: O(n)
- n = number of nodes
Space Complexity: O(n)
- n = number of nodes
- Auxiliary space for holding rank, parent nodes
```
You can find the link to the GitHub repo for this question here: 947. Most Stones Removed with Same Row or Column.
Conclusion
That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!
Thank you for reading!