Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
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 <= 10000 <= xi, yi <= 104Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map · Union-Find
[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
[[0,0],[0,2],[1,1],[2,0],[2,2]]
[[0,0]]
minimum-moves-to-get-a-peaceful-board)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #947: Most Stones Removed with Same Row or Column
class UnionFind {
private final int[] p;
private final int[] size;
public UnionFind(int n) {
p = new int[n];
size = new int[n];
for (int i = 0; i < n; ++i) {
p[i] = i;
size[i] = 1;
}
}
public int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
public boolean union(int a, int b) {
int pa = find(a), pb = find(b);
if (pa == pb) {
return false;
}
if (size[pa] > size[pb]) {
p[pb] = pa;
size[pa] += size[pb];
} else {
p[pa] = pb;
size[pb] += size[pa];
}
return true;
}
}
class Solution {
public int removeStones(int[][] stones) {
int n = stones.length;
UnionFind uf = new UnionFind(n);
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
ans += uf.union(i, j) ? 1 : 0;
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #947: Most Stones Removed with Same Row or Column
type unionFind struct {
p, size []int
}
func newUnionFind(n int) *unionFind {
p := make([]int, n)
size := make([]int, n)
for i := range p {
p[i] = i
size[i] = 1
}
return &unionFind{p, size}
}
func (uf *unionFind) find(x int) int {
if uf.p[x] != x {
uf.p[x] = uf.find(uf.p[x])
}
return uf.p[x]
}
func (uf *unionFind) union(a, b int) bool {
pa, pb := uf.find(a), uf.find(b)
if pa == pb {
return false
}
if uf.size[pa] > uf.size[pb] {
uf.p[pb] = pa
uf.size[pa] += uf.size[pb]
} else {
uf.p[pa] = pb
uf.size[pb] += uf.size[pa]
}
return true
}
func removeStones(stones [][]int) (ans int) {
n := len(stones)
uf := newUnionFind(n)
for i, s1 := range stones {
for j, s2 := range stones[:i] {
if s1[0] == s2[0] || s1[1] == s2[1] {
if uf.union(i, j) {
ans++
}
}
}
}
return
}
# Accepted solution for LeetCode #947: Most Stones Removed with Same Row or Column
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
uf = UnionFind(len(stones))
ans = 0
for i, (x1, y1) in enumerate(stones):
for j, (x2, y2) in enumerate(stones[:i]):
if x1 == x2 or y1 == y2:
ans += uf.union(i, j)
return ans
// Accepted solution for LeetCode #947: Most Stones Removed with Same Row or Column
struct Solution;
use std::collections::HashMap;
impl Solution {
fn remove_stones(stones: Vec<Vec<i32>>) -> i32 {
let n = stones.len();
let mut row: HashMap<i32, Vec<usize>> = HashMap::new();
let mut col: HashMap<i32, Vec<usize>> = HashMap::new();
for i in 0..n {
let r = stones[i][0];
let c = stones[i][1];
row.entry(r).or_default().push(i);
col.entry(c).or_default().push(i);
}
let mut visited: Vec<bool> = vec![false; n];
let mut island = 0;
for i in 0..n {
if !visited[i] {
visited[i] = true;
Self::dfs(i, &mut visited, &stones, &row, &col);
island += 1;
}
}
(n - island) as i32
}
fn dfs(
u: usize,
visited: &mut [bool],
stones: &[Vec<i32>],
row: &HashMap<i32, Vec<usize>>,
col: &HashMap<i32, Vec<usize>>,
) {
let r = stones[u][0];
let c = stones[u][1];
for &v in &row[&r] {
if !visited[v] {
visited[v] = true;
Self::dfs(v, visited, stones, row, col);
}
}
for &v in &col[&c] {
if !visited[v] {
visited[v] = true;
Self::dfs(v, visited, stones, row, col);
}
}
}
}
#[test]
fn test() {
let stones = vec_vec_i32![[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]];
let res = 5;
assert_eq!(Solution::remove_stones(stones), res);
let stones = vec_vec_i32![[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]];
let res = 3;
assert_eq!(Solution::remove_stones(stones), res);
let stones = vec_vec_i32![[0, 0]];
let res = 0;
assert_eq!(Solution::remove_stones(stones), res);
}
// Accepted solution for LeetCode #947: Most Stones Removed with Same Row or Column
class UnionFind {
p: number[];
size: number[];
constructor(n: number) {
this.p = Array.from({ length: n }, (_, i) => i);
this.size = Array(n).fill(1);
}
find(x: number): number {
if (this.p[x] !== x) {
this.p[x] = this.find(this.p[x]);
}
return this.p[x];
}
union(a: number, b: number): boolean {
const [pa, pb] = [this.find(a), this.find(b)];
if (pa === pb) {
return false;
}
if (this.size[pa] > this.size[pb]) {
this.p[pb] = pa;
this.size[pa] += this.size[pb];
} else {
this.p[pa] = pb;
this.size[pb] += this.size[pa];
}
return true;
}
}
function removeStones(stones: number[][]): number {
const n = stones.length;
const uf = new UnionFind(n);
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
if (stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1]) {
ans += uf.union(i, j) ? 1 : 0;
}
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Track components with a list or adjacency matrix. Each union operation may need to update all n elements’ component labels, giving O(n) per union. For n union operations total: O(n²). Find is O(1) with direct lookup, but union dominates.
With path compression and union by rank, each find/union operation takes O(α(n)) amortized time, where α is the inverse Ackermann function — effectively constant. Space is O(n) for the parent and rank arrays. For m operations on n elements: O(m × α(n)) total.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.