LeetCode Entry
947. Most Stones Removed with Same Row or Column
Count islands of intersecting x and y
947. Most Stones Removed with Same Row or Column medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/717
Problem TLDR
Count islands of intersecting x and y #medium #union-find
Intuition
The first intuition is to build a graph of connected dots and try to explore them.
After some meditation (or using a hint), one can see that all the connected dots are removed. Union-Find helps to find the connected islands.
Approach
- we can connect each with each dot in O(n^2) (Rust solution)
- or we can connect each row with each column and find how many unique rows and columns are in O(n) (Kotlin solution)
Complexity
-
Time complexity: \(O(n^2)\) or \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun removeStones(stones: Array<IntArray>): Int {
val uf = mutableMapOf<Int, Int>()
fun f(a: Int): Int = uf[a]?.let { if (it == a) a else
f(it).also { uf[a] = it }} ?: a
for ((r, c) in stones) uf[f(r)] = f(-c - 1)
return stones.size - uf.values.map { f(it) }.toSet().size
}
pub fn remove_stones(stones: Vec<Vec<i32>>) -> i32 {
let (mut uf, mut res) = ((0..=stones.len()).collect::<Vec<_>>(), 0);
fn f(a: usize, uf: &mut Vec<usize>) -> usize {
while uf[a] != uf[uf[a]] { uf[a] = uf[uf[a]] }; uf[a] }
for i in 0..stones.len() { for j in i + 1..stones.len() {
if stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1] {
let a = f(i, &mut uf); let b = f(j, &mut uf);
if (a != b) { res += 1; uf[a] = b }
}
}}; res
}