Most Stones Removed with Same Row or Column - Visualization

Graphs

Contents

ProblemExamplesSolutionAlgorithmCode

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❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...