Most Stones Removed with Same Row or Column Using DSU

73.5k
0

Given N stones at distinct integer coordinates [row,col], a stone can be removed after sharing a row or column with another remaining stone.

Return the maximum number of removable stones. Removal order may vary, but every connected group formed through shared rows or columns must retain at least one stone.

Example 1

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

Output: 5

Explanation: All six stones belong to one connected component, so five stones can be removed while one stone remains.

Example 2

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

Output: 3

Explanation: Four corner stones form one component, while stone [1,1] forms an isolated component. Three stones can be removed.

Brute Force Approach

Treat every stone as a graph node. Two stones are connected after sharing a row or column, including indirect chains through other stones. For each unvisited starting stone, an explicit stack explores the complete connected component.

A component containing K stones permits exactly K-1 removals because one final stone must remain. Summing across components gives N-components. Direct neighbor discovery scans all stones from every visited stone, producing quadratic time.

Algorithm

  • Initialize a visited array and a component counter because each connected component will leave one stone that cannot be removed.

  • Traverse every stone as a possible starting point for an unvisited component.

  • Start a stack traversal whenever an unvisited stone is found and increment the component count.

  • For each popped stone, scan all other stones to find those sharing the same row or column.

  • Visit every connected stone because sharing a row or column creates a direct connection, while repeated traversal captures indirect connections.

  • Continue the traversal until every stone in the current component has been visited.

  • A component containing K stones allows K - 1 removals, so across all components the answer is N - components.

  • Return the total number of stones minus the number of connected components.

Dry Run

most-stones-removed-brute-force-dry-run

most-stones-removed-brute-force-dry-run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the maximum number of stones that can be removed.
int removeStones(vector<vector<int>>& stones) {
int n = stones.size();
vector<int> visited(n, 0);
int components = 0;
// Each unvisited stone starts a new connected component.
for (int start = 0; start < n; start++) {
// This stone is already part of an earlier component.
if (visited[start]) {
continue;
}
components++;
stack<int> pending;
pending.push(start);
visited[start] = 1;
// DFS collects all stones connected by shared rows or columns.
while (!pending.empty()) {
int current = pending.top();
pending.pop();
// Compare the current stone with every other stone.
for (int candidate = 0; candidate < n; candidate++) {
bool sharesRow = stones[current][0] == stones[candidate][0];
bool sharesColumn = stones[current][1] == stones[candidate][1];
// An unseen stone sharing a row or column belongs to this component.
if (!visited[candidate] && (sharesRow || sharesColumn)) {
visited[candidate] = 1;
pending.push(candidate);
}
}
}
}
// One stone must remain in each connected component.
return n - components;
}
};
// Driver code
int main() {
vector<vector<int>> stones = {
{0, 0}, {0, 1}, {1, 0},
{1, 2}, {2, 1}, {2, 2}
};
// instance for class Solution
Solution sol;
cout << sol.removeStones(stones);
return 0;
}

Complexity Analysis

Time Complexity: O(N×N), every visited stone scans all N candidates.

Space Complexity: O(N), visited storage and the explicit traversal stack contain stone indices.

Optimal Approach: Row-Column Disjoint Set Union

Model every row and every column as separate DSU nodes. A stone at [row,col] becomes an edge joining row node row with shifted column node maxRow+1+col. The offset prevents row-column ID collisions.

All coordinate nodes connected through stones collapse into one representative per stone component. Count roots only among row and column nodes used by at least one stone. Subtracting the component count from N gives the maximum removals. Let R=maxRow+1 and C=maxCol+1.

Algorithm

  • Find the maximum row and column coordinates to determine the required DSU node range.

  • Set the column offset to maxRow + 1 so row and column nodes always have different IDs.

  • Initialize the DSU parent and size arrays for all row and shifted column nodes.

  • Convert each stone [row, col] into an edge between row node row and column node offset + col.

  • Merge the corresponding row and column nodes using union by size because each stone connects its row and column.

  • Record every row and column node that appears in at least one stone so unused DSU nodes do not affect the component count.

  • Use path compression during representative searches to keep DSU operations efficient.

  • Count distinct DSU representatives among the used coordinate nodes to determine the number of connected stone components.

  • Return number of stones - number of components, because each component can remove all but one stone.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<int> parent;
vector<int> componentSize;
// Returns the representative of the current set.
int findParent(int node) {
// This node is already the representative of its set.
if (parent[node] == node) {
return node;
}
// Path compression connects this node directly to its representative.
return parent[node] = findParent(parent[node]);
}
// Merges two sets when they belong to different components.
void unite(int first, int second) {
int firstRoot = findParent(first);
int secondRoot = findParent(second);
// Both nodes already belong to the same component.
if (firstRoot == secondRoot) {
return;
}
// The smaller component should attach under the larger component.
if (componentSize[firstRoot] < componentSize[secondRoot]) {
swap(firstRoot, secondRoot);
}
parent[secondRoot] = firstRoot;
componentSize[firstRoot] += componentSize[secondRoot];
}
public:
// Returns the maximum number of stones that can be removed.
int removeStones(vector<vector<int>>& stones) {
int stoneCount = stones.size();
int maxRow = 0;
int maxCol = 0;
// Find the largest row and column needed for coordinate nodes.
for (const vector<int>& stone : stones) {
maxRow = max(maxRow, stone[0]);
maxCol = max(maxCol, stone[1]);
}
int columnOffset = maxRow + 1;
int totalNodes = columnOffset + maxCol + 1;
parent.resize(totalNodes);
componentSize.assign(totalNodes, 1);
iota(parent.begin(), parent.end(), 0);
unordered_set<int> usedNodes;
// Each stone connects one row node with one shifted column node.
for (const vector<int>& stone : stones) {
int rowNode = stone[0];
int colNode = columnOffset + stone[1];
unite(rowNode, colNode);
usedNodes.insert(rowNode);
usedNodes.insert(colNode);
}
int components = 0;
// Count only the DSU components that contain at least one stone.
for (int node : usedNodes) {
// This used node is the representative of one active component.
if (findParent(node) == node) {
components++;
}
}
// One stone must remain in each connected component.
return stoneCount - components;
}
};
// Driver code
int main() {
vector<vector<int>> stones = {
{0, 0}, {0, 1}, {1, 0},
{1, 2}, {2, 1}, {2, 2}
};
// instance for class Solution
Solution sol;
cout << sol.removeStones(stones);
return 0;
}

Complexity Analysis

Time Complexity: Let N be the number of stones, R be maxRow + 1, and C be maxCol + 1. Finding the coordinate range and processing the stones takes O(N), DSU initialization takes O(R + C), and each union/find operation takes amortized O(α(R + C)) time. Here, α is the inverse Ackermann function, which grows extremely slowly and behaves almost like a constant in practice. Therefore, the total time complexity is O((R + C) + N × α(R + C)).

Space Complexity: The DSU parent and component-size arrays store R + C row and column nodes. The used-node set stores only coordinate nodes that appear in stones, which is bounded by O(R + C), so the total auxiliary space is O(R + C).

Interview follow-up Questions

The final stone has no second remaining stone inside the same component for satisfying the removal rule.

Graph

Read Similar Blogs

Graph

Find the City with the Smallest Number of Neighbors at a Threshold Distance

Given N cities numbered from 0 to N-1 , an array of bidirectional weighted roads [first, second, weight] , and a positive distanceThreshold , count the other cities reachable from every city with s...

105.7k
Graph

Dijkstra’s Algorithm

Input: V = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]], source = 0 Output: [0,3,1,4,7] Explanation: Minimum routes from source are 0 , 0->2->1 , 0->2 , 0->2->1->3 , and 0->2->1->3-...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weig...

96.1k
Comments0