Get started

Most Stones Removed with Same Row or Column — Medium Problem & Solution

Stones sit on distinct integer points of a 2D board; stones[i] = [xi, yi] is the position of stone i.

Problem statement

Stones sit on distinct integer points of a 2D board; stones[i] = [xi, yi] is the position of stone i.

A stone may be removed if at least one other stone that is still on the board shares its row (same x) or its column (same y). Remove stones one at a time, in any order you like.

Return the largest number of stones that can be removed.

Example 1

Input: stones = [[0,0],[0,2],[1,1],[2,1],[2,2]]
Output: 4
Explanation: All five stones are linked through shared rows and columns, so all but one can go.

Example 2

Input: stones = [[3,4],[3,7],[5,5]]
Output: 1
Explanation: `[3,4]` and `[3,7]` share row 3, so one of them can be removed; `[5,5]` shares nothing.

Example 3

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

Constraints

  • 1 <= stones.length <= 1000
  • 0 <= xi, yi <= 10^4
  • no two stones are at the same point

How to solve Most Stones Removed with Same Row or Column

Treat stones as nodes joined when they share a row or column. Each connected component can be whittled down to a single stone, and no component can lose its last stone, so the answer is n − components.

Approach

  1. Start a union-find with one set per stone and a component count of n.
  2. For every pair of stones that share an x or a y, union them; each successful union lowers the count by one.
  3. Return n minus the final component count.

Why it works

Take a spanning tree of a component and repeatedly remove a leaf: a leaf still has its tree neighbour on the board, which shares its row or column, so the removal is legal — this empties the component down to one stone. Conversely, the last stone of a component has no partner left in its row or column (any such partner would be in the same component), so it can never be removed. Components never interact, so the total is the sum over components of size − 1.

Complexity

  • Time — O(n² · α(n))
  • Space — O(n)

Pitfalls

  • The removal order matters for a single sequence but not for the maximum — don't try to simulate greedy removals.
  • Two stones in the same component need not share a row or column directly; connectivity is transitive.
  • Rows and columns can also be unioned as nodes themselves (offsetting columns) for an O(n) variant; the pairwise version is fine for n ≤ 1000.

Reference solution

Python

from typing import List

def removeStones(stones: List[List[int]]) -> int:
    n = len(stones)
    root = list(range(n))

    def find(x):
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    comps = n
    for i in range(n):
        for j in range(i + 1, n):
            if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
                a, b = find(i), find(j)
                if a != b:
                    root[a] = b
                    comps -= 1
    return n - comps

JavaScript

var removeStones = function(stones) {
    var n = stones.length;
    var root = [];
    for (var i = 0; i < n; i++) root.push(i);
    var find = function(x) {
        while (root[x] !== x) { root[x] = root[root[x]]; x = root[x]; }
        return x;
    };
    var comps = n;
    for (var a = 0; a < n; a++) {
        for (var b = a + 1; b < n; b++) {
            if (stones[a][0] === stones[b][0] || stones[a][1] === stones[b][1]) {
                var ra = find(a), rb = find(b);
                if (ra !== rb) { root[ra] = rb; comps--; }
            }
        }
    }
    return n - comps;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 71 graph problems · the whole catalogue

Learn the technique: Graph Data Structure · Depth-First Search (DFS)