Most Stones Removed with Same Row or Column

Most Stones Removed with Same Row or Column - Problem

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 where stones[i] = [x_i, y_i] represents the location of the i-th stone, return the largest possible number of stones that can be removed.

Input & Output

Example 1 — Connected Stones

$ Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]

› Output: 5

💡 Note: We can remove stones at [0,1], [1,0], [1,2], [2,1], [2,2] because they each share a row or column with at least one other stone. The stone at [0,0] would be the last one remaining.

Example 2 — Two Groups

$ Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]

› Output: 3

💡 Note: Stones form two connected components: {[0,0],[2,0]} share column 0, and {[0,2],[2,2]} share column 2, while [1,1] is isolated. We can remove 3 stones total.

Example 3 — Single Stone

$ Input: stones = [[0,0]]

› Output: 0

💡 Note: Cannot remove the only stone since it doesn't share a row or column with any other stone.

Constraints

1 ≤ stones.length ≤ 1000
0 ≤ x_i, y_i ≤ 10⁴
No two stones are at the same coordinate point

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Stones placed at coordinate points

Find Connections

Identify stones sharing rows/columns

Count Removable

Total stones minus connected components

Key Takeaway

🎯 Key Insight: Stones sharing rows or columns form connected components - keep one stone per component, remove the rest

Asked in

G Google 45 f Facebook 32 a Amazon 28 M Microsoft 22

The key insight is that stones sharing the same row or column form connected components. From each component, we can remove all stones except one. Best approach is Union-Find to efficiently group stones by coordinates. Time: O(n × α(n)), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n³)	O(n)	Simulate the removal process by repeatedly finding removable stones
DFS Connected Components	O(n²)	O(n²)	Build a graph where stones sharing rows/columns are connected, then find connected components
Union-Find (Disjoint Set)	O(n × α(n))	O(n)	Use Union-Find to efficiently group stones that share coordinates

Brute Force Simulation — Algorithm Steps

Step 1: Mark all stones as existing
Step 2: Find a stone that shares row/column with another
Step 3: Remove it and increment counter
Step 4: Repeat until no removable stones left

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

All stones present on the grid

Find Removable

Search for stones sharing rows/columns

Remove & Repeat

Remove one stone and search again

Code -

solution.c — C

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

int solution(int stones[][2], int n) {
    bool* removed = (bool*)calloc(n, sizeof(bool));
    int count = 0;
    
    while (true) {
        bool found = false;
        for (int i = 0; i < n; i++) {
            if (removed[i]) continue;
            // Check if this stone shares row/column with another existing stone
            bool canRemove = false;
            for (int j = 0; j < n; j++) {
                if (i != j && !removed[j]) {
                    if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) {
                        canRemove = true;
                        break;
                    }
                }
            }
            if (canRemove) {
                removed[i] = true;
                count++;
                found = true;
                break;
            }
        }
        if (!found) break;
    }
    
    free(removed);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[x1,y1],[x2,y2],...]
    int stones[1000][2];
    int n = 0;
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            stones[n][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            stones[n][1] = atoi(ptr);
            while (*ptr != ']') ptr++;
            n++;
        }
        ptr++;
    }
    
    printf("%d\n", solution(stones, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n stones to remove, we scan all remaining stones twice

⚠ Quadratic Growth

Space Complexity

O(n)

Boolean array to track which stones still exist

⚡ Linearithmic Space

89.6K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler