947. Most Stones Removed with Same Row or Column #

Problem #

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:

1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

Problem Summary #

On a 2D plane, we place stones at some integer coordinate points. Each coordinate point may have at most one stone. Now, a move operation removes a stone that shares a column or row with another stone on the grid. What is the maximum number of move operations we can perform?

Hint:

1 <= stones.length <= 1000
0 <= stones[i][j] < 10000

Solution Ideas #

Given an array whose elements are a series of coordinate points. Now some coordinate points can be removed, and the removal must satisfy: the point to be removed has another point in the same row or column. Ask how many points can be removed in the end. After removals, there will inevitably be some points that exclusively occupy a row, and these points cannot be removed.
The solution idea for this problem is Union-Find. union() all points that share the same row or column. Points in different sets cannot remove each other. Proof by contradiction: if they can be removed, it means there exists a same-row or same-column situation, so they must be in the same set, which contradicts being in different sets. The points left in the end are the number of sets, and each set will leave only one point. So the number of removed points is the total number of points minus the number of sets: len(stones) - uf.totalCount().
If sets are merged by brute force, the time complexity is also very poor, and there is room for optimization. While traversing all points, we can store the rows and columns that have been traversed. Here we can use a map to record them, where the key is the row number and the value is the index of the previously traversed point. Similarly, columns can also be stored with a map, where the key is the column number and the value is the index of the previously traversed point. After such optimization, the time complexity will improve significantly.

Code #


package leetcode

import (
	"github.com/halfrost/leetcode-go/template"
)

func removeStones(stones [][]int) int {
	if len(stones) <= 1 {
		return 0
	}
	uf, rowMap, colMap := template.UnionFind{}, map[int]int{}, map[int]int{}
	uf.Init(len(stones))
	for i := 0; i < len(stones); i++ {
		if _, ok := rowMap[stones[i][0]]; ok {
			uf.Union(rowMap[stones[i][0]], i)
		} else {
			rowMap[stones[i][0]] = i
		}
		if _, ok := colMap[stones[i][1]]; ok {
			uf.Union(colMap[stones[i][1]], i)
		} else {
			colMap[stones[i][1]] = i
		}
	}
	return len(stones) - uf.TotalCount()
}