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❯

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.

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

Comments

Loading comments...