Most Stones Removed with Same Row or Column - DSU

This comprehensive study note explores solving the "Most Stones Removed with Same Row or Column" problem using the Disjoint Set Union (DSU) data structure. We will progress from intuitive problem-working to mathematical deduction, spatial node mapping, and optimized implementation.

1. Problem Statement & The Core Challenge

We are given $N$ stones located at integer coordinate points $(r, c)$ on a 2D plane. Each coordinate point contains at most one stone.

• Removal Rule: A stone can be removed if and only if it shares either the same row or the same column as another stone that has not yet been removed.
• Objective: Find the maximum possible number of stones that can be removed from the board.

Example Board Layout (Stones represented as coordinates):
Row 0: [Stone at Col 0], [Stone at Col 2]
Row 1: [Stone at Col 3]
Row 3: [Stone at Col 0], [Stone at Col 2]
Row 4: [Stone at Col 3]

Can we remove every stone? Let's trace carefully.

2. Creator's Real-Life Mental Model & Dry Run

Real-Life Analogy: Connecting Dots in a Network

Imagine each stone as a physical device. If two devices share a wire (same row or same column), they are connected. When we remove a stone, we are effectively severing a connection or taking down a node that can cascade along connected neighbors.

Let's do a manual dry run of removing stones:

1. Stone at $(0,0)$: Shares row $0$ with $(0,2)$. We can remove $(0,0)$.
2. Stone at $(0,2)$: Shares column $2$ with $(3,2)$. We can remove $(0,2)$.
3. Stone at $(3,2)$: Shares row $3$ with $(3,0)$. We can remove $(3,2)$.
4. Stone at $(3,0)$: Now, look at $(3,0)$. Does it share a row or column with any remaining active stones?
   • Row $3$: No other stones left.
   • Column $0$: No other stones left.
   • Result: We are stuck! We cannot remove $(3,0)$ because its neighbors have already been stripped away.

Key Observation: Within any connected component of size $K$, no matter how you sequence your removals, exactly one stone must always be left behind because the final remaining stone will no longer share a row or column with any active partner.

3. Mathematical Derivation: $N$ minus Connected Components

Let us formalize the relationship between connected components and total removable stones.

Suppose we have $N$ total stones, which form $C$ independent connected components in our graph:

• Component 1 has $X_1$ stones.
• Component 2 has $X_2$ stones.
• Component $C$ has $X_C$ stones.

The sum of all stones across all components equals the total number of stones:

Within each component $i$, we can remove all stones except one. Therefore, the removable stones in component $i$ is $(X_i - 1)$.

Summing the removable stones across all components:

Rearranging the terms:

4. Transforming the 2D Grid into a Graph Problem

How do we represent rows and columns inside a graph data structure?

If we treat individual stones as nodes, linking them directly can be complex because coordinates can be large (e.g., $10^4 \times 10^4$). Instead, we can treat Rows and Columns as Nodes in our Disjoint Set!

Coordinate Shift Strategy

• Suppose our grid has max row index MaxRow (e.g., indices $0$ to $4$, total $5$ rows).
• Rows are mapped directly: Node ID for row $r$ is simply $r$.
• Columns are shifted to avoid index collisions with rows: Node ID for column $c$ is shifted by MaxRow + 1 + c.

Node ID Assignment:
Rows:    0, 1, 2, 3, 4  (Representing Row 0, 1, 2, 3, 4)
Columns: 5, 6, 7, 8     (Representing Col 0, 1, 2, 3 shifted by MaxRow + 1)

Whenever a stone exists at coordinate $(r, c)$, we simply perform a Union operation between the row node ($r$) and the column node ($c + \text{MaxRow} + 1$).

5. Step-by-Step Algorithm Walkthrough

1. Find Grid Dimensions: Iterate through the stones array to find MaxRow and MaxCol.
2. Initialize DSU: Create a Disjoint Set data structure with a capacity large enough to hold all row and column nodes: $\text{MaxRow} + \text{MaxCol} + 2$.
3. Union Rows and Columns: For each stone $(r, c)$, union the row node $r$ with the column node $(c + \text{MaxRow} + 1)$.
4. Count Unique Components:
   • Collect all unique nodes present in the stone list (both row and column nodes).
   • Find the ultimate parent for each using findUPar().
   • Count how many unique ultimate parents exist among the active stone nodes. This count represents our number of connected components ($C$).
5. Return Result: Compute $N - C$.

6. Production-Grade Implementation (C++ & Java)

C++ Solution

#cpp
#include <vector>
#include <unordered_map>
#include <algorithm>

class DisjointSet {
    std::vector<int> parent, size;
public:
    DisjointSet(int n) {
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }

    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }

    void unionBySize(int u, int v) {
        int rootU = findUPar(u);
        int rootV = findUPar(v);
        if (rootU == rootV) return;
        if (size[rootU] < size[rootV]) {
            parent[rootU] = rootV;
            size[rootV] += size[rootU];
        } else {
            parent[rootV] = rootU;
            size[rootU] += size[rootV];
        }
    }
};

class Solution {
public:
    int removeStones(std::vector<std::vector<int>>& stones) {
        int maxRow = 0;
        int maxCol = 0;

        // Step 1: Find maximum row and column indices
        for (auto& stone : stones) {
            maxRow = std::max(maxRow, stone[0]);
            maxCol = std::max(maxCol, stone[1]);
        }

        // Step 2: Initialize DSU with space for rows and shifted columns
        DisjointSet ds(maxRow + maxCol + 1);
        std::unordered_map<int, int> stoneNodes;

        // Step 3: Union row and column for each stone
        for (auto& stone : stones) {
            int nodeRow = stone[0];
            int nodeCol = stone[1] + maxRow + 1;
            
            ds.unionBySize(nodeRow, nodeCol);
            
            stoneNodes[nodeRow] = 1;
            stoneNodes[nodeCol] = 1;
        }

        // Step 4: Count unique connected components (distinct ultimate parents)
        int componentCount = 0;
        for (auto& it : stoneNodes) {
            int node = it.first;
            if (ds.findUPar(node) == node) {
                componentCount++;
            }
        }

        // Step 5: Total stones minus number of components
        return stones.size() - componentCount;
    }
};

Java Equivalent Logic Structure

import java.util.*;

class DisjointSet {
    List<Integer> parent = new ArrayList<>();
    List<Integer> size = new ArrayList<>();

    public DisjointSet(int n) {
        for (int i = 0; i <= n; i++) {
            parent.add(i);
            size.add(1);
        }
    }

    public int findUPar(int node) {
        if (node == parent.get(node)) {
            return node;
        }
        int ulp = findUPar(parent.get(node));
        parent.set(node, ulp);
        return parent.get(node);
    }

    public void unionBySize(int u, int v) {
        int rootU = findUPar(u);
        int rootV = findUPar(v);
        if (rootU == rootV) return;
        if (size.get(rootU) < size.get(rootV)) {
            parent.set(rootU, rootV);
            size.set(rootV, size.get(rootV) + size.get(rootV));
        } else {
            parent.set(rootV, rootU);
            size.set(rootU, size.get(rootU) + size.get(rootV));
        }
    }
}

7. Complexity Analysis

• Time Complexity:

  • Finding max rows and columns takes $\mathcal{O}(N)$, where $N$ is the number of stones.
  • Performing unionBySize operations takes nearly constant time, $\mathcal{O}(N \cdot \alpha(\text{V}))$, where $\alpha$ is the Inverse Ackermann function.
  • Counting components takes $\mathcal{O}(N)$ iterations over unique nodes.
  • Overall Time Complexity: $\mathcal{O}(N \alpha(V))$, which is extremely efficient and executes in milliseconds for competitive programming constraints.

• Space Complexity:

  • Storing parent and size arrays in DSU requires $\mathcal{O}(\text{MaxRow} + \text{MaxCol})$ space.
  • The hash map (stoneNodes) requires $\mathcal{O}(N)$ space.
  • Overall Space Complexity: $\mathcal{O}(\text{MaxRow} + \text{MaxCol} + N)$.

8. Summary and Key Takeaways

• Problem Reduction: The stone removal puzzle reduces directly to calculating Total Stones ($N$) minus Connected Components ($C$).
• Invariant Rule: Within any connected component of stones, exactly one stone must remain unremoved because it will eventually be isolated.
• Row-Column Graph Modeling: Instead of linking stones to stones, treat rows and shifted columns as graph nodes. This drastically reduces the graph's vertex count and simplifies connection logic.
• Coordinate Shifting Formula: Shift column indices by MaxRow + 1 (nodeCol = stone[1] + maxRow + 1) to prevent index collision with row nodes.
• DSU Efficiency: Disjoint Set Union with Path Compression and Union by Size provides near-$\mathcal{O}(1)$ time complexity per union-find operation, making it the optimal choice for dynamic connectivity problems.
• Component Counting: Count unique connected components by checking how many distinct ultimate parents exist among active row/column nodes that contain stones.