ProgramGuru

Most Stones Removed with Same Row or Column

Problem and examples

You are given n stones placed on a 2D plane, where each stone has a unique position represented by [x, y]. A stone can be removed if there exists another stone in the same row or column.

The objective is to remove as many stones as possible under the given rule. Return the maximum number of stones that can be removed.

Stones Maximum Removable Explanation
[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]] 5 All stones but one can be removed as they form connected components.
[[0,0],[0,2],[1,1],[2,0],[2,2]] 3 Stones can be grouped and reduced via graph components.
[[0,0]] 0 No other stone in same row or column — cannot remove it.
[[0,0],[0,1]] 1 Same row, can remove one.

How it works

Understanding the Problem

We are given a set of stones on a 2D grid. Each stone is placed at a unique coordinate (x, y). We are allowed to remove a stone if there is at least one other stone in the same row or column.

The goal is to find the maximum number of stones we can remove, following the given rule.

At first glance, this may not seem like a graph problem—but it is. Think of each stone as a node in a graph. If two stones share the same row or column, draw an edge between them. The stones form connected components through these edges.

From each connected component, we can remove all the stones except one. Therefore, the number of stones we can remove is:

total number of stones - number of connected components

Step-by-Step Solution with Example

step 1: Represent the Problem as a Graph

Each stone is a node. If two stones have the same row or the same column, draw an edge between them.

For example, suppose the stones are placed at the following coordinates:

[[0, 0], [0, 1], [1, 0], [1, 2], [2, 2], [2, 3]]

We connect stones sharing rows or columns:

  • [0, 0] is connected to [0, 1] and [1, 0]
  • [1, 2] is connected to [2, 2]
  • [2, 2] is connected to [2, 3]

We get two connected components: one with [0, 0], [0, 1], [1, 0] and another with [1, 2], [2, 2], [2, 3].

step 2: Count Connected Components

We can use Depth-First Search (DFS) to visit all stones in a connected component.

Maintain a visited set. For each unvisited stone, do a DFS and mark all stones in that component as visited. Count how many times you initiate DFS—this gives the number of connected components.

step 3: Calculate the Answer

Once we know the number of connected components, subtract that from the total number of stones.

In our example:

Total stones = 6
Connected components = 2
Removable stones = 6 - 2 = 4

Edge Cases

  • No stones: If the input is empty, the answer is 0.
  • All stones in different rows and columns: No stone shares a row or column, so no stone can be removed. Each stone is its own component.
  • All stones in the same row or column: All stones belong to one component, so we can remove all except one.
  • Duplicate coordinates: Problem assumes all coordinates are unique, but validation might be necessary in real input.

Finally

This problem is a classic example of reducing a 2D grid problem into a graph traversal problem. By modeling the connections between stones based on rows and columns, we were able to use DFS to find connected components and calculate the solution efficiently.

Always remember: when you’re allowed to remove things based on indirect connections, it often signals that a graph approach will help.

  1. Build a graph where each stone is a node.
  2. Connect stones that share the same row or column using edges.
  3. Track visited stones using a visited set.
  4. Iterate over each unvisited stone and perform DFS to mark all stones in the same component.
  5. Count the number of such DFS calls — this gives the number of connected components.
  6. Return total stones - number of components as the final answer.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

// Union-Find data structure for disjoint sets
typedef struct {
    int *parent;
    int *rank;
    int size;
} UnionFind;

UnionFind *uf_create(int n) {
    UnionFind *uf = (UnionFind *)malloc(sizeof(UnionFind));
    uf->size = n;
    uf->parent = (int *)malloc(n * sizeof(int));
    uf->rank = (int *)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
    }
    return uf;
}

int uf_find(UnionFind *uf, int x) {
    if (uf->parent[x] != x)
        uf->parent[x] = uf_find(uf, uf->parent[x]);
    return uf->parent[x];
}

void uf_union(UnionFind *uf, int x, int y) {
    int rootX = uf_find(uf, x);
    int rootY = uf_find(uf, y);
    if (rootX != rootY) {
        if (uf->rank[rootX] < uf->rank[rootY]) {
            uf->parent[rootX] = rootY;
        } else if (uf->rank[rootX] > uf->rank[rootY]) {
            uf->parent[rootY] = rootX;
        } else {
            uf->parent[rootY] = rootX;
            uf->rank[rootX]++;
        }
    }
}

int removeStones(int stones[][2], int stonesSize) {
    int maxCoord = 0;
    for (int i = 0; i < stonesSize; i++) {
        if (stones[i][0] > maxCoord) maxCoord = stones[i][0];
        if (stones[i][1] > maxCoord) maxCoord = stones[i][1];
    }

    UnionFind *uf = uf_create(2 * (maxCoord + 1));

    for (int i = 0; i < stonesSize; i++) {
        // Union row index with column index offset by maxCoord + 1
        uf_union(uf, stones[i][0], stones[i][1] + maxCoord + 1);
    }

    int connectedComponents = 0;
    int *visited = (int *)calloc(2 * (maxCoord + 1), sizeof(int));

    for (int i = 0; i < stonesSize; i++) {
        int root = uf_find(uf, stones[i][0]);
        if (!visited[root]) {
            visited[root] = 1;
            connectedComponents++;
        }
    }

    free(visited);
    free(uf->parent);
    free(uf->rank);
    free(uf);

    return stonesSize - connectedComponents;
}

int main() {
    int stones1[][2] = {{0,0}, {0,1}, {1,0}, {1,2}, {2,1}, {2,2}};
    int size1 = sizeof(stones1) / sizeof(stones1[0]);
    printf("%d\n", removeStones(stones1, size1)); // Output: 5

    int stones2[][2] = {{0,0}, {0,2}, {1,1}, {2,0}, {2,2}};
    int size2 = sizeof(stones2) / sizeof(stones2[0]);
    printf("%d\n", removeStones(stones2, size2)); // Output: 3

    int stones3[][2] = {{0,0}};
    int size3 = sizeof(stones3) / sizeof(stones3[0]);
    printf("%d\n", removeStones(stones3, size3)); // Output: 0

    return 0;
}

C++ implementation

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class UnionFind {
private:
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;
public:
    int find(int x) {
        if (parent.find(x) == parent.end()) {
            parent[x] = x;
            rank[x] = 0;
        }
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

int removeStones(vector<vector<int>> &stones) {
    UnionFind uf;
    for (auto &stone : stones) {
        // Union rows and columns offset by 10000 to avoid collision
        uf.unite(stone[0], stone[1] + 10000);
    }

    unordered_map<int, bool> uniqueParents;
    for (auto &stone : stones) {
        uniqueParents[uf.find(stone[0])] = true;
    }

    return stones.size() - uniqueParents.size();
}

int main() {
    vector<vector<int>> stones1 = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
    cout << removeStones(stones1) << endl; // Output: 5

    vector<vector<int>> stones2 = {{0,0},{0,2},{1,1},{2,0},{2,2}};
    cout << removeStones(stones2) << endl; // Output: 3

    vector<vector<int>> stones3 = {{0,0}};
    cout << removeStones(stones3) << endl; // Output: 0

    return 0;
}

Python implementation

from typing import List

def remove_stones(stones: List[List[int]]) -> int:
    parent = {}

    def find(x):
        if x != parent.setdefault(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 + 10000)

    unique_roots = set(find(x) for x, y in stones)
    return len(stones) - len(unique_roots)

if __name__ == "__main__":
    print(remove_stones([[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]])) # Output: 5
    print(remove_stones([[0,0],[0,2],[1,1],[2,0],[2,2]])) # Output: 3
    print(remove_stones([[0,0]])) # Output: 0

Java implementation

import java.util.*;

public class RemoveStones {

    static class UnionFind {
        private Map<Integer, Integer> parent = new HashMap<>();
        private Map<Integer, Integer> rank = new HashMap<>();

        public int find(int x) {
            parent.putIfAbsent(x, x);
            rank.putIfAbsent(x, 0);
            if (parent.get(x) != x) {
                parent.put(x, find(parent.get(x)));
            }
            return parent.get(x);
        }

        public void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX != rootY) {
                int rankX = rank.get(rootX);
                int rankY = rank.get(rootY);
                if (rankX < rankY) {
                    parent.put(rootX, rootY);
                } else if (rankX > rankY) {
                    parent.put(rootY, rootX);
                } else {
                    parent.put(rootY, rootX);
                    rank.put(rootX, rankX + 1);
                }
            }
        }
    }

    public static int removeStones(int[][] stones) {
        UnionFind uf = new UnionFind();
        for (int[] stone : stones) {
            uf.union(stone[0], stone[1] + 10000);
        }

        Set<Integer> uniqueRoots = new HashSet<>();
        for (int[] stone : stones) {
            uniqueRoots.add(uf.find(stone[0]));
        }

        return stones.length - uniqueRoots.size();
    }

    public static void main(String[] args) {
        int[][] stones1 = {{0,0}, {0,1}, {1,0}, {1,2}, {2,1}, {2,2}};
        System.out.println(removeStones(stones1)); // Output: 5

        int[][] stones2 = {{0,0}, {0,2}, {1,1}, {2,0}, {2,2}};
        System.out.println(removeStones(stones2)); // Output: 3

        int[][] stones3 = {{0,0}};
        System.out.println(removeStones(stones3)); // Output: 0
    }
}

JavaScript implementation

function removeStones(stones) {
  const adj = new Map();

  // Build graph with row/col identifier trick to avoid collisions
  for (const [x, y] of stones) {
    const row = `r${x}`;
    const col = `c${y}`;

    if (!adj.has(row)) adj.set(row, []);
    if (!adj.has(col)) adj.set(col, []);

    adj.get(row).push(col);
    adj.get(col).push(row);
  }

  const visited = new Set();
  let components = 0;

  function dfs(node) {
    visited.add(node);
    for (const neighbor of adj.get(node) || []) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
  }

  for (const [x, y] of stones) {
    const node = `r${x}`;
    if (!visited.has(node)) {
      dfs(node);
      components++;
    }
  }

  return stones.length - components;
}

console.log(removeStones([[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]])); // Output: 5
console.log(removeStones([[0,0],[0,2],[1,1],[2,0],[2,2]])); // Output: 3
console.log(removeStones([[0,0]])); // Output: 0

Go implementation

package main

import "fmt"

func find(parent []int, x int) int {
    if parent[x] != x {
        parent[x] = find(parent, parent[x])
    }
    return parent[x]
}

func union(parent []int, rank []int, x int, y int) {
    rootX := find(parent, x)
    rootY := find(parent, y)
    if rootX != rootY {
        if rank[rootX] < rank[rootY] {
            parent[rootX] = rootY
        } else if rank[rootX] > rank[rootY] {
            parent[rootY] = rootX
        } else {
            parent[rootY] = rootX
            rank[rootX]++
        }
    }
}

func removeStones(stones [][]int) int {
    maxCoord := 0
    for _, stone := range stones {
        if stone[0] > maxCoord {
            maxCoord = stone[0]
        }
        if stone[1] > maxCoord {
            maxCoord = stone[1]
        }
    }

    parent := make([]int, 2*(maxCoord+1))
    rank := make([]int, 2*(maxCoord+1))
    for i := 0; i < len(parent); i++ {
        parent[i] = i
    }

    for _, stone := range stones {
        union(parent, rank, stone[0], stone[1]+maxCoord+1)
    }

    uniqueRoots := make(map[int]bool)
    for _, stone := range stones {
        root := find(parent, stone[0])
        uniqueRoots[root] = true
    }

    return len(stones) - len(uniqueRoots)
}

func main() {
    stones1 := [][]int{{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}}
    fmt.Println(removeStones(stones1)) // Output: 5

    stones2 := [][]int{{0,0},{0,2},{1,1},{2,0},{2,2}}
    fmt.Println(removeStones(stones2)) // Output: 3

    stones3 := [][]int{{0,0}}
    fmt.Println(removeStones(stones3)) // Output: 0
}

Rust implementation

use std::collections::HashMap;

struct UnionFind {
    parent: HashMap<i32, i32>,
    rank: HashMap<i32, i32>,
}

impl UnionFind {
    fn new() -> Self {
        Self {
            parent: HashMap::new(),
            rank: HashMap::new(),
        }
    }

    fn find(&mut self, x: i32) -> i32 {
        if !self.parent.contains_key(&x) {
            self.parent.insert(x, x);
            self.rank.insert(x, 0);
        }
        if *self.parent.get(&x).unwrap() != x {
            let parent_x = *self.parent.get(&x).unwrap();
            let root = self.find(parent_x);
            self.parent.insert(x, root);
        }
        *self.parent.get(&x).unwrap()
    }

    fn union(&mut self, x: i32, y: i32) {
        let root_x = self.find(x);
        let root_y = self.find(y);
        if root_x != root_y {
            let rank_x = *self.rank.get(&root_x).unwrap();
            let rank_y = *self.rank.get(&root_y).unwrap();
            if rank_x < rank_y {
                self.parent.insert(root_x, root_y);
            } else if rank_x > rank_y {
                self.parent.insert(root_y, root_x);
            } else {
                self.parent.insert(root_y, root_x);
                self.rank.insert(root_x, rank_x + 1);
            }
        }
    }
}

fn remove_stones(stones: Vec<Vec<i32>>) -> i32 {
    let mut uf = UnionFind::new();

    for stone in &stones {
        uf.union(stone[0], stone[1] + 10000);
    }

    let mut unique_roots = std::collections::HashSet::new();
    for stone in stones {
        unique_roots.insert(uf.find(stone[0]));
    }

    stones.len() as i32 - unique_roots.len() as i32
}

fn main() {
    println!("{}", remove_stones(vec![vec![0,0], vec![0,1], vec![1,0], vec![1,2], vec![2,1], vec![2,2]])); // Output: 5
    println!("{}", remove_stones(vec![vec![0,0], vec![0,2], vec![1,1], vec![2,0], vec![2,2]])); // Output: 3
    println!("{}", remove_stones(vec![vec![0,0]])); // Output: 0
}

Kotlin implementation

fun main() {
    class UnionFind {
        private val parent = mutableMapOf<Int, Int>()
        private val rank = mutableMapOf<Int, Int>()

        fun find(x: Int): Int {
            if (!parent.containsKey(x)) {
                parent[x] = x
                rank[x] = 0
            }
            if (parent[x] != x) {
                parent[x] = find(parent[x]!!)
            }
            return parent[x]!!
        }

        fun union(x: Int, y: Int) {
            val rootX = find(x)
            val rootY = find(y)
            if (rootX != rootY) {
                val rankX = rank[rootX]!!
                val rankY = rank[rootY]!!
                when {
                    rankX < rankY -> parent[rootX] = rootY
                    rankX > rankY -> parent[rootY] = rootX
                    else -> {
                        parent[rootY] = rootX
                        rank[rootX] = rankX + 1
                    }
                }
            }
        }
    }

    fun removeStones(stones: Array<IntArray>): Int {
        val uf = UnionFind()
        for (stone in stones) {
            uf.union(stone[0], stone[1] + 10000)
        }
        val uniqueRoots = stones.map { uf.find(it[0]) }.toSet()
        return stones.size - uniqueRoots.size
    }

    val stones1 = arrayOf(intArrayOf(0,0), intArrayOf(0,1), intArrayOf(1,0), intArrayOf(1,2), intArrayOf(2,1), intArrayOf(2,2))
    println(removeStones(stones1)) // Output: 5

    val stones2 = arrayOf(intArrayOf(0,0), intArrayOf(0,2), intArrayOf(1,1), intArrayOf(2,0), intArrayOf(2,2))
    println(removeStones(stones2)) // Output: 3

    val stones3 = arrayOf(intArrayOf(0,0))
    println(removeStones(stones3)) // Output: 0
}

Swift implementation

import Foundation

class UnionFind {
    var parent = [Int: Int]()
    var rank = [Int: Int]()

    func find(_ x: Int) -> Int {
        if parent[x] == nil {
            parent[x] = x
            rank[x] = 0
        }
        if parent[x]! != x {
            parent[x] = find(parent[x]!)
        }
        return parent[x]!
    }

    func union(_ x: Int, _ y: Int) {
        let rootX = find(x)
        let rootY = find(y)
        if rootX != rootY {
            let rankX = rank[rootX] ?? 0
            let rankY = rank[rootY] ?? 0
            if rankX < rankY {
                parent[rootX] = rootY
            } else if rankX > rankY {
                parent[rootY] = rootX
            } else {
                parent[rootY] = rootX
                rank[rootX] = rankX + 1
            }
        }
    }
}

func removeStones(_ stones: [[Int]]) -> Int {
    let uf = UnionFind()
    for stone in stones {
        uf.union(stone[0], stone[1] + 10000)
    }

    var uniqueRoots = Set<Int>()
    for stone in stones {
        uniqueRoots.insert(uf.find(stone[0]))
    }

    return stones.count - uniqueRoots.count
}

// Test
print(removeStones([[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]])) // Output: 5
print(removeStones([[0,0],[0,2],[1,1],[2,0],[2,2]])) // Output: 3
print(removeStones([[0,0]])) // Output: 0

TypeScript implementation

class UnionFind {
  private parent: Map<number, number> = new Map();
  private rank: Map<number, number> = new Map();

  find(x: number): number {
    if (!this.parent.has(x)) {
      this.parent.set(x, x);
      this.rank.set(x, 0);
    }
    if (this.parent.get(x)! !== x) {
      this.parent.set(x, this.find(this.parent.get(x)!));
    }
    return this.parent.get(x)!;
  }

  union(x: number, y: number): void {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX !== rootY) {
      const rankX = this.rank.get(rootX)!;
      const rankY = this.rank.get(rootY)!;
      if (rankX < rankY) {
        this.parent.set(rootX, rootY);
      } else if (rankX > rankY) {
        this.parent.set(rootY, rootX);
      } else {
        this.parent.set(rootY, rootX);
        this.rank.set(rootX, rankX + 1);
      }
    }
  }
}

function removeStones(stones: number[][]): number {
  const uf = new UnionFind();
  for (const stone of stones) {
    uf.union(stone[0], stone[1] + 10000);
  }

  const uniqueRoots = new Set<number>();
  for (const stone of stones) {
    uniqueRoots.add(uf.find(stone[0]));
  }

  return stones.length - uniqueRoots.size;
}

// Test
console.log(removeStones([[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]])); // Output: 5
console.log(removeStones([[0,0],[0,2],[1,1],[2,0],[2,2]])); // Output: 3
console.log(removeStones([[0,0]])); // Output: 0