LeetCode 947: Most Stones Removed with Same Row or Column Solution

Master LeetCode problem 947 (Most Stones Removed with Same Row or Column), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

947. Most Stones Removed with Same Row or Column

Medium

Hash Table Depth-First Search Union Find Graph

Problem Explanation

Explanation:

The problem can be solved using a Union Find (Disjoint Set Union) data structure. We treat stones as nodes in a graph, where stones in the same row or column are connected. By finding connected components, we can determine the maximum number of stones that can be removed.

Create a Union Find data structure with each stone as a node.
For each stone pair, if they share the same row or column, union their components.
The maximum number of stones that can be removed is the total number of stones minus the number of connected components.

Time Complexity: O(n * α(n)) where α is the inverse Ackermann function (almost constant). Space Complexity: O(n)

Solution Code

class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        UnionFind uf = new UnionFind(n);
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                    uf.union(i, j);
                }
            }
        }
        
        return n - uf.getNumOfComponents();
    }
    
    class UnionFind {
        int[] parent;
        int components;
        
        public UnionFind(int n) {
            parent = new int[n];
            components = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                parent[rootX] = rootY;
                components--;
            }
        }
        
        public int getNumOfComponents() {
            return components;
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 947 (Most Stones Removed with Same Row or Column)?

This page provides optimized solutions for LeetCode problem 947 (Most Stones Removed with Same Row or Column) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 947 (Most Stones Removed with Same Row or Column)?

The time complexity for LeetCode 947 (Most Stones Removed with Same Row or Column) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 947 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 947 in Java, C++, or Python.

Back to LeetCode Solutions