947. Most Stones Removed with Same Row or Column

leetcode medium

#array#csharp#graph#hash-table#leetcode#linked-list#medium#search#string

Task

Учитывая массив stones длины n, где stones[i] = [xi, yi] представляет местоположение i-го камня, верните наибольшее возможное количество камней, которые могут быть удалены.

Пример:

Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

Output: 5

C# solution

matched/original

public class Solution {
    public int RemoveStones(int[][] stones) {
        Dictionary<int, int> parent = new Dictionary<int, int>();
        
        int Find(int x) {
            if (!parent.ContainsKey(x)) parent[x] = x;
            if (parent[x] != x) parent[x] = Find(parent[x]);
            return parent[x];
        }
        
        void Union(int x, int y) {
            parent[Find(x)] = Find(y);
        }
        
        foreach (var stone in stones) {
            Union(stone[0], ~stone[1]);
        }
        
        HashSet<int> uniqueRoots = new HashSet<int>();
        foreach (var key in parent.Keys) {
            uniqueRoots.Add(Find(key));
        }
        
        return stones.Length - uniqueRoots.Count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int RemoveStones(int[][] stones) {
        unordered_map<int, int> parent = new unordered_map<int, int>();
        
        int Find(int x) {
            if (!parent.count(x)) parent[x] = x;
            if (parent[x] != x) parent[x] = Find(parent[x]);
            return parent[x];
        }
        
        void Union(int x, int y) {
            parent[Find(x)] = Find(y);
        }
        
        foreach (var stone in stones) {
            Union(stone[0], ~stone[1]);
        }
        
        HashSet<int> uniqueRoots = new HashSet<int>();
        foreach (var key in parent.Keys) {
            uniqueRoots.push_back(Find(key));
        }
        
        return stones.size() - uniqueRoots.size();
    }
}

Java solution

matched/original

import java.util.*;

class Solution {
    public int removeStones(int[][] stones) {
        Map<Integer, Integer> parent = new HashMap<>();
        
        int find(int x) {
            if (!parent.containsKey(x)) {
                parent.put(x, x);
            }
            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x)));
            }
            return parent.get(x);
        }
        
        void union(int x, int y) {
            parent.put(find(x), find(y));
        }
        
        for (int[] stone : stones) {
            union(stone[0], ~stone[1]);
        }
        
        Set<Integer> uniqueRoots = new HashSet<>();
        for (int key : parent.keySet()) {
            uniqueRoots.add(find(key));
        }
        
        return stones.length - uniqueRoots.size();
    }
}

JavaScript solution

matched/original

var removeStones = function(stones) {
    const parent = {};
    
    function find(x) {
        if (!(x in parent)) parent[x] = x;
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    function union(x, y) {
        parent[find(x)] = find(y);
    }
    
    for (const [x, y] of stones) {
        union(x, ~y);
    }
    
    const uniqueRoots = new Set(Object.keys(parent).map(find));
    return stones.length - uniqueRoots.size;
};

Python solution

matched/original

def removeStones(stones):
    parent = {}
    
    def find(x):
        if parent.setdefault(x, x) != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        parent[find(x)] = find(y)
    
    for x, y in stones:
        union(x, ~y)
    
    return len(stones) - len({find(x) for x in parent})

Go solution

matched/original

package main

func removeStones(stones [][]int) int {
    parent := make(map[int]int)
    
    var find func(int) int
    find = func(x int) int {
        if parent[x] == 0 {
            parent[x] = x
        }
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    
    union := func(x, y int) {
        parent[find(x)] = find(y)
    }
    
    for _, stone := range stones {
        union(stone[0], ^stone[1])
    }
    
    uniqueRoots := make(map[int]bool)
    for k := range parent {
        uniqueRoots[find(k)] = true
    }
    
    return len(stones) - len(uniqueRoots)
}

Explanation

Algorithm

Представить каждую строку и столбец как узлы в графе.

Создать связи между узлами для камней, которые находятся в той же строке или столбце.

Использовать алгоритм поиска в глубину (DFS) или объединение-поиска (Union-Find), чтобы найти компоненты связности.

Количество камней, которые могут быть удалены, это общее количество камней минус количество компонентов связности.

😎