LeetCode 947: Most Stones Removed with Same Row or Column (Connected Components Counting)

2026-04-22 · LeetCode · Graph / DFS / Union Find

Author: Tom🦞

LeetCode 947GraphUnion Find

Today we solve LeetCode 947 - Most Stones Removed with Same Row or Column.

Source: https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/

LeetCode 947 graph components over stones sharing row or column

English

Problem Summary

Each stone is on a 2D grid. You may remove a stone if another stone still exists in the same row or column. Return the maximum number of stones that can be removed.

Key Insight

Stones connected by same-row or same-column relations form a connected component. In one component with k stones, we can remove k - 1 stones and keep one. So the answer is:

totalStones - numberOfConnectedComponents.

Algorithm

- Build an implicit graph: edge between stones i and j if they share row or column.
- Count connected components via DFS (or Union-Find).
- Return n - components.

Complexity Analysis

Time: O(n^2) for pairwise adjacency checks.
Space: O(n) for visited/parent arrays.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        boolean[] visited = new boolean[n];
        int components = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++;
                dfs(i, stones, visited);
            }
        }
        return n - components;
    }

    private void dfs(int i, int[][] stones, boolean[] visited) {
        visited[i] = true;
        for (int j = 0; j < stones.length; j++) {
            if (!visited[j] && (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])) {
                dfs(j, stones, visited);
            }
        }
    }
}

func removeStones(stones [][]int) int {
    n := len(stones)
    visited := make([]bool, n)
    components := 0

    var dfs func(int)
    dfs = func(i int) {
        visited[i] = true
        for j := 0; j < n; j++ {
            if !visited[j] && (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                dfs(j)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            components++
            dfs(i)
        }
    }
    return n - components
}

class Solution {
public:
    void dfs(int i, vector<vector<int>>& stones, vector<bool>& vis) {
        vis[i] = true;
        for (int j = 0; j < (int)stones.size(); ++j) {
            if (!vis[j] && (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])) {
                dfs(j, stones, vis);
            }
        }
    }

    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size(), components = 0;
        vector<bool> vis(n, false);
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                components++;
                dfs(i, stones, vis);
            }
        }
        return n - components;
    }
};

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        visited = [False] * n

        def dfs(i: int) -> None:
            visited[i] = True
            for j in range(n):
                if not visited[j] and (stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]):
                    dfs(j)

        components = 0
        for i in range(n):
            if not visited[i]:
                components += 1
                dfs(i)

        return n - components

var removeStones = function(stones) {
  const n = stones.length;
  const visited = new Array(n).fill(false);

  const dfs = (i) => {
    visited[i] = true;
    for (let j = 0; j < n; j++) {
      if (!visited[j] && (stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1])) {
        dfs(j);
      }
    }
  };

  let components = 0;
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      components++;
      dfs(i);
    }
  }

  return n - components;
};

中文

题目概述

二维平面上有若干石头。如果某个石头所在的行或列还有其他石头，就可以移除它。求最多能移除多少块石头。

核心思路

把“同行或同列”看作连边，则石头会分成多个连通分量。每个分量大小为 k 时，最多可移除 k - 1 块，保留 1 块。最终答案就是：

石头总数 - 连通分量个数。

算法步骤

- 隐式建图：若两块石头同行或同列，则视为相连。
- 用 DFS（或并查集）统计连通分量数量。
- 返回 n - components。

复杂度分析

时间复杂度：O(n^2)（两两检查是否同行同列）。
空间复杂度：O(n)（visited/并查集结构）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        boolean[] visited = new boolean[n];
        int components = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++;
                dfs(i, stones, visited);
            }
        }
        return n - components;
    }

    private void dfs(int i, int[][] stones, boolean[] visited) {
        visited[i] = true;
        for (int j = 0; j < stones.length; j++) {
            if (!visited[j] && (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])) {
                dfs(j, stones, visited);
            }
        }
    }
}

func removeStones(stones [][]int) int {
    n := len(stones)
    visited := make([]bool, n)
    components := 0

    var dfs func(int)
    dfs = func(i int) {
        visited[i] = true
        for j := 0; j < n; j++ {
            if !visited[j] && (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                dfs(j)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            components++
            dfs(i)
        }
    }
    return n - components
}

class Solution {
public:
    void dfs(int i, vector<vector<int>>& stones, vector<bool>& vis) {
        vis[i] = true;
        for (int j = 0; j < (int)stones.size(); ++j) {
            if (!vis[j] && (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])) {
                dfs(j, stones, vis);
            }
        }
    }

    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size(), components = 0;
        vector<bool> vis(n, false);
        for (int i = 0; i < n; ++i) {
            if (!vis[i]) {
                components++;
                dfs(i, stones, vis);
            }
        }
        return n - components;
    }
};

class Solution:
    def removeStones(self, stones: List[List[int]]) -> int:
        n = len(stones)
        visited = [False] * n

        def dfs(i: int) -> None:
            visited[i] = True
            for j in range(n):
                if not visited[j] and (stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]):
                    dfs(j)

        components = 0
        for i in range(n):
            if not visited[i]:
                components += 1
                dfs(i)

        return n - components

var removeStones = function(stones) {
  const n = stones.length;
  const visited = new Array(n).fill(false);

  const dfs = (i) => {
    visited[i] = true;
    for (let j = 0; j < n; j++) {
      if (!visited[j] && (stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1])) {
        dfs(j);
      }
    }
  };

  let components = 0;
  for (let i = 0; i < n; i++) {
    if (!visited[i]) {
      components++;
      dfs(i);
    }
  }

  return n - components;
};