Most Stones Removed with Same Row or Column
MedPrompt
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] = [xi, yi] represents the location of the ith stone, return the largest possible number of stones that can be removed.
Example 1:
Input: stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5
Explanation: One way to remove 5 stones is as follows:
1. Remove stone [2,2] because it shares the same row as [2,1].
2. Remove stone [2,1] because it shares the same column as [0,1].
3. Remove stone [1,2] because it shares the same row as [1,0].
4. Remove stone [1,0] because it shares the same column as [0,0].
5. Remove stone [0,1] because it shares the same row as [0,0].
Stone [0,0] cannot be removed since it does not share a row/column with another stone still on the plane.Example 2:
Input: stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3
Explanation: One way to make 3 moves is as follows:
1. Remove stone [2,2] because it shares the same row as [2,0].
2. Remove stone [2,0] because it shares the same column as [0,0].
3. Remove stone [0,2] because it shares the same row as [0,0].
Stones [0,0] and [1,1] cannot be removed since they do not share a row/column with another stone still on the plane.Example 3:
Input: stones = [[0,0]]
Output: 0
Explanation: [0,0] is the only stone on the plane, so you cannot remove it.
Constraints:
1 <= stones.length <= 10000 <= xi, yi <= 104- No two stones are at the same coordinate point.
Approaches
3 approaches with complexity analysis and trade-offs.
This approach models the problem as a graph problem. Each stone is a vertex, and an edge exists between two stones if they share the same row or column. The problem then becomes finding the number of connected components in this graph. For each component of size k, we can remove k-1 stones. Thus, the total number of removable stones is N - C, where N is the total number of stones and C is the number of connected components. We can build an explicit adjacency list for the graph and then use Depth-First Search (DFS) to count the components.
Algorithm
- Create an adjacency list
adjfornstones. - Iterate through all pairs of stones
(i, j). - If
stones[i]andstones[j]share a row or column, add an edge betweeniandjinadj. - Initialize a
visitedarray of sizentofalse. - Initialize
components = 0. - Iterate from
i = 0ton-1:- If
visited[i]isfalse:- Increment
components. - Call a DFS function starting from
ito mark all nodes in the component as visited.
- Increment
- If
- Return
n - components.
Walkthrough
Graph Construction
We first build an adjacency list representation of the graph. We iterate through every pair of stones. If two stones stones[i] and stones[j] have the same x-coordinate or the same y-coordinate, we add an edge between vertex i and vertex j. This takes O(N^2) time.
Counting Components with DFS
We use a visited array to keep track of visited stones (vertices). We iterate through all stones from 0 to N-1. If a stone i has not been visited, it means we've found a new connected component. We increment our component counter and start a DFS traversal from stone i. The DFS function will recursively visit all neighbors of the current stone, marking them as visited. This ensures that all stones in the same component are visited together.
Final Calculation
After iterating through all stones, the component counter will hold the total number of connected components, C. The maximum number of stones that can be removed is N - C.
import java.util.*; class Solution { public int removeStones(int[][] stones) { int n = stones.length; List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) { adj.add(new ArrayList<>()); } // Build adjacency list - O(N^2) for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) { adj.get(i).add(j); adj.get(j).add(i); } } } boolean[] visited = new boolean[n]; int components = 0; // Count connected components using DFS - O(N+E) which is O(N^2) for (int i = 0; i < n; i++) { if (!visited[i]) { dfs(i, adj, visited); components++; } } return n - components; } private void dfs(int u, List<List<Integer>> adj, boolean[] visited) { visited[u] = true; for (int v : adj.get(u)) { if (!visited[v]) { dfs(v, adj, visited); } } }}Complexity
Time
`O(N^2)`. Building the adjacency list requires checking `N*(N-1)/2` pairs, which is `O(N^2)`. The DFS traversal takes `O(V+E) = O(N+E)`. In the worst case, the number of edges `E` can be `O(N^2)`, making the total time complexity dominated by `O(N^2)`.
Space
`O(N^2)`. The adjacency list can store up to `O(N^2)` edges in a dense graph. The `visited` array and recursion stack for DFS take `O(N)` space.
Trade-offs
Pros
Conceptually straightforward, directly translating the problem into a standard graph traversal problem.
Cons
High time complexity of
O(N^2)due to building the graph by checking all pairs.High space complexity of
O(N^2)in the worst case for the adjacency list if the graph is dense.
This approach also identifies connected components but uses a more space-efficient data structure, the Disjoint Set Union (DSU) or Union-Find. Each stone is an element in a set. We iterate through all pairs of stones and if they are connected (share a row or column), we union their sets. The number of connected components is the final number of disjoint sets. The result is N - (number of components).
Algorithm
- Initialize a DSU structure for
nelements, with each element in its own set. The number of components isn. - Iterate through all pairs of stones
(i, j). - If
stones[i]andstones[j]share a row or column, performunion(i, j). Theunionoperation will merge the sets if they are different and decrement the component count. - Return
n - (final component count).
Walkthrough
DSU Data Structure
We implement a DSU data structure with two main operations: find (to find the representative/root of the set an element belongs to) and union (to merge two sets). Path compression and union by size/rank optimizations are used to make these operations nearly constant time.
Algorithm
Initialize a DSU structure for N stones. Each stone i is its own parent, so we start with N components. Iterate through all pairs of stones (i, j). If stones[i] and stones[j] share a row or column, we check if they are already in the same set using find(i) != find(j). If they are in different sets, we merge them using union(i, j) and decrement the component count.
Final Calculation
The final count of components is used to calculate the result: N - components.
class Solution { class DSU { int[] parent; int components; DSU(int n) { parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } components = n; } int find(int i) { if (parent[i] == i) { return i; } return parent[i] = find(parent[i]); // Path compression } void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { parent[rootI] = rootJ; components--; } } } public int removeStones(int[][] stones) { int n = stones.length; DSU dsu = new DSU(n); // O(N^2) loop to connect stones for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1]) { dsu.union(i, j); } } } return n - dsu.components; }}Complexity
Time
`O(N^2 * α(N))`, which is effectively `O(N^2)`. The dominant factor is the nested loop iterating through all pairs of stones. The `union` and `find` operations are nearly constant time, `O(α(N))`, where `α` is the inverse Ackermann function.
Space
`O(N)`. We need an array of size `N` for the DSU's parent pointers.
Trade-offs
Pros
More space-efficient than the explicit graph approach, using only
O(N)space.The DSU data structure is highly optimized for component-finding problems.
Cons
The time complexity is still
O(N^2)because of the nested loops to check every pair of stones for connectivity.
This is the most efficient approach. It avoids the O(N^2) pairwise comparison by using hash maps to quickly find stones that share a row or column. We iterate through the stones just once. For each stone, we check if we've already seen a stone in the same row or column. If so, we union the current stone with the previously seen stone. This reduces the time complexity to be nearly linear.
Algorithm
- Initialize a DSU structure for
nstones. - Initialize two hash maps,
rowMapandcolMap. - Iterate through the stones from
i = 0ton-1:- Let the stone's coordinates be
(r, c). - If
ris inrowMap,union(i, rowMap.get(r)). Otherwise,rowMap.put(r, i). - If
cis incolMap,union(i, colMap.get(c)). Otherwise,colMap.put(c, i).
- Let the stone's coordinates be
- Return
n - (final component count).
Walkthrough
Core Idea
Instead of comparing every stone with every other stone, we can process stones one by one and connect them to a "representative" for their row and column. If we encounter a stone at (r, c), and we've already seen another stone in row r, we know these two stones are connected and should be in the same component. The same logic applies to column c.
Algorithm
Initialize a DSU structure for N stones. Create two hash maps: rowMap to map a row index to the index of a stone in that row, and colMap to map a column index to the index of a stone in that column. Iterate through each stone i from 0 to N-1 with coordinates (r, c). For the current stone's row r: if rowMap does not contain r, map r to the current stone's index i. If rowMap already contains r, it means we've seen a stone in this row before. We union the current stone i with the stone previously stored for this row, union(i, rowMap.get(r)). Do the same for the current stone's column c using colMap.
Final Calculation
After iterating through all stones, the number of components is tracked by the DSU structure. The result is N - (number of components).
import java.util.*; class Solution { class DSU { int[] parent; int components; DSU(int n) { parent = new int[n]; for (int i = 0; i < n; i++) { parent[i] = i; } components = n; } int find(int i) { if (parent[i] == i) { return i; } return parent[i] = find(parent[i]); } void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { parent[rootI] = rootJ; components--; } } } public int removeStones(int[][] stones) { int n = stones.length; DSU dsu = new DSU(n); Map<Integer, Integer> rowMap = new HashMap<>(); Map<Integer, Integer> colMap = new HashMap<>(); for (int i = 0; i < n; i++) { int r = stones[i][0]; int c = stones[i][1]; if (rowMap.containsKey(r)) { dsu.union(i, rowMap.get(r)); } else { rowMap.put(r, i); } if (colMap.containsKey(c)) { dsu.union(i, colMap.get(c)); } else { colMap.put(c, i); } } return n - dsu.components; }}Complexity
Time
`O(N * α(N))`. We iterate through `N` stones once. Inside the loop, hash map operations are `O(1)` on average, and DSU operations are `O(α(N))`.
Space
`O(N)`. The DSU structure requires `O(N)` space. The hash maps, in the worst case, can store up to `N` distinct rows and `N` distinct columns, leading to `O(N)` space.
Trade-offs
Pros
Highly efficient time complexity, close to linear.
Optimal space complexity, depending only on the number of stones
N.
Cons
Slightly more complex to conceptualize than the direct graph-building approaches.
Solutions
Solution
class Solution {private int[] p;public int removeStones(int[][] stones) { int n = 10010; p = new int[n << 1]; for (int i = 0; i < p.length; ++i) { p[i] = i; } for (int[] stone : stones) { p[find(stone[0])] = find(stone[1] + n); } Set<Integer> s = new HashSet<>(); for (int[] stone : stones) { s.add(find(stone[0])); } return stones.length - s.size(); }private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }}class Solution {public: vector<int> p; int removeStones(vector<vector<int>> &stones) { int n = 10010; p.resize(n << 1); for (int i = 0; i < p.size(); ++i) p[i] = i; for (auto &stone : stones) p[find(stone[0])] = find(stone[1] + n); unordered_set<int> s; for (auto &stone : stones) s.insert(find(stone[0])); return stones.size() - s.size(); } int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }};class Solution: def removeStones(self, stones: List[List[int]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] n = 10010 p = list(range(n << 1)) for x, y in stones: p[find(x)] = find(y + n) s = {find(x) for x, _ in stones} return len(stones) - len(s)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.