947. Most Stones Removed with Same Row or Column
Most Stones Removed with Same Row or Column
On a 2D plane, we place n stones at some integer coordinate points. Each coordinate point may have at most one stone.
A stone can be removed if it shares either the same row or the same column as another stone that has not been removed.
Given an array stones of length n that stones[i] = [xi, yi] represents the location of the ith stone, returns the largest possible number of stones that can be removed.
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] Output: 5 Explanation: One way to remove 5 stones is as follows: 1. Remove stone [2,2] because it shares the same row as [2,1]. 2. Remove stone [2,1] because it shares the same column as [0,1]. 3. Remove stone [1,2] because it shares the same row as [1,0]. 4. Remove stone [1,0] because it shares the same column as [0,0]. 5. Remove stone [0,1] because it shares the same row as [0,0]. Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.
Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]] Output: 3 Explanation: One way to make 3 moves is as follows: 1. Remove stone [2,2] because it shares the same row as [2,0]. 2. Remove stone [2,0] because it shares the same column as [0,0]. 3. Remove stone [0,2] because it shares the same row as [0,0]. Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.
Example 3:
Input: stones = [[0,0]] Output: 0 Explanation: [0,0] is the only stone on the plane, so you cannot remove it.
Constraints:
1 <= stones.length <= 10000 <= xi, yi <= 104- No two stones are at the same coordinate point.
Process every vertex, if they share the same row or column that means they are connected, so union them. Once the Union Find has been set up, the number of parents gives you the answer.
I used a map to keep track of nodes and parents but in hindsight this can be done by using a parents array only.
/**
* @param {number[][]} stones
* @return {number}
*/
var Node = function(c){
this.parent = this;
this.c = c;
this.size = 1;
}
class UnionFind {
constructor(vertices){
this.nodes = [];
this.map = new Map();
for(let v of vertices){
let n = new Node(v);
this.map.set(this.getKey(v), n)
this.nodes.push(n);
}
for(let i=0; i < vertices.length-1; i++){
for(let j=i+1; j < vertices.length; j++){
if(this.isConnected(vertices[i], vertices[j])){
let [k1, k2] = [this.map.get(this.getKey(vertices[i])),
this.map.get(this.getKey(vertices[j]))]
this.union(k1, k2);
}
}
}
}
getKey([x,y]){
return `x${x}-y${y}`;
}
getParent(v1){
let p = this.map.get(this.getKey(v1));
while(p !== p.parent){
p = p.parent;
}
return p;
}
union(n1, n2){
let [p1, p2] = [n1, n2];
while(p1.parent !== p1){
p1 = p1.parent;
}
while(p2.parent !== p2){
p2 = p2.parent;
}
if(p1 !== p2){
if(p1.size > p2.size){
p2.parent = p1;
p2.size = 0;
p1.size = p1.size+1;
}
else {
p1.parent = p2;
p1.size = 0;
p2.size = p2.size+1;
}
}
// console.log(p1.size, p2.size)
}
isConnected(v1, v2){
let [x1, y1] = v1;
let [x2, y2] = v2;
return x1===x2 || y1 === y2;
}
}
var removeStones = function(stones) {
let uf = new UnionFind(stones);
let answer = 0;
for(let n of uf.nodes){
if(n.size > 0) answer++;
}
return stones.length - answer;
};Resource: https://www.youtube.com/watch?v=ID00PMy0-vE
const STONE_RANGE = 10000
// Disjoint Set Union
class DSU {
constructor(sets) {
this.parents = [...Array(sets).keys()]
this.rank = Array(sets).fill(0)
}
find(x) {
const { parents } = this
if (parents[x] !== x) {
// Path compression
parents[x] = this.find(parents[x])
}
return parents[x]
}
union(x, y) {
const { parents, rank } = this
const leaderX = this.find(x)
const leaderY = this.find(y)
// Union by rank
if (leaderX === leaderY) {
return false
} else if (rank[leaderX] < rank[leaderY]) {
parents[leaderX] = leaderY
} else {
if (rank[leaderY] < rank[leaderX]) {
rank[leaderX]++
}
parents[leaderY] = leaderX
}
return true
}
}
/**
* @param {number[][]} stones
* @return {number}
*/
var removeStones = function(stones) {
// Space for rows and cols
const dsu = new DSU(STONE_RANGE * 2)
for (const [r, c] of stones) {
dsu.union(r, c + STONE_RANGE)
}
// Count how many distinct components
const seen = new Set()
for (const [r] of stones) seen.add(dsu.find(r))
return stones.length - seen.size
};Another way to see this problem is 'what is the minimum number of stones we can have remaining?'. To solve this, one must first realize that for any number of stones in a set, as long as they are connected to one other stone in the set by row or by col, they can be removed till only one stone is remaining.
Hence we can find the number of remaining stones by finding the number of disjointed sets. From there, the maximum number of stones we can remove will be = total num of stones - remaining stones.
The solution, first I get a mapping of all stones in each row and col. Then, for each new unvisited stone in the arr, do a dfs to mark all connected stones in the same row and same col as visited. In this way, every new unvisited stone in the arr will be a new disjoint set, hence we increment the remaining stones value by 1 when we reach a new unvisited stone.
var removeStones = function(stones) {
const rows = new Map();
const cols = new Map();
for (const [r, c] of stones) {
rows.set(r, (rows.get(r) || new Set()).add(c));
cols.set(c, (cols.get(c) || new Set()).add(r));
}
const visited = new Set();
const visit = (i, j) => {
const key = `${i}-${j}`;
if (visited.has(key)) return;
visited.add(key);
const adjRow = rows.get(i);
for (const col of adjRow) {
visit(i, col);
}
const adjCol = cols.get(j);
for (const row of adjCol) {
visit(row, j);
}
}
let remainingStones = 0;
for (const [r, c] of stones) {
const key = `${r}-${c}`;
if (visited.has(key)) continue;
visit(r,c);
remainingStones++;
}
return stones.length - remainingStones;
};const removeStones = (stones) => {
const rowMap = {};
const colMap = {};
let visited = new Set();
let numbOfGraphs = 0;
stones.forEach((stone) => {
rowMap[stone[0]] = rowMap[stone[0]] === undefined ? [stone[1]] : rowMap[stone[0]].concat([stone[1]]);
colMap[stone[1]] = colMap[stone[1]] === undefined ? [stone[0]] : colMap[stone[1]].concat([stone[0]]);
});
stones.forEach((stone) => {
const stoneString = `${stone[0]}-${stone[1]}`;
if (visited.has(stoneString)) { return; }
numbOfGraphs += 1;
markAllStonesInGraph(stone, visited, rowMap, colMap);
});
return stones.length - numbOfGraphs;
};
function markAllStonesInGraph (stone, visited, rowMap, colMap) {
const stoneString = `${stone[0]}-${stone[1]}`;
if (visited.has(stoneString)) { return; }
visited.add(stoneString);
const inSameRow = rowMap[stone[0]];
const inSameCol = colMap[stone[1]];
(inSameRow || []).forEach((item) => {
markAllStonesInGraph ([stone[0], item], visited, rowMap, colMap);
});
(inSameCol || []).forEach((item) => {
markAllStonesInGraph ([item, stone[1]], visited, rowMap, colMap);
});
};
That’s all folks! In this post, we solved LeetCode problem 947. Most Stones are Removed with the Same Row or Column
I hope you have enjoyed this post. Feel free to share your thoughts on this.
You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.
In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!
Comments
Post a Comment