947. Most Stones Removed with Same Row or Column

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone.

Now, a move consists of removing a stone that shares a column or row with another stone on the grid.

What is the largest possible number of moves we can make?

Example 1:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5

Example 2:

Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3

Example 3:

Input: stones = [[0,0]]
Output: 0

Note:

---

	class Solution {
	public int removeStones(int[][] stones) {
	Map<Integer, List<Integer>> graph1 = new HashMap<Integer, List<Integer>>();
	Map<Integer, List<Integer>> graph2 = new HashMap<Integer, List<Integer>>();

	for (int[] stone: stones) {
	int u = stone[0];
	int v = stone[1];
	graph1.putIfAbsent(u, new ArrayList<Integer>());
	graph1.get(u).add(v);

	graph2.putIfAbsent(v, new ArrayList<Integer>());
	graph2.get(v).add(u);
	}

	int count = 0;
	Set<Integer> visited1 = new HashSet<Integer>();
	Set<Integer> visited2 = new HashSet<Integer>();

	for (int[] stone: stones) {
	int row = stone[0];
	int col = stone[1];

	if (!visited1.contains(row) && !visited2.contains(col)) {
	visited1.add(row);
	visited2.add(col);
	dfs(row, col, graph1, graph2, visited1, visited2);
	count++;
	}
	}

	return stones.length - count;
	}

	private void dfs(int row, int col, Map<Integer, List<Integer>> graph1, Map<Integer, List<Integer>> graph2, Set<Integer> visited1, Set<Integer> visited2) {

	for (int c: graph1.get(row)) {
	if (!visited2.contains(c)) {
	visited2.add(c);
	dfs(row, c, graph1, graph2, visited1, visited2);
	}
	}

	for (int r: graph2.get(col)) {
	if (!visited1.contains(r)) {
	visited1.add(r);
	dfs(r, col, graph1, graph2, visited1, visited2);
	}
	}
	}
	}

SWE Interview preparation