Most Stones Removed with Same Row or Column (Graph-Based)

Problem Statement❯

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.

Examples❯

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.

Solution❯

This problem can be visualized as a graph traversal problem. Treat each stone as a node. Draw an edge between two stones if they share a row or column. The result is a graph where each connected component represents stones that are directly or indirectly connected via rows/columns.

Within each connected component, we can remove all stones except one. So, the maximum number of removable stones is: total stones - number of connected components.

To solve this, we build a graph where each node is connected to others that share its row or column. We then perform a Depth-First Search (DFS) to count the number of connected components.

Algorithm Steps❯

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

Code

JavaScript

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

⬅ Previous TopicMinimum Operations to Make Network Connected

Next Topic ⮕Accounts Merge Problem using Disjoint Set Union