Most Stones Removed with Same Row or Column

Medium Graphs Connected Components Original on LeetCode

Reported atPhonePeMedia.net

Most Stones Removed with Same Row or Column is a medium graphs problem solved with the connected components pattern. The best approach, optimal (union-find on rows and columns), runs in O(n · α(n)) time and O(R + C) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs on the stone graph up.

Problem

Stones sit at distinct integer points on a 2D grid; stones[i] = [x_i, y_i] is the position of the i-th stone.

You may remove a stone if another stone that is still on the grid shares its row (same x) or its column (same y). Removals happen one at a time. Return the largest number of stones you can remove.

Examples

Example 1

Input
stones = [[0, 0], [0, 3], [2, 3], [4, 1], [4, 4]]
Output
3
Why
Stones (0,0), (0,3), (2,3) are linked through row 0 and column 3, so two of them can go; (4,1) and (4,4) share row 4, so one of them can go.

Example 2

Input
stones = [[1, 1], [2, 2], [3, 3]]
Output
0
Why
No two stones share a row or a column, so nothing can be removed.

Example 3

Input
stones = [[5, 2]]
Output
0
Why
A lone stone can never be removed.

Constraints

  • 1 <= stones.length <= 1000
  • 0 <= x_i, y_i <= 10^4
  • No two stones are at the same coordinate.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 15 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
DFS on the stone graphO(n²)O(n)
Optimal (union-find on rows and columns)O(n · α(n))O(R + C)

1DFS on the stone graph

TimeO(n²)Every stone visited checks all n stones for a shared row or column.
SpaceO(n)The visited array and the DFS stack.

Treat each stone as a node and connect two stones that share a row or a column. Count connected components with DFS; each component keeps one stone, so the answer is n minus the component count.

  1. Mark all stones unvisited; components = 0.
  2. For each unvisited stone: components++, then DFS, visiting every unvisited stone with the same row or column.
  3. Return n - components.
class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        boolean[] seen = new boolean[n];
        int components = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            components++;
            seen[s] = true;
            stack.push(s);
            while (!stack.isEmpty()) {
                int i = stack.pop();
                for (int j = 0; j < n; j++) {
                    if (!seen[j] && (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])) {
                        seen[j] = true;
                        stack.push(j);
                    }
                }
            }
        }
        return n - components;
    }
}

2Optimal (union-find on rows and columns)

TimeO(n · α(n))One union per stone with path compression and union by size.
SpaceO(R + C)Parent array over all possible row and column ids (about 2 · 10^4).

Make every row value and every column value a node (columns shifted by 10001 so they never clash with rows). Each stone unions its row with its column. Stones in the same component are exactly the stones whose rows/columns are linked, so the number of components among the used row/column nodes is the number of stone groups.

  1. For each stone, union(x, y + 10001); count a node as new the first time it appears.
  2. Every successful union of two different roots merges two groups: groups--.
  3. Return n - groups.
class Solution {
    private int[] parent = new int[20002];
    private int[] size = new int[20002];
    private int groups = 0;

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private void add(int x) {
        if (size[x] == 0) {
            parent[x] = x;
            size[x] = 1;
            groups++;
        }
    }

    public int removeStones(int[][] stones) {
        for (int[] s : stones) {
            int r = s[0], c = s[1] + 10001;
            add(r);
            add(c);
            int a = find(r), b = find(c);
            if (a != b) {
                if (size[a] < size[b]) { int t = a; a = b; b = t; }
                parent[b] = a;
                size[a] += size[b];
                groups--;
            }
        }
        return stones.length - groups;
    }
}

Edge cases to test

  • A single stone
  • All stones in one row or one column
  • Stones linked only through a chain (row, then column, then row...)
  • Many isolated stones

Hints

Hint 1

Join two stones with an edge when they share a row or column. What can you remove inside one connected group?

Hint 2

Inside a connected group you can always remove stones in an order that leaves exactly one behind (remove leaves of a spanning tree first).

Hint 3

So the answer is the number of stones minus the number of connected groups. Union-find over row ids and column ids counts the groups without building the edges.

FAQ

What is the best time complexity for Most Stones Removed with Same Row or Column?

Optimal (union-find on rows and columns) runs in O(n · α(n)) time and O(R + C) extra space. One union per stone with path compression and union by size.

Which pattern does Most Stones Removed with Same Row or Column use?

It is a graphs problem that uses the connected components pattern. Other problems with the same pattern: Number of Provinces, Number of Islands, Evaluate Division.

Is there a brute force solution for Most Stones Removed with Same Row or Column?

Yes. DFS on the stone graph takes O(n²) time and O(n) space. Treat each stone as a node and connect two stones that share a row or a column.

Which edge cases should I test for Most Stones Removed with Same Row or Column?

A single stone; All stones in one row or one column; Stones linked only through a chain (row, then column, then row...); Many isolated stones.