Most stones removed with same row or column

Hash Table Depth-First Search Union-Find Graph Theory

62.7% acceptance

Feb 25, 2026

6420

709

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn remove_stones(stones: Vec<Vec<i32>>) -> i32 {
    let n = stones.len();
    let mut parent: Vec<usize> = (0..n).collect();
    fn find(p: &mut Vec<usize>, x: usize) -> usize {
      if p[x] != x { p[x] = find(p, p[x]); }
      p[x]
    }
    fn union(p: &mut Vec<usize>, x: usize, y: usize) {
      let px = find(p, x);
      let py = find(p, y);
      if px != py { p[px] = py; }
    }
    for i in 0..n {
      for j in i+1..n {
        if stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1] {
          union(&mut parent, i, j);
        }
      }
    }
    let mut roots = std::collections::HashSet::new();
    for i in 0..n { roots.insert(find(&mut parent, i)); }
    (n - roots.len()) as i32
  }
}