☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

Most stones removed with same row or column

Medium TUF ID 513 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

n stones are placed on a 2D grid at integer coordinates, at most one stone per cell. stones[i] = [row, col]. A stone may be removed if, at that moment, some other stone that is still on the grid shares its row or its column. Return the maximum number of stones you can remove.

Constraints: 1 ≤ n ≤ 1000, 0 ≤ row, col ≤ 10^4, no two stones on the same cell.

Example 1

stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
answer = 5          // all six stones are linked; only one has to stay

Example 2

stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
answer = 3          // corners form one group of 4 (keep 1), centre is alone (keep it)

The key observation

Draw an edge between two stones when they share a row or a column. The stones split into connected components. Two facts settle the problem:

  1. At most size - 1 stones of a component can be removed. A stone shares a row or column only with stones in its own component (otherwise they would be in the same component). So once a component is down to one stone, that stone has no partner and can never go.
  2. Exactly size - 1 can always be removed. Take any spanning tree of the component, for example the DFS tree. Remove stones leaves first, always picking a stone whose tree parent is still present. The parent shares a row or column with it, so each removal is legal, and the root is the only stone left at the end.

Adding over components: answer = n - (number of components). The rest of the problem is just counting components, and how fast we can find the edges.

Approach 1: DFS on the stone graph

Intuition. Treat stones as vertices. Two stones are adjacent when row or col matches. Instead of building an adjacency list, the DFS can check all other stones on the fly: for the current stone u, every unvisited v with a matching row or column is a neighbour.

Algorithm.

  1. For every stone s not yet visited: increment components and run an iterative DFS from it.
  2. When popping stone u, scan all stones v; push each unvisited v that shares u’s row or column.
  3. Return n - components.
static int dfsStones(int[][] stones) {
    int n = stones.length, components = 0;
    boolean[] visited = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int s = 0; s < n; s++) {
        if (visited[s]) continue;
        components++;
        visited[s] = true;
        stack.push(s);
        while (!stack.isEmpty()) {
            int u = stack.pop();
            for (int v = 0; v < n; v++) {
                boolean linked = stones[u][0] == stones[v][0] || stones[u][1] == stones[v][1];
                if (!visited[v] && linked) {
                    visited[v] = true;
                    stack.push(v);
                }
            }
        }
    }
    return n - components;                       // each component keeps exactly one stone
}

Complexity. Time O(n^2): each stone is popped once and scans all n stones. Space O(n) for visited and the stack. With n ≤ 1000 this is a million cheap checks, perfectly fine, but it does not scale: there can be O(n^2) edges (a whole row of stones is a clique), and enumerating them is the bottleneck.

Approach 2: Disjoint Set over rows and columns

Intuition. Look at why two stones are connected: because they share a row node or a column node. So make the rows and columns themselves the vertices. Every stone becomes a single edge joining “row r” to “column c”. Two stones in the same row both touch the node for that row, so they automatically end up in the same component, and that is true transitively too. This bipartite row-column graph has only n edges, no matter how crowded a row is.

Rows and columns need distinct ids. Give row r the id r and column c the id maxRow + 1 + c; the Disjoint Set then needs maxRow + maxCol + 2 slots.

Not every row or column carries a stone, and empty rows would each count as a lonely component of their own. So we only count components among the nodes a stone actually touched, stored in usedNodes. Each such component contains at least one stone, and stones inside it are exactly one stone component, so the two counts agree.

static final class DisjointSet {
    final int[] parent, size;

    DisjointSet(int n) {
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
        return parent[x];
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                         // already in the same set
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;                                    // hang the smaller tree under the larger
        size[ra] += size[rb];
        return true;
    }
}

Algorithm.

  1. Find maxRow and maxCol, create a Disjoint Set of size maxRow + maxCol + 2.
  2. For each stone [r, c]: union(r, maxRow + 1 + c) and record both node ids in usedNodes.
  3. Count the used nodes that are their own root (find(node) == node). That is the number of components.
  4. Return n - components.
static int disjointSet(int[][] stones) {
    int maxRow = 0, maxCol = 0;
    for (int[] s : stones) {
        maxRow = Math.max(maxRow, s[0]);
        maxCol = Math.max(maxCol, s[1]);
    }
    DisjointSet ds = new DisjointSet(maxRow + maxCol + 2);   // rows 0..maxRow, then columns
    Set<Integer> usedNodes = new HashSet<>();
    for (int[] s : stones) {
        int rowNode = s[0], colNode = maxRow + 1 + s[1];
        ds.union(rowNode, colNode);
        usedNodes.add(rowNode);
        usedNodes.add(colNode);
    }
    int components = 0;
    for (int node : usedNodes) {
        if (ds.find(node) == node) components++;
    }
    return stones.length - components;
}

Dry run on example 2: maxRow = 2, so column c gets id 3 + c.

stone union groups after
(0,0) row0, col0 = 0, 3 {0,3}
(0,2) 0, 5 {0,3,5}
(1,1) 1, 4 {0,3,5}, {1,4}
(2,0) 2, 3 {0,2,3,5}, {1,4}
(2,2) 2, 5 already together

Used nodes {0,1,2,3,4,5} form 2 components, so the answer is 5 - 2 = 3.

Complexity. Time O(n · α(R + C) + R + C) where R and C bound the coordinates: creating the arrays is linear in their size, and each stone costs one near-constant union. Space O(R + C) for the Disjoint Set, plus O(n) for usedNodes.

If coordinates were huge (say up to 10^9), the array-based Disjoint Set would not fit. The fix is to compress coordinates first, or keep the parent map in a HashMap<Integer, Integer> and create nodes on demand; the logic is unchanged.

Why “rows and columns as nodes” works

This trick is worth remembering on its own. Whenever items are linked by sharing any attribute value (same row, same column, same email, same colour), connecting every pair of items is quadratic. Connecting each item to the attribute value instead is linear, and connectivity is preserved: two items share a value if and only if they are both adjacent to that value’s node. Accounts merge uses the same idea with emails playing the role of rows and columns.

Edge cases and pitfalls