Most Stones Removed with Same Row or Column

🎯

Most Stones Removed with Same Row or Column

mediumGRAPHAmazonGoogleFacebook

Imagine a game where you have piles of stones placed on a grid, and you want to remove as many stones as possible by only removing stones that share a row or column with another stone.

💡 This problem is about grouping stones that share rows or columns and removing as many as possible. Beginners often struggle because it looks like a graph problem but requires a union-find data structure to efficiently group stones by rows and columns.

📋

Problem Statement

You are given an array stones where stones[i] = [x_i, y_i] represents the location of the i-th stone on a 2D plane. A stone can be removed if it shares either the same row or the same column as another stone that has not been removed. Return the largest possible number of stones that can be removed.

1 ≤ stones.length ≤ 10^50 ≤ x_i, y_i ≤ 10^4

💡

Example

Input"[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]"

Output5

One way to remove 5 stones is to remove stones in the order: [2,2], [2,1], [1,2], [1,0], [0,1]. The stone at [0,0] remains.

• Only one stone → 0 stones can be removed
• All stones in the same row → n-1 stones can be removed
• All stones in the same column → n-1 stones can be removed
• Stones placed such that no two stones share a row or column → 0 stones can be removed

⚠️

Common Mistakes

Not offsetting columns when unioning rows and columns

Rows and columns collide in union-find causing incorrect unions

✅ Add a large offset to column indices to separate them from rows

Forgetting to count unique parents after unions

Incorrect calculation of connected components leads to wrong answer

✅ Track count of unique parents or sets in union-find

Using brute force graph approach for large inputs

Solution times out due to O(n^2) complexity

✅ Use union-find to optimize to near O(n)

Not implementing path compression or union by rank

Union-find operations become slower on large inputs

✅ Add path compression and union by rank optimizations

Not handling edge cases like single stone or isolated stones

Incorrect output or misunderstanding problem constraints

✅ Test and handle edge cases explicitly

🧠

Brute Force (Graph DFS to find connected components)

💡 This approach exists to build intuition by modeling the problem as a graph and finding connected components using DFS. It is straightforward but inefficient for large inputs.

Intuition

Model stones as nodes in a graph where edges connect stones sharing a row or column. Then, count connected components. The answer is total stones minus number of connected components.

Algorithm

1. Build a graph where each stone is a node.
2. Connect stones with an edge if they share the same row or column.
3. Use DFS to find connected components in the graph.
4. Return total stones minus number of connected components.

💡 The challenge is building the graph efficiently and understanding that connected components represent groups of stones that can be reduced to one stone.

</>

Code

from collections import defaultdict

def removeStones(stones):
    graph = defaultdict(list)
    n = len(stones)
    for i in range(n):
        for j in range(i+1, n):
            if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]:
                graph[i].append(j)
                graph[j].append(i)

    visited = set()
    def dfs(node):
        visited.add(node)
        for nei in graph[node]:
            if nei not in visited:
                dfs(nei)

    components = 0
    for i in range(n):
        if i not in visited:
            dfs(i)
            components += 1
    return n - components

# Driver code
if __name__ == '__main__':
    stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
    print(removeStones(stones))  # Output: 5

Line Notes

graph = defaultdict(list)Initialize adjacency list to represent graph connections

for i in range(n):Outer loop to consider each stone

if stones[i][0] == stones[j][0] or stones[i][1] == stones[j][1]Check if stones share row or column to connect them

visited = set()Track visited nodes to avoid revisiting

def dfs(node):Define DFS to explore connected component

components += 1Increment count for each connected component found

return n - componentsMaximum stones removed is total stones minus connected components

import java.util.*;

public class Solution {
    public int removeStones(int[][] stones) {
        int n = stones.length;
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        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]) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }
            }
        }
        boolean[] visited = new boolean[n];
        int components = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited);
                components++;
            }
        }
        return n - components;
    }

    private void dfs(int node, Map<Integer, List<Integer>> graph, boolean[] visited) {
        visited[node] = true;
        for (int nei : graph.get(node)) {
            if (!visited[nei]) {
                dfs(nei, graph, visited);
            }
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] stones = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
        System.out.println(sol.removeStones(stones)); // Output: 5
    }
}

Line Notes

Map<Integer, List<Integer>> graph = new HashMap<>()Create adjacency list for graph

for (int i = 0; i < n; i++)Initialize graph nodes

if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])Connect stones sharing row or column

boolean[] visited = new boolean[n]Track visited stones

if (!visited[i])Start DFS for unvisited node

visited[node] = trueMark node as visited

return n - componentsCalculate max stones removed

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
        visited[node] = true;
        for (int nei : graph[node]) {
            if (!visited[nei]) {
                dfs(nei, graph, visited);
            }
        }
    }

    int removeStones(vector<vector<int>>& stones) {
        int n = stones.size();
        vector<vector<int>> graph(n);
        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]) {
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
        }
        vector<bool> visited(n, false);
        int components = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited);
                components++;
            }
        }
        return n - components;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> stones = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
    cout << sol.removeStones(stones) << endl; // Output: 5
    return 0;
}

Line Notes

vector<vector<int>> graph(n)Adjacency list for graph representation

for (int i = 0; i < n; i++)Outer loop to build graph edges

if (stones[i][0] == stones[j][0] || stones[i][1] == stones[j][1])Connect stones sharing row or column

vector<bool> visited(n, false)Track visited nodes

if (!visited[i])Start DFS from unvisited node

visited[node] = trueMark node visited to avoid cycles

return n - componentsCalculate max stones removed

function removeStones(stones) {
    const n = stones.length;
    const graph = new Map();
    for (let i = 0; i < n; i++) {
        graph.set(i, []);
    }
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1]) {
                graph.get(i).push(j);
                graph.get(j).push(i);
            }
        }
    }
    const visited = new Set();
    function dfs(node) {
        visited.add(node);
        for (const nei of graph.get(node)) {
            if (!visited.has(nei)) dfs(nei);
        }
    }
    let components = 0;
    for (let i = 0; i < n; i++) {
        if (!visited.has(i)) {
            dfs(i);
            components++;
        }
    }
    return n - components;
}

// Driver code
const stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]];
console.log(removeStones(stones)); // Output: 5

Line Notes

const graph = new Map()Create adjacency list using Map

for (let i = 0; i < n; i++)Initialize graph nodes

if (stones[i][0] === stones[j][0] || stones[i][1] === stones[j][1])Connect stones sharing row or column

const visited = new Set()Track visited stones

function dfs(node)DFS to explore connected component

components++Count connected components

return n - componentsCalculate max stones removed

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

We check every pair of stones to build the graph, which takes O(n^2). DFS visits all nodes and edges, also O(n^2) in worst case.

💡 For n=1000 stones, this means about 1,000,000 comparisons, which is too slow for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem structure and connected components.

🧠

Union-Find (Disjoint Set Union) by connecting stones sharing rows or columns

💡 This approach uses union-find to efficiently group stones by rows and columns, avoiding the O(n^2) graph construction. It introduces a key optimization by mapping rows and columns to nodes.

Intuition

Treat rows and columns as nodes in a union-find structure. Union stones by their row and column indices. The number of connected components is the number of unique parents in union-find.

Algorithm

1. Initialize union-find structure for rows and columns (offset columns to avoid collision).
2. For each stone, union its row and column nodes.
3. Count unique parents representing connected components.
4. Return total stones minus number of connected components.

💡 The tricky part is mapping columns to a different index space to avoid overlap with rows and counting unique parents correctly.

</>

Code

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.count = 0

    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.count += 1
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootX] = rootY
            self.count -= 1


def removeStones(stones):
    uf = UnionFind()
    OFFSET = 10000  # offset columns to avoid collision with rows
    for x, y in stones:
        uf.union(x, y + OFFSET)
    return len(stones) - uf.count

# Driver code
if __name__ == '__main__':
    stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
    print(removeStones(stones))  # Output: 5

Line Notes

self.parent = {}Initialize parent dictionary for union-find

if x not in self.parentAdd new node with itself as parent

self.count += 1Track number of distinct sets

if self.parent[x] != xPath compression to flatten tree

if rootX != rootYUnion two sets if roots differ

self.count -= 1Decrease count when two sets merge

uf.union(x, y + OFFSET)Union row and column with offset to avoid collision

return len(stones) - uf.countMax stones removed is total stones minus connected components

import java.util.*;

class UnionFind {
    private Map<Integer, Integer> parent = new HashMap<>();
    private int count = 0;

    public int find(int x) {
        if (!parent.containsKey(x)) {
            parent.put(x, x);
            count++;
        }
        if (parent.get(x) != x) {
            parent.put(x, find(parent.get(x)));
        }
        return parent.get(x);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent.put(rootX, rootY);
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}

public class Solution {
    public int removeStones(int[][] stones) {
        UnionFind uf = new UnionFind();
        int OFFSET = 10000;
        for (int[] stone : stones) {
            uf.union(stone[0], stone[1] + OFFSET);
        }
        return stones.length - uf.getCount();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] stones = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
        System.out.println(sol.removeStones(stones)); // Output: 5
    }
}

Line Notes

private Map<Integer, Integer> parent = new HashMap<>()Parent map for union-find nodes

if (!parent.containsKey(x))Add new node if not present

parent.put(x, find(parent.get(x)))Path compression to optimize find

if (rootX != rootY)Union sets if roots differ

count--Decrease count when sets merge

uf.union(stone[0], stone[1] + OFFSET)Union row and column with offset

return stones.length - uf.getCount()Calculate max stones removed

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class UnionFind {
    unordered_map<int, int> parent;
    int count = 0;
public:
    int find(int x) {
        if (parent.find(x) == parent.end()) {
            parent[x] = x;
            count++;
        }
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
            count--;
        }
    }

    int getCount() {
        return count;
    }
};

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        UnionFind uf;
        const int OFFSET = 10000;
        for (auto& stone : stones) {
            uf.unite(stone[0], stone[1] + OFFSET);
        }
        return stones.size() - uf.getCount();
    }
};

int main() {
    Solution sol;
    vector<vector<int>> stones = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
    cout << sol.removeStones(stones) << endl; // Output: 5
    return 0;
}

Line Notes

unordered_map<int, int> parentParent map for union-find nodes

if (parent.find(x) == parent.end())Add new node if not present

parent[x] = find(parent[x])Path compression optimization

if (rootX != rootY)Union sets if roots differ

count--Decrease count when sets merge

uf.unite(stone[0], stone[1] + OFFSET)Union row and column with offset

return stones.size() - uf.getCount()Calculate max stones removed

class UnionFind {
    constructor() {
        this.parent = new Map();
        this.count = 0;
    }

    find(x) {
        if (!this.parent.has(x)) {
            this.parent.set(x, x);
            this.count++;
        }
        if (this.parent.get(x) !== x) {
            this.parent.set(x, this.find(this.parent.get(x)));
        }
        return this.parent.get(x);
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            this.parent.set(rootX, rootY);
            this.count--;
        }
    }
}

function removeStones(stones) {
    const uf = new UnionFind();
    const OFFSET = 10000;
    for (const [x, y] of stones) {
        uf.union(x, y + OFFSET);
    }
    return stones.length - uf.count;
}

// Driver code
const stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]];
console.log(removeStones(stones)); // Output: 5

Line Notes

this.parent = new Map()Parent map for union-find nodes

if (!this.parent.has(x))Add new node if not present

this.parent.set(x, this.find(this.parent.get(x)))Path compression optimization

if (rootX !== rootY)Union sets if roots differ

this.count--Decrease count when sets merge

uf.union(x, y + OFFSET)Union row and column with offset

return stones.length - uf.countCalculate max stones removed

⏱

Complexity

TimeO(n α(n))

SpaceO(n)

Union-find operations are almost O(1) amortized (α is inverse Ackermann function). We do union for each stone once.

💡 For n=100000 stones, this approach is efficient and practical, unlike the brute force.

Interview Verdict: Accepted / Optimal for large inputs

This is the preferred approach in interviews due to efficiency and elegance.

🧠

Union-Find with Path Compression and Union by Rank Optimization

💡 This approach improves the previous union-find by adding union by rank to keep trees shallow, further optimizing performance for very large inputs.

Intuition

Use union-find with path compression and union by rank to minimize tree height, speeding up find and union operations.

Algorithm

1. Initialize union-find with parent and rank arrays.
2. For each stone, union its row and column nodes with offset.
3. Use path compression in find to flatten trees.
4. Use union by rank to attach smaller tree under larger tree.
5. Return total stones minus number of connected components.

💡 The key is maintaining rank to keep union operations efficient and path compression to speed up finds.

</>

Code

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
        self.count = 0

    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
            self.rank[x] = 0
            self.count += 1
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            self.count -= 1


def removeStones(stones):
    uf = UnionFind()
    OFFSET = 10000
    for x, y in stones:
        uf.union(x, y + OFFSET)
    return len(stones) - uf.count

# Driver code
if __name__ == '__main__':
    stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
    print(removeStones(stones))  # Output: 5

Line Notes

self.rank = {}Initialize rank dictionary to track tree height

self.rank[x] = 0New node starts with rank 0

if self.rank[rootX] < self.rank[rootY]Attach smaller rank tree under larger rank tree

self.rank[rootX] += 1Increment rank when two equal rank trees merge

self.parent[x] = self.find(self.parent[x])Path compression to flatten tree

self.count -= 1Decrease count when union merges two sets

uf.union(x, y + OFFSET)Union row and column with offset

return len(stones) - uf.countCalculate max stones removed

import java.util.*;

class UnionFind {
    private Map<Integer, Integer> parent = new HashMap<>();
    private Map<Integer, Integer> rank = new HashMap<>();
    private int count = 0;

    public int find(int x) {
        if (!parent.containsKey(x)) {
            parent.put(x, x);
            rank.put(x, 0);
            count++;
        }
        if (parent.get(x) != x) {
            parent.put(x, find(parent.get(x)));
        }
        return parent.get(x);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            int rankX = rank.get(rootX);
            int rankY = rank.get(rootY);
            if (rankX < rankY) {
                parent.put(rootX, rootY);
            } else if (rankX > rankY) {
                parent.put(rootY, rootX);
            } else {
                parent.put(rootY, rootX);
                rank.put(rootX, rankX + 1);
            }
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}

public class Solution {
    public int removeStones(int[][] stones) {
        UnionFind uf = new UnionFind();
        int OFFSET = 10000;
        for (int[] stone : stones) {
            uf.union(stone[0], stone[1] + OFFSET);
        }
        return stones.length - uf.getCount();
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] stones = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
        System.out.println(sol.removeStones(stones)); // Output: 5
    }
}

Line Notes

private Map<Integer, Integer> rank = new HashMap<>()Rank map to track tree height

rank.put(x, 0)Initialize rank for new node

if (rankX < rankY)Attach smaller rank tree under larger rank tree

rank.put(rootX, rankX + 1)Increment rank when merging equal rank trees

parent.put(x, find(parent.get(x)))Path compression optimization

count--Decrease count when union merges sets

uf.union(stone[0], stone[1] + OFFSET)Union row and column with offset

return stones.length - uf.getCount()Calculate max stones removed

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class UnionFind {
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;
    int count = 0;
public:
    int find(int x) {
        if (parent.find(x) == parent.end()) {
            parent[x] = x;
            rank[x] = 0;
            count++;
        }
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }

    int getCount() {
        return count;
    }
};

class Solution {
public:
    int removeStones(vector<vector<int>>& stones) {
        UnionFind uf;
        const int OFFSET = 10000;
        for (auto& stone : stones) {
            uf.unite(stone[0], stone[1] + OFFSET);
        }
        return stones.size() - uf.getCount();
    }
};

int main() {
    Solution sol;
    vector<vector<int>> stones = {{0,0},{0,1},{1,0},{1,2},{2,1},{2,2}};
    cout << sol.removeStones(stones) << endl; // Output: 5
    return 0;
}

Line Notes

unordered_map<int, int> rankRank map to track tree height

rank[x] = 0Initialize rank for new node

if (rank[rootX] < rank[rootY])Attach smaller rank tree under larger rank tree

rank[rootX]++Increment rank when merging equal rank trees

parent[x] = find(parent[x])Path compression optimization

count--Decrease count when union merges sets

uf.unite(stone[0], stone[1] + OFFSET)Union row and column with offset

return stones.size() - uf.getCount()Calculate max stones removed

class UnionFind {
    constructor() {
        this.parent = new Map();
        this.rank = new Map();
        this.count = 0;
    }

    find(x) {
        if (!this.parent.has(x)) {
            this.parent.set(x, x);
            this.rank.set(x, 0);
            this.count++;
        }
        if (this.parent.get(x) !== x) {
            this.parent.set(x, this.find(this.parent.get(x)));
        }
        return this.parent.get(x);
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            const rankX = this.rank.get(rootX);
            const rankY = this.rank.get(rootY);
            if (rankX < rankY) {
                this.parent.set(rootX, rootY);
            } else if (rankX > rankY) {
                this.parent.set(rootY, rootX);
            } else {
                this.parent.set(rootY, rootX);
                this.rank.set(rootX, rankX + 1);
            }
            this.count--;
        }
    }
}

function removeStones(stones) {
    const uf = new UnionFind();
    const OFFSET = 10000;
    for (const [x, y] of stones) {
        uf.union(x, y + OFFSET);
    }
    return stones.length - uf.count;
}

// Driver code
const stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]];
console.log(removeStones(stones)); // Output: 5

Line Notes

this.rank = new Map()Rank map to track tree height

this.rank.set(x, 0)Initialize rank for new node

if (rankX < rankY)Attach smaller rank tree under larger rank tree

this.rank.set(rootX, rankX + 1)Increment rank when merging equal rank trees

this.parent.set(x, this.find(this.parent.get(x)))Path compression optimization

this.count--Decrease count when union merges sets

uf.union(x, y + OFFSET)Union row and column with offset

return stones.length - uf.countCalculate max stones removed

⏱

Complexity

TimeO(n α(n))

SpaceO(n)

Union-find with rank and path compression has near constant amortized time per operation.

💡 This is the most optimized union-find approach, suitable for very large inputs.

Interview Verdict: Accepted / Optimal with best union-find optimizations

This approach is the best practice for union-find problems in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 Use union-find with path compression and union by rank in 95% of interviews for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Graph DFS)	O(n^2)	O(n^2)	Yes (deep recursion possible)	N/A	Mention only - never code for large inputs
2. Union-Find without rank	O(n α(n))	O(n)	No	N/A	Good for initial union-find implementation
3. Union-Find with rank and path compression	O(n α(n))	O(n)	No	N/A	Best practice - code this if comfortable

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force graph approach to find connected components.Step 3: Explain inefficiency and introduce union-find to optimize.Step 4: Implement union-find with offset mapping for rows and columns.Step 5: Optionally optimize union-find with rank and path compression.Step 6: Test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your understanding of graph connectivity, union-find data structure, and ability to optimize naive solutions.

Common Follow-ups

• What if stones have very large coordinates? → Use hashing or coordinate compression.
• Can you solve without union-find? → Yes, DFS or BFS but less efficient.

💡 These follow-ups test your ability to handle large inputs and alternative graph traversal methods.

🔍

Pattern Recognition

When to Use

1) Problem involves grouping by shared rows or columns, 2) Need to find connected components, 3) Large input size requiring efficient unions, 4) Problem hints at union-find or disjoint sets.

Signature Phrases

stones sharing same row or columnlargest possible number of stones removed

NOT This Pattern When

Problems that require shortest path or dynamic programming are different despite involving grids.

Similar Problems

Number of Connected Components in an Undirected Graph - similar connected components conceptAccounts Merge - union-find to merge accounts by emails

Practice

1. Consider the following Python code implementing the optimal solution for the problem. Given the input n = 4 and edges = [[3,1,2],[3,2,3],[1,1,3],[2,3,4]], what is the final return value of max_num_edges_to_remove_sorted(n, edges)?

easy

A. 3

B. 2

C. 1

D. -1

Solution

1. Step 1: Sort edges by type descending

   Edges sorted: type 3 edges first: [3,1,2], [3,2,3], then type 1: [1,1,3], then type 2: [2,3,4].

2. Step 2: Process edges with union-find

   Type 3 edges connect nodes 0-1 and 1-2 for both Alice and Bob, used=2. Type 1 edge connects 0-2 for Alice, but already connected, so no increment. Type 2 edge connects 2-3 for Bob, used=3 total. Both have count=1 (fully connected). Edges used=3, total edges=4, so removable=1.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Used edges=3, removable=4-3=1 -> careful: used=3, removable=1 [OK]

Hint: Count used edges after union-find merges [OK]

Common Mistakes:

• Off-by-one in indexing nodes
• Ignoring type 3 edges first
• Counting used edges incorrectly

2. You are given a list of equations between variables, each either asserting equality (e.g., a==b) or inequality (e.g., a!=b). Which algorithmic approach best guarantees an efficient and correct solution to determine if all equations can be satisfied simultaneously?

easy

A. Union-Find data structure with two passes: first union all equalities, then check inequalities

B. Greedy approach that processes equations in input order, merging sets as it goes

C. Dynamic programming to track variable equivalences and contradictions

D. Brute force checking all pairs of variables for contradictions repeatedly

Solution

1. Step 1: Understand problem constraints

   The problem requires grouping variables into equivalence classes based on equalities and then verifying inequalities do not contradict these groups.

2. Step 2: Identify suitable algorithm

   Union-Find efficiently merges sets for equalities and then checks inequalities in a separate pass, ensuring correctness and near-linear time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-Find handles equivalence classes efficiently [OK]

Hint: Separate equality and inequality processing [OK]

Common Mistakes:

• Assuming greedy order works
• Using DP without clear state
• Brute force is too slow

3. What is the time complexity of the optimal Union-Find algorithm with path compression and union by rank when finding the redundant connection in a graph with n edges?

medium

A. O(n²) because each union operation may traverse all nodes

B. O(n * α(n)) where α(n) is the inverse Ackermann function, nearly constant

C. O(n log n) due to sorting edges before union operations

D. O(n) because each edge is processed once without overhead

Solution

1. Step 1: Identify number of union/find operations

   There are n edges, each triggers at most one union and two finds.

2. Step 2: Analyze complexity of find with path compression and union by rank

   Each find/union operation runs in amortized O(α(n)) time, where α(n) is inverse Ackermann function, which grows extremely slowly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Union-Find with optimizations runs in near-linear time O(n * α(n)) [OK]

Hint: Inverse Ackermann function α(n) is almost constant [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing sorting complexity with union-find
• Ignoring path compression benefits

4. Consider the following buggy union-find code snippet for Swim in Rising Water. Which line contains the subtle bug that can cause incorrect connectivity checks?

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return false
        if self.rank[rx] <= self.rank[ry]:
            self.parent[rx] = ry
        else:
            self.parent[ry] = rx
            if self.rank[rx] == self.rank[ry]:
                self.rank[rx] += 1
        return true

medium

A. Line with 'if rx == ry: return false' (checking if already connected)

B. Line 'if self.rank[rx] <= self.rank[ry]:' (union by rank condition)

C. Line 'self.parent[rx] = ry' (assigning parent when rank comparison true)

D. Line 'if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1' (rank increment after union)

Solution

1. Step 1: Analyze union by rank condition

   The condition uses '<=' which causes incorrect parent assignment when ranks are equal.

2. Step 2: Identify correct union by rank logic

   When ranks are equal, parent of ry should be set to rx and rank of rx incremented; current code reverses this.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect rank comparison leads to wrong parent assignment [OK]

Hint: Check union by rank condition carefully for equality case [OK]

Common Mistakes:

• Misusing <= instead of < in rank comparison
• Incrementing rank of wrong root after union
• Confusing which parent to assign when ranks equal

5. Suppose the problem is extended so that variables can be reused multiple times in equations, and inequalities can be chained (e.g., a==b, b!=c, c==a). Which modification to the union-find approach correctly handles early contradiction detection in this scenario?

hard

A. Process all equalities and inequalities in a single pass, unioning and checking contradictions immediately

B. First union all equalities, then check all inequalities for contradictions, returning false if any found

C. Use union-find with early contradiction detection by checking inequalities during union operations and aborting immediately on conflict

D. Replace union-find with a graph coloring approach to handle chained inequalities

Solution

1. Step 1: Understand reuse and chaining impact

   Variables appearing multiple times and chained inequalities require detecting contradictions as soon as they arise to avoid unnecessary work.

2. Step 2: Early contradiction detection

   Checking inequalities during union operations allows immediate detection of conflicts, improving efficiency and correctness.

3. Step 3: Compare alternatives

   Single pass union and check can miss contradictions; two-pass delays detection; graph coloring is more complex and less efficient here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Early contradiction detection aborts on conflict [OK]

Hint: Check contradictions during union to detect conflicts early [OK]

Common Mistakes:

• Checking inequalities only after all unions
• Trying single pass union and check without order