Most Stones Removed with Same Row or Column

class Solution {
public:
    int removeSimilarStones(vector<vector<int>>& stones) {
        int stoneCount = stones.size();
        DisjointSet ds(20002);

        for (int idx = 0; idx < stoneCount; idx++) {
            ds.mergeSets(
                stones[idx][0],
                stones[idx][1] + 10001);
        }

        return stoneCount - ds.totalComponents;
    }

private:
    class DisjointSet {
    public:
        vector<int> leader;
        int totalComponents;
        unordered_set<int> distinctElements;

        DisjointSet(int size) {
            leader.resize(size, -1);
            totalComponents = 0;
        }

        int root(int x) {
            if (distinctElements.find(x) == distinctElements.end()) {
                totalComponents++;
                distinctElements.insert(x);
            }

            if (leader[x] == -1) {
                return x;
            }
            return leader[x] = root(leader[x]);
        }

        void mergeSets(int x, int y) {
            int rootX = root(x);
            int rootY = root(y);

            if (rootX == rootY) {
                return;
            }

            leader[rootX] = rootY;
            totalComponents--;
        }
    };
};

The solution implements the method to solve the problem of removing stones arranged in a grid such that each stone is placed at a point having unique coordinates (row, column). Each removal must be from a row or column containing at least one other stone. The approach uses a Disjoint Set (Union-Find) data structure for efficient union and find operations to deal with the dynamic connectivity problem among stones.

Here's a breakdown of how the solution works:

• A DisjointSet class constructs the union-find structure with features to merge sets and find root of elements. It tracks the number of distinct components using totalComponents which initially counts each position separately.
• Each call to mergeSets(x, y) attempts to combine the components of stone at position x and position y + 10001 to ensure row and column mappings are treated uniquely.
• The number of stones that can be removed is determined by the difference between the total number of stones and the total number of distinct components (totalComponents) left after union operations. This is handled by the line return stoneCount - ds.totalComponents.

The core logic provided in removeSimilarStones function iteratively forms unions of rows and columns represented by each stone and then calculates the result by subtracting the count of unique components from the total number of stones. The optimization with + 10001 effectively separates row and column values to prevent unintended unions. Overall, this solution captures the essence of reducing the problem into connected components, each representing a group of stones that can be sequentially removed from the grid, except one left per group.

class Solution {

    public int removeDuplicateStones(int[][] stones) {
        int totalStones = stones.length;
        ComponentTracker ct = new ComponentTracker(20002); // Initialize with ample space

        // Connect stones that share either row or column
        for (int i = 0; i < totalStones; i++) {
            ct.merge(stones[i][0], stones[i][1] + 10001); // Offset y-coordinate for distinction
        }

        return totalStones - ct.countConnectedComponents;
    }

    // ComponentTracker using a union-find data structure
    class ComponentTracker {

        int[] owner; // Array to manage the owner of each node
        int countConnectedComponents; // Track the number of separated components
        Set<Integer> identifiedNodes; // Tracks noted nodes

        ComponentTracker(int size) {
            owner = new int[size];
            Arrays.fill(owner, -1); // Mark all nodes as independent initially
            countConnectedComponents = 0;
            identifiedNodes = new HashSet<>();
        }

        // Find method with compression
        int find(int x) {
            // Increment the component count if the node is new
            if (!identifiedNodes.contains(x)) {
                countConnectedComponents++;
                identifiedNodes.add(x);
            }

            if (owner[x] == -1) {
                return x;
            }
            return owner[x] = find(owner[x]);
        }

        // Merge sets
        void merge(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX != rootY) {
                owner[rootX] = rootY;
                countConnectedComponents--; // Reduce the component count on merging
            }
        }
    }
}

The solution provided in Java addresses the problem of removing stones from a 2D plane, where stones can be removed if they share the same row or column with another stone. Here's how the solution works:

• An inner class ComponentTracker is used, leveraging a union-find data structure for efficient component tracking.
• This class maintains an array owner representing the parent or owner of each node, and uses path compression in the find method to keep the tree flat.
• A hash set identifiedNodes tracks unique nodes or stones, and an integer countConnectedComponents keeps track of the distinct number of components or groups of connected stones.

The process can be described as follows:

1. Initialize ComponentTracker with a size large enough to distinctively map row and column indices without collision. In this case, it's twice the total possible coordinates because y-coordinates are offset by an additional value (10001) to differentiate from x-coordinates.
2. Iterate through each stone, and for each stone, use the union-find structure (merge method) to group stones that share the same row or column. This is done by mapping each stone's row and column to a unique identifier in the ComponentTracker.
3. The goal is to find the total number of stones minus the number of components obtained after all merges. The rationale being, each connected group of stones minus one represents the stones that can be removed while still leaving one stone as a representative of that row or column.
4. Return the count of removable stones after processing all stones.

The final result of the function removeDuplicateStones is the number of stones that can be removed according to the given rules.

This solution efficiently collapses multiple queries of connectivity and merging operations involved in determining removable stones into a linear complexity respective to the number of stones, thanks to the union-find algorithm with path compression and union by rank. This ensures that the solution is scalable and performs well even for larger datasets.

class Solution:
    def eliminateStones(self, stones):
        connect = self.MergeFindSet(20002)  # Use a large index to include all possible points

        # Connect stones via their coordinated axes
        for i, j in stones:
            connect.merge(i, j + 10001)  # Offset y-coordinate to separate from x

        return len(stones) - connect.countOfComponents

    class MergeFindSet:
        def __init__(self, size):
            self.rep = [-1] * size
            self.components = (
                0  # Track number of separate components
            )
            self.tracked_elements = (
                set()
            )  # Monitor unique elements in the structure

        # Compress path and find representative
        def find(self, element):
            if element not in self.tracked_elements:
                self.components += 1
                self.tracked_elements.add(element)

            if self.rep[element] == -1:
                return element
            self.rep[element] = self.find(self.rep[element])
            return self.rep[element]

        # Combine elements into a single set
        def merge(self, elem1, elem2):
            root1 = self.find(elem1)
            root2 = self.find(elem2)

            if root1 == root2:
                return

            self.rep[root1] = root2
            self.components -= 1

In the Python solution for the problem of removing the most stones from a grid where each stone has an associated row and column placement, the code utilizes a Union-Find data structure to efficiently find and union subsets, which are designated by the stone's coordinates. Here's an explanation of the approach and the core components of the code:

• The MergeFindSet class is a custom implementation of a Union-Find data structure. It uses:

  • An array rep that represents the parent of each element, and initialized to -1 to indicate each element is its own parent initially.
  • Two counters: components to count the number of distinct sets and tracked_elements to keep track of unique elements that have been accessed.

• Initialization and Path Compression:

  • Each stone, represented by pairs (i, j), is mapped onto a unique index in the Union-Find structure using connect.merge(i, j + 10001). The addition of 10001 to the y-coordinate ensures that row and column indices are treated separately.
  • The find function implements path compression to flatten the structure of the tree whenever it is accessed, speeding up future accesses.

• Union by Rank:

  • The merge function unites two subsets. If both elements have the same representative, which indicates they're already in the same set, it does nothing. Otherwise, it joins them by setting the representative of one to the representative of the other, and decrements the count of distinct sets.

• The eliminateStones function ultimately calculates how many stones can be removed, given by len(stones) - connect.countOfComponents. Each stone can be represented as a component in the Union-Find structure, with the maximum removals coming from uniting stones that share either a row or a column.

The ability to efficiently group stones by rows and columns and determining the number of connected components allows the solution to effectively determine the maximum number of stones that can be removed while still leaving at least one stone in each row and column that originally had stones.