Remove Max Edges to Keep Graph Traversable

🎯

Remove Max Edges to Keep Graph Traversable

hardGRAPHAmazonGoogleFacebook

Imagine two friends, Alice and Bob, want to travel across a country using roads. Some roads are exclusive to Alice, some to Bob, and some shared. They want to remove as many roads as possible but still ensure both can travel anywhere in the country.

💡 This problem involves understanding how to maintain connectivity in a graph for two different users simultaneously. Beginners often struggle because it requires managing two overlapping connectivity sets and deciding which edges are essential or redundant.

📋

Problem Statement

You are given an undirected graph with n nodes labeled from 1 to n. The graph has three types of edges: type 1 edges can be traversed by Alice only, type 2 edges by Bob only, and type 3 edges by both Alice and Bob. Your task is to remove the maximum number of edges such that after removal, both Alice and Bob can still traverse the entire graph (i.e., the graph is fully connected for both). Return the maximum number of edges you can remove, or -1 if it's impossible for both to traverse the entire graph.

1 ≤ n ≤ 10^51 ≤ edges.length ≤ min(10^5, n * (n - 1) / 2)edges[i].length == 31 ≤ edges[i][0] ≤ 31 ≤ edges[i][1] < edges[i][2] ≤ n

💡

Example

Input"n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]"

Output2

We can remove two edges while keeping the graph fully traversable for both Alice and Bob.

Input"n = 4, edges = [[3,1,2],[1,1,4],[2,1,4]]"

Output-1

It's impossible for both Alice and Bob to traverse the entire graph after any removals.

• Graph with no edges → output -1 because no connectivity
• Graph with only type 3 edges → maximum removals possible while keeping connectivity
• Graph with edges only for Alice or only for Bob → likely -1
• Graph with duplicate edges → duplicates can be removed

⚠️

Common Mistakes

Not processing type 3 edges first

Misses maximizing shared connectivity, leading to incorrect results

✅ Always process type 3 edges before type 1 and 2

Union-find union returns ignored

Counting edges incorrectly, either overcounting or undercounting used edges

✅ Use union return value to count only edges that connect new components

Not checking full connectivity for both Alice and Bob at the end

Returning a result even if one user cannot traverse the entire graph

✅ Verify ufAlice.count == 1 and ufBob.count == 1 before returning result

Off-by-one errors in union-find indexing

Runtime errors or incorrect unions due to 1-based vs 0-based indexing mismatch

✅ Convert node labels from 1-based to 0-based before union-find operations

Not breaking early when both graphs are connected

Unnecessary processing leading to slower runtime

✅ Add early termination when ufAlice.count == 1 and ufBob.count == 1

🧠

Brute Force (Try All Subsets of Edges)

💡 This approach exists to understand the problem's combinatorial nature and why naive attempts are infeasible. It helps grasp the connectivity requirements before optimizing.

Intuition

Try every subset of edges to check if both Alice and Bob can traverse the entire graph. Count how many edges can be removed while maintaining full connectivity for both.

Algorithm

1. Generate all subsets of edges.
2. For each subset, build two graphs: one for Alice (type 1 and 3 edges) and one for Bob (type 2 and 3 edges).
3. Check if both graphs are fully connected.
4. Track the maximum number of edges removed among valid subsets.

💡 This algorithm is hard to see because it involves exponential subsets and separate connectivity checks for two users.

</>

Code

from itertools import combinations

def max_num_edges_to_remove_bruteforce(n, edges):
    max_remove = -1
    m = len(edges)
    # Check connectivity using DFS
    def is_connected(graph):
        visited = set()
        def dfs(u):
            visited.add(u)
            for v in graph[u]:
                if v not in visited:
                    dfs(v)
        dfs(1)
        return len(visited) == n

    for r in range(m + 1):
        for subset in combinations(edges, m - r):
            alice_graph = {i: [] for i in range(1, n + 1)}
            bob_graph = {i: [] for i in range(1, n + 1)}
            for t, u, v in subset:
                if t == 1 or t == 3:
                    alice_graph[u].append(v)
                    alice_graph[v].append(u)
                if t == 2 or t == 3:
                    bob_graph[u].append(v)
                    bob_graph[v].append(u)
            if is_connected(alice_graph) and is_connected(bob_graph):
                max_remove = max(max_remove, r)
    return max_remove

# Example usage
if __name__ == '__main__':
    n = 4
    edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
    print(max_num_edges_to_remove_bruteforce(n, edges))  # Output: 2

Line Notes

from itertools import combinationsImport combinations to generate all subsets of edges

def is_connected(graph):Helper function to check if a graph is fully connected

for r in range(m + 1):Try removing r edges from the graph

for subset in combinations(edges, m - r):Generate all subsets with m-r edges to keep

if is_connected(alice_graph) and is_connected(bob_graph):Check if both Alice and Bob can traverse the graph

return max_removeReturn the maximum number of edges that can be removed

import java.util.*;

public class Solution {
    // Helper class to represent graph and check connectivity
    static class Graph {
        Map<Integer, List<Integer>> adj;
        int n;
        Graph(int n) {
            this.n = n;
            adj = new HashMap<>();
            for (int i = 1; i <= n; i++) adj.put(i, new ArrayList<>());
        }
        void addEdge(int u, int v) {
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
        boolean isConnected() {
            Set<Integer> visited = new HashSet<>();
            dfs(1, visited);
            return visited.size() == n;
        }
        void dfs(int u, Set<Integer> visited) {
            visited.add(u);
            for (int v : adj.get(u)) {
                if (!visited.contains(v)) dfs(v, visited);
            }
        }
    }

    // Generate all combinations of edges of size k
    static void combinations(int[][] edges, int start, int k, List<int[]> current, List<List<int[]>> result) {
        if (current.size() == k) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < edges.length; i++) {
            current.add(edges[i]);
            combinations(edges, i + 1, k, current, result);
            current.remove(current.size() - 1);
        }
    }

    public static int maxNumEdgesToRemoveBruteForce(int n, int[][] edges) {
        int maxRemove = -1;
        int m = edges.length;
        for (int r = 0; r <= m; r++) {
            List<List<int[]>> subsets = new ArrayList<>();
            combinations(edges, 0, m - r, new ArrayList<>(), subsets);
            for (List<int[]> subset : subsets) {
                Graph aliceGraph = new Graph(n);
                Graph bobGraph = new Graph(n);
                for (int[] edge : subset) {
                    int t = edge[0], u = edge[1], v = edge[2];
                    if (t == 1 || t == 3) {
                        aliceGraph.addEdge(u, v);
                    }
                    if (t == 2 || t == 3) {
                        bobGraph.addEdge(u, v);
                    }
                }
                if (aliceGraph.isConnected() && bobGraph.isConnected()) {
                    maxRemove = Math.max(maxRemove, r);
                }
            }
        }
        return maxRemove;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{3,1,2},{3,2,3},{1,1,3},{1,2,4},{1,1,2},{2,3,4}};
        System.out.println(maxNumEdgesToRemoveBruteForce(n, edges)); // Output: 2
    }

Line Notes

static class Graph {Helper class to represent graph and check connectivity

void dfs(int u, Set<Integer> visited) {DFS to traverse graph nodes

for (int r = 0; r <= m; r++) {Try removing r edges from the graph

combinations(edges, 0, m - r, new ArrayList<>(), subsets);Generate all subsets with m-r edges to keep

if (aliceGraph.isConnected() && bobGraph.isConnected()) {Check connectivity for both Alice and Bob

return maxRemove;Return maximum removable edges

#include <bits/stdc++.h>
using namespace std;

class Graph {
public:
    unordered_map<int, vector<int>> adj;
    int n;
    Graph(int n) : n(n) {
        for (int i = 1; i <= n; i++) adj[i] = {};
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void dfs(int u, unordered_set<int>& visited) {
        visited.insert(u);
        for (int v : adj[u]) {
            if (!visited.count(v)) dfs(v, visited);
        }
    }
    bool isConnected() {
        unordered_set<int> visited;
        dfs(1, visited);
        return visited.size() == n;
    }
};

void combinations(const vector<vector<int>>& edges, int start, int k, vector<vector<int>>& current, vector<vector<vector<int>>>& result) {
    if ((int)current.size() == k) {
        result.push_back(current);
        return;
    }
    for (int i = start; i < (int)edges.size(); i++) {
        current.push_back(edges[i]);
        combinations(edges, i + 1, k, current, result);
        current.pop_back();
    }
}

int maxNumEdgesToRemoveBruteForce(int n, vector<vector<int>>& edges) {
    int maxRemove = -1;
    int m = (int)edges.size();
    for (int r = 0; r <= m; r++) {
        vector<vector<vector<int>>> subsets;
        vector<vector<int>> current;
        combinations(edges, 0, m - r, current, subsets);
        for (auto& subset : subsets) {
            Graph aliceGraph(n), bobGraph(n);
            for (auto& e : subset) {
                int t = e[0], u = e[1], v = e[2];
                if (t == 1 || t == 3) aliceGraph.addEdge(u, v);
                if (t == 2 || t == 3) bobGraph.addEdge(u, v);
            }
            if (aliceGraph.isConnected() && bobGraph.isConnected()) {
                maxRemove = max(maxRemove, r);
            }
        }
    }
    return maxRemove;
}

int main() {
    int n = 4;
    vector<vector<int>> edges = {{3,1,2},{3,2,3},{1,1,3},{1,2,4},{1,1,2},{2,3,4}};
    cout << maxNumEdgesToRemoveBruteForce(n, edges) << "\n"; // Output: 2
    return 0;
}

Line Notes

class Graph {Graph class to store adjacency and check connectivity

void dfs(int u, unordered_set<int>& visited) {DFS traversal to mark visited nodes

for (int r = 0; r <= m; r++) {Try removing r edges from the graph

combinations(edges, 0, m - r, current, subsets);Generate all subsets with m-r edges to keep

if (aliceGraph.isConnected() && bobGraph.isConnected()) {Check if both graphs are connected

return maxRemove;Return maximum number of removable edges

function maxNumEdgesToRemoveBruteforce(n, edges) {
    const m = edges.length;
    let maxRemove = -1;

    function isConnected(graph) {
        const visited = new Set();
        function dfs(u) {
            visited.add(u);
            for (const v of graph.get(u) || []) {
                if (!visited.has(v)) dfs(v);
            }
        }
        dfs(1);
        return visited.size === n;
    }

    function* combinations(arr, k, start = 0, path = []) {
        if (path.length === k) {
            yield path;
            return;
        }
        for (let i = start; i < arr.length; i++) {
            yield* combinations(arr, k, i + 1, path.concat(arr[i]));
        }
    }

    for (let r = 0; r <= m; r++) {
        for (const subset of combinations(edges, m - r)) {
            const aliceGraph = new Map();
            const bobGraph = new Map();
            for (const [t, u, v] of subset) {
                if (t === 1 || t === 3) {
                    if (!aliceGraph.has(u)) aliceGraph.set(u, []);
                    if (!aliceGraph.has(v)) aliceGraph.set(v, []);
                    aliceGraph.get(u).push(v);
                    aliceGraph.get(v).push(u);
                }
                if (t === 2 || t === 3) {
                    if (!bobGraph.has(u)) bobGraph.set(u, []);
                    if (!bobGraph.has(v)) bobGraph.set(v, []);
                    bobGraph.get(u).push(v);
                    bobGraph.get(v).push(u);
                }
            }
            if (isConnected(aliceGraph) && isConnected(bobGraph)) {
                maxRemove = Math.max(maxRemove, r);
            }
        }
    }
    return maxRemove;
}

// Example usage
const n = 4;
const edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]];
console.log(maxNumEdgesToRemoveBruteforce(n, edges)); // Output: 2

Line Notes

function isConnected(graph) {Helper to check if graph is fully connected

function* combinations(arr, k, start = 0, path = []) {Generator to produce all subsets of edges

for (let r = 0; r <= m; r++) {Try removing r edges from the graph

if (isConnected(aliceGraph) && isConnected(bobGraph)) {Check connectivity for both Alice and Bob

return maxRemove;Return maximum removable edges found

⏱

Complexity

TimeO(2^m * (n + m))

SpaceO(n + m)

We try all subsets of edges (2^m), and for each subset, we check connectivity for Alice and Bob using DFS (O(n + m)).

💡 For n=4 and m=6, this means 64 subsets and connectivity checks, which is already slow. For large n, this is impossible.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Greedy with Union-Find (Process Type 3 Edges First)

💡 This approach introduces union-find to efficiently manage connectivity and uses a greedy strategy to prioritize shared edges, which is key to solving the problem optimally.

Intuition

Use union-find to track connectivity for Alice and Bob separately. First, add all type 3 edges to both sets to maximize shared connectivity. Then add type 1 edges for Alice and type 2 edges for Bob. Count edges that do not contribute to connectivity as removable.

Algorithm

1. Initialize two union-find structures: one for Alice and one for Bob.
2. Add all type 3 edges to both union-finds; count edges that connect new components.
3. Add type 1 edges to Alice's union-find; count edges that connect new components.
4. Add type 2 edges to Bob's union-find; count edges that connect new components.
5. If both union-finds are fully connected, return total edges minus edges used; else return -1.

💡 The key difficulty is managing two union-finds and ensuring edges are counted correctly to maximize removals.

</>

Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = 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):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        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
        return True

def max_num_edges_to_remove(n, edges):
    uf_alice = UnionFind(n)
    uf_bob = UnionFind(n)
    used_edges = 0

    # Process type 3 edges first
    for t, u, v in edges:
        if t == 3:
            if uf_alice.union(u - 1, v - 1) | uf_bob.union(u - 1, v - 1):
                used_edges += 1

    # Process type 1 edges for Alice
    for t, u, v in edges:
        if t == 1:
            if uf_alice.union(u - 1, v - 1):
                used_edges += 1

    # Process type 2 edges for Bob
    for t, u, v in edges:
        if t == 2:
            if uf_bob.union(u - 1, v - 1):
                used_edges += 1

    if uf_alice.count == 1 and uf_bob.count == 1:
        return len(edges) - used_edges
    else:
        return -1

# Example usage
if __name__ == '__main__':
    n = 4
    edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
    print(max_num_edges_to_remove(n, edges))  # Output: 2

Line Notes

class UnionFind:Define union-find data structure to manage connectivity efficiently

def union(self, x, y):Union returns False if already connected, True if union done

for t, u, v in edges:Process edges by type in order: type 3 first, then 1, then 2

if uf_alice.union(u - 1, v - 1) | uf_bob.union(u - 1, v - 1):Union in both sets for type 3 edges; count if either union succeeds

if uf_alice.count == 1 and uf_bob.count == 1:Check if both graphs are fully connected

return len(edges) - used_edgesReturn maximum removable edges

import java.util.*;

class UnionFind {
    int[] parent, rank;
    int count;
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
        return true;
    }
}

public class Solution {
    public static int maxNumEdgesToRemove(int n, int[][] edges) {
        UnionFind ufAlice = new UnionFind(n);
        UnionFind ufBob = new UnionFind(n);
        int usedEdges = 0;

        for (int[] edge : edges) {
            if (edge[0] == 3) {
                boolean unionAlice = ufAlice.union(edge[1] - 1, edge[2] - 1);
                boolean unionBob = ufBob.union(edge[1] - 1, edge[2] - 1);
                if (unionAlice || unionBob) usedEdges++;
            }
        }
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                if (ufAlice.union(edge[1] - 1, edge[2] - 1)) usedEdges++;
            }
        }
        for (int[] edge : edges) {
            if (edge[0] == 2) {
                if (ufBob.union(edge[1] - 1, edge[2] - 1)) usedEdges++;
            }
        }
        if (ufAlice.count == 1 && ufBob.count == 1) return edges.length - usedEdges;
        return -1;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{3,1,2},{3,2,3},{1,1,3},{1,2,4},{1,1,2},{2,3,4}};
        System.out.println(maxNumEdgesToRemove(n, edges)); // Output: 2
    }
}

Line Notes

class UnionFind {Union-find class to manage disjoint sets efficiently

boolean union(int x, int y) {Union returns false if already connected, true if union performed

for (int[] edge : edges) {Process edges by type: type 3 first, then 1, then 2

if (unionAlice || unionBob) usedEdges++;Count edge if it connects new components in either set

if (ufAlice.count == 1 && ufBob.count == 1)Check if both Alice and Bob can traverse entire graph

return edges.length - usedEdges;Return maximum removable edges

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
public:
    vector<int> parent, rank;
    int count;
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool unionSet(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
        return true;
    }
};

int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
    UnionFind ufAlice(n), ufBob(n);
    int usedEdges = 0;

    for (auto& e : edges) {
        if (e[0] == 3) {
            bool ua = ufAlice.unionSet(e[1] - 1, e[2] - 1);
            bool ub = ufBob.unionSet(e[1] - 1, e[2] - 1);
            if (ua || ub) usedEdges++;
        }
    }
    for (auto& e : edges) {
        if (e[0] == 1) {
            if (ufAlice.unionSet(e[1] - 1, e[2] - 1)) usedEdges++;
        }
    }
    for (auto& e : edges) {
        if (e[0] == 2) {
            if (ufBob.unionSet(e[1] - 1, e[2] - 1)) usedEdges++;
        }
    }
    if (ufAlice.count == 1 && ufBob.count == 1) return (int)edges.size() - usedEdges;
    return -1;
}

int main() {
    int n = 4;
    vector<vector<int>> edges = {{3,1,2},{3,2,3},{1,1,3},{1,2,4},{1,1,2},{2,3,4}};
    cout << maxNumEdgesToRemove(n, edges) << "\n"; // Output: 2
    return 0;
}

Line Notes

class UnionFind {Union-find data structure for efficient connectivity checks

bool unionSet(int x, int y) {Union returns false if already connected, true if union done

for (auto& e : edges) {Process edges by type in order: 3, then 1, then 2

if (ua || ub) usedEdges++;Count edge if it connects new components in either union-find

if (ufAlice.count == 1 && ufBob.count == 1)Check if both graphs are fully connected

return (int)edges.size() - usedEdges;Return maximum removable edges

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
        this.count = n;
    }
    find(x) {
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }
    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX === rootY) return false;
        if (this.rank[rootX] < this.rank[rootY]) this.parent[rootX] = rootY;
        else if (this.rank[rootX] > this.rank[rootY]) this.parent[rootY] = rootX;
        else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        this.count--;
        return true;
    }
}

function maxNumEdgesToRemove(n, edges) {
    const ufAlice = new UnionFind(n);
    const ufBob = new UnionFind(n);
    let usedEdges = 0;

    for (const [t, u, v] of edges) {
        if (t === 3) {
            const ua = ufAlice.union(u - 1, v - 1);
            const ub = ufBob.union(u - 1, v - 1);
            if (ua || ub) usedEdges++;
        }
    }
    for (const [t, u, v] of edges) {
        if (t === 1) {
            if (ufAlice.union(u - 1, v - 1)) usedEdges++;
        }
    }
    for (const [t, u, v] of edges) {
        if (t === 2) {
            if (ufBob.union(u - 1, v - 1)) usedEdges++;
        }
    }
    if (ufAlice.count === 1 && ufBob.count === 1) return edges.length - usedEdges;
    return -1;
}

// Example usage
const n = 4;
const edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]];
console.log(maxNumEdgesToRemove(n, edges)); // Output: 2

Line Notes

class UnionFind {Union-find class to efficiently manage disjoint sets

union(x, y) {Union returns false if already connected, true if union performed

for (const [t, u, v] of edges) {Process edges by type: 3 first, then 1, then 2

if (ua || ub) usedEdges++;Count edge if it connects new components in either union-find

if (ufAlice.count === 1 && ufBob.count === 1)Check if both Alice and Bob can traverse entire graph

return edges.length - usedEdges;Return maximum removable edges

⏱

Complexity

TimeO(m α(n))

SpaceO(n)

Union-find operations are almost O(1) amortized (α is inverse Ackermann function). We process all edges a constant number of times.

💡 For n=10^5 and m=10^5, this approach is efficient and practical for interviews.

Interview Verdict: Accepted

This is the optimal and accepted approach, demonstrating mastery of union-find and greedy strategies.

🧠

Union-Find with Edge Sorting and Early Termination

💡 This approach optimizes the previous by sorting edges by type and stopping early when full connectivity is achieved, improving runtime in practice.

Intuition

Sort edges so type 3 edges come first, then type 1, then type 2. Use union-find to add edges greedily. Stop processing once both Alice and Bob are fully connected to avoid unnecessary work.

Algorithm

1. Sort edges so type 3 edges come first, then type 1, then type 2.
2. Initialize union-find for Alice and Bob.
3. Iterate edges in order, union nodes accordingly, and count used edges.
4. After each union, check if both Alice and Bob are fully connected; if yes, break early.
5. Return total edges minus used edges if fully connected; else -1.

💡 The challenge is managing early termination correctly and ensuring sorting preserves the greedy strategy.

</>

Code

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = 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):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        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
        return True

def max_num_edges_to_remove_sorted(n, edges):
    edges.sort(key=lambda x: -x[0])  # type 3 first
    uf_alice = UnionFind(n)
    uf_bob = UnionFind(n)
    used_edges = 0

    for t, u, v in edges:
        if t == 3:
            union_a = uf_alice.union(u - 1, v - 1)
            union_b = uf_bob.union(u - 1, v - 1)
            if union_a or union_b:
                used_edges += 1
        elif t == 1:
            if uf_alice.union(u - 1, v - 1):
                used_edges += 1
        else:  # t == 2
            if uf_bob.union(u - 1, v - 1):
                used_edges += 1
        if uf_alice.count == 1 and uf_bob.count == 1:
            break

    if uf_alice.count == 1 and uf_bob.count == 1:
        return len(edges) - used_edges
    else:
        return -1

# Example usage
if __name__ == '__main__':
    n = 4
    edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
    print(max_num_edges_to_remove_sorted(n, edges))  # Output: 2

Line Notes

edges.sort(key=lambda x: -x[0])Sort edges so type 3 edges are processed first

union_a = uf_alice.union(u - 1, v - 1)Try union for Alice on current edge

union_b = uf_bob.union(u - 1, v - 1)Try union for Bob on current edge

if union_a or union_b:Count edge if it connects new components for either user

if uf_alice.count == 1 and uf_bob.count == 1:Early termination if both fully connected

return len(edges) - used_edgesReturn maximum removable edges

import java.util.*;

public class Solution {
    static class UnionFind {
        int[] parent, rank;
        int count;
        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            count = n;
            for (int i = 0; i < n; i++) parent[i] = i;
        }
        int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];
                x = parent[x];
            }
            return x;
        }
        boolean union(int x, int y) {
            int rootX = find(x), rootY = find(y);
            if (rootX == rootY) return false;
            if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
            return true;
        }
    }

    public static int maxNumEdgesToRemoveSorted(int n, int[][] edges) {
        Arrays.sort(edges, (a, b) -> b[0] - a[0]);
        UnionFind ufAlice = new UnionFind(n);
        UnionFind ufBob = new UnionFind(n);
        int usedEdges = 0;

        for (int[] edge : edges) {
            int t = edge[0], u = edge[1] - 1, v = edge[2] - 1;
            if (t == 3) {
                boolean unionAlice = ufAlice.union(u, v);
                boolean unionBob = ufBob.union(u, v);
                if (unionAlice || unionBob) usedEdges++;
            } else if (t == 1) {
                if (ufAlice.union(u, v)) usedEdges++;
            } else {
                if (ufBob.union(u, v)) usedEdges++;
            }
            if (ufAlice.count == 1 && ufBob.count == 1) break;
        }
        if (ufAlice.count == 1 && ufBob.count == 1) return edges.length - usedEdges;
        return -1;
    }

    public static void main(String[] args) {
        int n = 4;
        int[][] edges = {{3,1,2},{3,2,3},{1,1,3},{1,2,4},{1,1,2},{2,3,4}};
        System.out.println(maxNumEdgesToRemoveSorted(n, edges)); // Output: 2
    }
}

Line Notes

Arrays.sort(edges, (a, b) -> b[0] - a[0]);Sort edges descending by type to process type 3 first

boolean unionAlice = ufAlice.union(u, v);Try union for Alice on current edge

boolean unionBob = ufBob.union(u, v);Try union for Bob on current edge

if (unionAlice || unionBob) usedEdges++;Count edge if it connects new components

if (ufAlice.count == 1 && ufBob.count == 1) break;Early stop if both fully connected

return edges.length - usedEdges;Return maximum removable edges

#include <bits/stdc++.h>
using namespace std;

class UnionFind {
public:
    vector<int> parent, rank;
    int count;
    UnionFind(int n) : parent(n), rank(n, 0), count(n) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    bool unionSet(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;
        if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
        else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
        else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
        return true;
    }
};

int maxNumEdgesToRemoveSorted(int n, vector<vector<int>>& edges) {
    sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a[0] > b[0]; });
    UnionFind ufAlice(n), ufBob(n);
    int usedEdges = 0;

    for (auto& e : edges) {
        int t = e[0], u = e[1] - 1, v = e[2] - 1;
        if (t == 3) {
            bool ua = ufAlice.unionSet(u, v);
            bool ub = ufBob.unionSet(u, v);
            if (ua || ub) usedEdges++;
        } else if (t == 1) {
            if (ufAlice.unionSet(u, v)) usedEdges++;
        } else {
            if (ufBob.unionSet(u, v)) usedEdges++;
        }
        if (ufAlice.count == 1 && ufBob.count == 1) break;
    }
    if (ufAlice.count == 1 && ufBob.count == 1) return (int)edges.size() - usedEdges;
    return -1;
}

int main() {
    int n = 4;
    vector<vector<int>> edges = {{3,1,2},{3,2,3},{1,1,3},{1,2,4},{1,1,2},{2,3,4}};
    cout << maxNumEdgesToRemoveSorted(n, edges) << "\n"; // Output: 2
    return 0;
}

Line Notes

sort(edges.begin(), edges.end(), [](auto& a, auto& b) { return a[0] > b[0]; });Sort edges descending by type to process type 3 first

bool ua = ufAlice.unionSet(u, v);Try union for Alice on current edge

bool ub = ufBob.unionSet(u, v);Try union for Bob on current edge

if (ua || ub) usedEdges++;Count edge if it connects new components

if (ufAlice.count == 1 && ufBob.count == 1) break;Early stop if both fully connected

return (int)edges.size() - usedEdges;Return maximum removable edges

class UnionFind {
    constructor(n) {
        this.parent = Array.from({length: n}, (_, i) => i);
        this.rank = Array(n).fill(0);
        this.count = n;
    }
    find(x) {
        while (this.parent[x] !== x) {
            this.parent[x] = this.parent[this.parent[x]];
            x = this.parent[x];
        }
        return x;
    }
    union(x, y) {
        let rootX = this.find(x);
        let rootY = this.find(y);
        if (rootX === rootY) return false;
        if (this.rank[rootX] < this.rank[rootY]) this.parent[rootX] = rootY;
        else if (this.rank[rootX] > this.rank[rootY]) this.parent[rootY] = rootX;
        else {
            this.parent[rootY] = rootX;
            this.rank[rootX]++;
        }
        this.count--;
        return true;
    }
}

function maxNumEdgesToRemoveSorted(n, edges) {
    edges.sort((a, b) => b[0] - a[0]);
    const ufAlice = new UnionFind(n);
    const ufBob = new UnionFind(n);
    let usedEdges = 0;

    for (const [t, u, v] of edges) {
        if (t === 3) {
            const ua = ufAlice.union(u - 1, v - 1);
            const ub = ufBob.union(u - 1, v - 1);
            if (ua || ub) usedEdges++;
        } else if (t === 1) {
            if (ufAlice.union(u - 1, v - 1)) usedEdges++;
        } else {
            if (ufBob.union(u - 1, v - 1)) usedEdges++;
        }
        if (ufAlice.count === 1 && ufBob.count === 1) break;
    }
    if (ufAlice.count === 1 && ufBob.count === 1) return edges.length - usedEdges;
    return -1;
}

// Example usage
const n = 4;
const edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]];
console.log(maxNumEdgesToRemoveSorted(n, edges)); // Output: 2

Line Notes

edges.sort((a, b) => b[0] - a[0]);Sort edges descending by type to process type 3 first

const ua = ufAlice.union(u - 1, v - 1);Try union for Alice on current edge

const ub = ufBob.union(u - 1, v - 1);Try union for Bob on current edge

if (ua || ub) usedEdges++;Count edge if it connects new components

if (ufAlice.count === 1 && ufBob.count === 1) break;Early stop if both fully connected

return edges.length - usedEdges;Return maximum removable edges

⏱

Complexity

TimeO(m log m + m α(n))

SpaceO(n)

Sorting edges takes O(m log m), union-find operations are O(m α(n)). Early termination can reduce runtime in practice.

💡 This approach is slightly faster in practice due to sorting and early stopping, useful for large inputs.

Interview Verdict: Accepted

This is an optimized accepted solution that balances clarity and performance.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, always code the union-find greedy approach (Approach 2 or 3). Brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^m * (n + m))	O(n + m)	Yes (deep recursion in DFS)	N/A	Mention only - never code due to inefficiency
2. Greedy with Union-Find (Process Type 3 First)	O(m α(n))	O(n)	No	Yes	Code this approach for optimal solution
3. Union-Find with Edge Sorting and Early Termination	O(m log m + m α(n))	O(n)	No	Yes	Code this if asked for optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding. Progress to the union-find greedy solution, and finally mention optimizations. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach to show understanding of connectivity.Step 3: Introduce union-find and explain the greedy strategy of processing type 3 edges first.Step 4: Code the union-find solution carefully, explaining each step.Step 5: Discuss possible optimizations like sorting edges and early termination.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Optimize: 7min. Total ~30min

What the Interviewer Tests

The interviewer tests your understanding of graph connectivity, union-find data structure, greedy strategies, and ability to optimize code for large inputs.

Common Follow-ups

• What if edges are not sorted? → Sorting helps prioritize shared edges.
• Can we solve without union-find? → Possible but inefficient and complex.
• How to handle disconnected graphs? → Return -1 if either Alice or Bob cannot traverse fully.
• What if we want to maximize edges used instead? → Similar approach but count differently.

💡 These follow-ups test your depth of understanding and ability to adapt solutions.

🔍

Pattern Recognition

When to Use

Use this pattern when: 1) Graph connectivity for multiple users is involved, 2) Edges have types or constraints, 3) You need to maximize or minimize edges while preserving connectivity, 4) Union-find is applicable for efficient connectivity checks.

Signature Phrases

'edges can be traversed by Alice only, Bob only, or both''remove maximum number of edges while keeping graph fully traversable'

NOT This Pattern When

Problems involving shortest paths, minimum spanning trees, or DP on graphs are different patterns.

Similar Problems

Number of Connected Components in an Undirected Graph - basic union-findRedundant Connection - cycle detection with union-findGraph Valid Tree - connectivity and cycle checks

Practice

1. 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

2. Examine the following buggy union-find code used in Kruskal's MST. Which line contains the subtle bug that can cause incorrect MST results on disconnected graphs?

medium

A. Line: if self.size[rx] < self.size[ry]:

B. Line: edges.sort(key=lambda x: x[2])

C. Line: return mst_weight # No connectivity check

D. Line: self.parent[x] = self.parent[self.parent[x]] # Path compression

Solution

1. Step 1: Identify missing connectivity validation

   The code returns mst_weight without verifying if all nodes are connected, which can produce incorrect MST for disconnected graphs.

2. Step 2: Understand impact of missing check

   Without checking if edges_used == n-1 or connectivity, the MST may be incomplete, returning partial sums.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Connectivity check missing causes incomplete MST [OK]

Hint: Always verify MST connects all nodes before returning [OK]

Common Mistakes:

• Forgetting to check if MST spans all vertices
• Assuming union-find union count guarantees connectivity
• Ignoring disconnected graph edge cases

3. The following code attempts to implement the optimal solution for the smallest string with swaps problem. Identify the line that contains a subtle bug that can cause incorrect output.

medium

A. Line: for i, idx in enumerate(group): res[idx] = chars[i]

B. Line: groups[uf.find(i)].append(i)

C. Line: for x, y in pairs: uf.union(x, y)

D. Line: chars.sort()

Solution

1. Step 1: Identify grouping and sorting

   Indices in each group are collected but not sorted before assignment.

2. Step 2: Check assignment order

   Assigning sorted characters to unsorted group indices causes characters to be placed incorrectly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting group indices before assignment fixes the bug [OK]

Hint: Always sort indices before assigning sorted chars [OK]

Common Mistakes:

• Not sorting indices before assignment
• Assuming group order matches index order

4. Suppose the problem is modified so that stones can be removed only if they share the same row or column AND the stones are adjacent (i.e., consecutive indices in row or column). Which approach correctly adapts to this constraint?

hard

A. Use brute force DFS on the graph where edges exist only between adjacent stones in rows or columns

B. Modify union-find to only union stones if their row or column indices differ by exactly 1

C. Use the same union-find approach connecting all stones sharing rows or columns without modification

D. Sort stones and greedily remove stones from the largest connected component

Solution

1. Step 1: Understand adjacency constraint

   Only stones adjacent in row or column can be connected, so union-find on all stones sharing row/column is incorrect.

2. Step 2: Choose graph DFS on adjacency edges

   Build graph edges only between stones adjacent in row or column, then DFS to find connected components.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-find without adjacency check unions too many stones [OK]

Hint: Adjacency requires explicit graph edges, not union-find on all same row/col [OK]

Common Mistakes:

• Applying union-find without adjacency check
• Assuming greedy removal works
• Ignoring sorting and adjacency in graph construction

5. Suppose the problem is modified so that edges can be added multiple times (i.e., duplicate edges allowed), and you need to find the first edge that creates a cycle considering duplicates. Which modification to the union-find approach correctly handles this scenario?

hard

A. Before union, check if the edge already exists in a hash set; if yes, return it immediately as redundant

B. Use union-find as usual but also maintain a visited edges set to detect duplicates causing cycles

C. Modify union-find to count the number of times an edge is added and only detect cycle when count > 1

D. Ignore duplicates and run union-find as usual; duplicates won't affect cycle detection

Solution

1. Step 1: Understand duplicate edges impact

   Duplicate edges connect the same nodes multiple times, creating immediate cycles on second insertion.

2. Step 2: Modify algorithm to detect duplicates

   Using a hash set to track edges allows detecting duplicates before union, returning the duplicate edge as redundant immediately.

3. Step 3: Why other options fail

   Ignoring duplicates misses immediate cycle; counting edge additions in union-find is not standard; maintaining visited edges separately duplicates hash set logic.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash set lookup detects duplicates in O(1) before union [OK]

Hint: Detect duplicates with a hash set before union [OK]

Common Mistakes:

• Assuming union-find alone detects duplicates
• Trying to count edges in union-find
• Ignoring duplicate edges impact