Facebook Pixel

1579. Remove Max Number of Edges to Keep Graph Fully Traversable

HardUnion FindGraph
Leetcode Link

Problem Description

This problem involves a graph with n nodes that needs to be traversable by both Alice and Bob. The graph has three types of edges:

  • Type 1: Only Alice can use these edges
  • Type 2: Only Bob can use these edges
  • Type 3: Both Alice and Bob can use these edges

You're given an array edges where each element edges[i] = [type_i, u_i, v_i] represents a bidirectional edge of type type_i connecting nodes u_i and v_i.

The goal is to find the maximum number of edges you can remove while ensuring that:

  • After removal, Alice can still reach every node from any starting node (the graph remains fully connected for Alice)
  • After removal, Bob can still reach every node from any starting node (the graph remains fully connected for Bob)

If it's impossible for both Alice and Bob to fully traverse the graph even without removing any edges, return -1.

The solution uses a Union-Find (Disjoint Set Union) data structure to efficiently track connectivity. The key insight is to:

  1. First process Type 3 edges (usable by both), as they're most valuable for maintaining connectivity
  2. Keep an edge only if it connects previously disconnected components
  3. Count redundant edges (those connecting already-connected components) as removable
  4. Check if both Alice's and Bob's graphs are fully connected at the end

The approach maintains separate Union-Find structures for Alice and Bob to track their individual connectivity requirements.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to think about this problem in reverse - instead of removing edges, we should think about which edges we must keep to maintain connectivity for both Alice and Bob.

For a graph with n nodes to be fully connected, we need exactly n-1 edges (this forms a spanning tree). Since both Alice and Bob need their own connected graphs, we might initially think we need 2*(n-1) edges total. However, Type 3 edges are special - they can serve both Alice and Bob simultaneously, potentially reducing the total edges needed.

This leads us to a greedy strategy: Type 3 edges are the most valuable because one Type 3 edge can satisfy connectivity requirements for both Alice and Bob. We should prioritize keeping Type 3 edges over Type 1 or Type 2 edges whenever possible.

The approach becomes clear:

  1. Process Type 3 edges first - Each Type 3 edge that connects previously disconnected components helps both Alice and Bob simultaneously. If a Type 3 edge connects nodes already connected, it's redundant and can be removed.

  2. Then process Type 1 and Type 2 edges - After using Type 3 edges, we fill in the remaining gaps in Alice's and Bob's connectivity with their specific edge types. Again, any edge connecting already-connected nodes is redundant.

We use Union-Find to efficiently track which nodes are already connected. When we try to union two nodes:

  • If they're in different components, the edge is necessary (union returns True)
  • If they're already in the same component, the edge is redundant (union returns False)

The total removable edges equals the number of redundant edges we encounter. Finally, we verify both graphs are fully connected (each has exactly 1 component) - if not, we return -1.

Learn more about Union Find and Graph patterns.

Solution Approach

The solution implements two Union-Find data structures to track connectivity for Alice and Bob separately.

Union-Find Implementation:

  • p: Parent array where p[i] stores the parent of node i
  • size: Array tracking the size of each component for union by rank optimization
  • cnt: Counter tracking the number of disjoint components (starts at n, decreases with each successful union)
  • find(x): Finds the root of node x with path compression
  • union(a, b): Merges components containing nodes a and b. Returns True if they were in different components (edge is necessary), False if already connected (edge is redundant)

Main Algorithm:

  1. Initialize two Union-Find structures: ufa for Alice and ufb for Bob, each with n nodes.

  2. First pass - Process Type 3 edges:

    for t, u, v in edges:
    if t == 3:
        if ufa.union(u, v):  # Try to union in Alice's [graph](/problems/graph_intro)
            ufb.union(u, v)  # If successful, also union in Bob's graph
        else:
            ans += 1  # Edge is redundant, can be removed

    When a Type 3 edge successfully connects components in Alice's graph, we also apply it to Bob's graph. If it's redundant for Alice, it's redundant for both.

  3. Second pass - Process Type 1 and Type 2 edges:

    for t, u, v in edges:
    if t == 1:
        ans += not ufa.union(u, v)  # Count redundant edges for Alice
    if t == 2:
        ans += not ufb.union(u, v)  # Count redundant edges for Bob

    For each type-specific edge, we attempt to union the nodes. If union returns False, the edge is redundant and we increment our removable edge count.

  4. Final validation:

    return ans if ufa.cnt == 1 and ufb.cnt == 1 else -1

    Check if both graphs are fully connected (each has exactly 1 component). If either has more than 1 component, return -1 as full traversal is impossible.

Note: The solution uses 1-indexed nodes in the input, so union(u, v) internally converts to 0-indexed with find(a - 1) and find(b - 1).

The time complexity is O(E * α(n)) where E is the number of edges and α is the inverse Ackermann function (practically constant). Space complexity is O(n) for the Union-Find structures.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with n = 4 nodes and the following edges:

edges = [[3,1,2], [3,2,3], [1,1,3], [1,2,4], [1,1,2], [2,3,4]]

Initial Setup:

  • Create two Union-Find structures for Alice and Bob
  • Both start with 4 separate components: {1}, {2}, {3}, {4}
  • Alice's components: 4, Bob's components: 4
  • Removable edges counter: 0

First Pass - Process Type 3 edges:

  1. Edge [3,1,2]: Type 3 edge connecting nodes 1 and 2

    • Alice: Union(1,2) → Success! Components become {1,2}, {3}, {4} (count: 3)
    • Bob: Also union(1,2) → Components become {1,2}, {3}, {4} (count: 3)
    • This edge is necessary, removable count stays at 0

  2. Edge [3,2,3]: Type 3 edge connecting nodes 2 and 3

    • Alice: Union(2,3) → Success! Components become {1,2,3}, {4} (count: 2)
    • Bob: Also union(2,3) → Components become {1,2,3}, {4} (count: 2)
    • This edge is necessary, removable count stays at 0

Second Pass - Process Type 1 and Type 2 edges:

  1. Edge [1,1,3]: Type 1 edge (Alice only) connecting nodes 1 and 3

    • Alice: Union(1,3) → Fail! Nodes 1 and 3 are already connected through 2
    • This edge is redundant, removable count: 0 + 1 = 1

  2. Edge [1,2,4]: Type 1 edge (Alice only) connecting nodes 2 and 4

    • Alice: Union(2,4) → Success! Components become {1,2,3,4} (count: 1)
    • This edge is necessary, removable count stays at 1

  3. Edge [1,1,2]: Type 1 edge (Alice only) connecting nodes 1 and 2

    • Alice: Union(1,2) → Fail! Already connected
    • This edge is redundant, removable count: 1 + 1 = 2

  4. Edge [2,3,4]: Type 2 edge (Bob only) connecting nodes 3 and 4

    • Bob: Union(3,4) → Success! Components become {1,2,3,4} (count: 1)
    • This edge is necessary, removable count stays at 2

Final Check:

  • Alice's component count: 1 ✓ (fully connected)
  • Bob's component count: 1 ✓ (fully connected)
  • Both graphs are fully connected, so we return the removable count: 2

The edges we can remove are [1,1,3] and [1,1,2], both Type 1 edges that were redundant for Alice's connectivity.

Solution Implementation

1from typing import List
2
3
4class UnionFind:
5    """Union-Find (Disjoint Set Union) data structure with path compression and union by size."""
6  
7    def __init__(self, n: int) -> None:
8        """
9        Initialize Union-Find structure with n nodes.
10      
11        Args:
12            n: Number of nodes (0-indexed internally)
13        """
14        # Parent array - initially each node is its own parent
15        self.parent = list(range(n))
16        # Size of each component - initially all components have size 1
17        self.component_size = [1] * n
18        # Number of connected components
19        self.component_count = n
20
21    def find(self, x: int) -> int:
22        """
23        Find the root of the component containing node x.
24        Uses path compression for optimization.
25      
26        Args:
27            x: Node to find the root for
28          
29        Returns:
30            Root node of the component containing x
31        """
32        if self.parent[x] != x:
33            # Path compression: make all nodes point directly to root
34            self.parent[x] = self.find(self.parent[x])
35        return self.parent[x]
36
37    def union(self, node_a: int, node_b: int) -> bool:
38        """
39        Unite two components containing nodes a and b.
40        Uses union by size for optimization.
41      
42        Args:
43            node_a: First node (1-indexed, converted to 0-indexed internally)
44            node_b: Second node (1-indexed, converted to 0-indexed internally)
45          
46        Returns:
47            True if union was performed (nodes were in different components),
48            False if nodes were already in the same component
49        """
50        # Convert from 1-indexed to 0-indexed
51        root_a = self.find(node_a - 1)
52        root_b = self.find(node_b - 1)
53      
54        # Already in the same component
55        if root_a == root_b:
56            return False
57      
58        # Union by size: attach smaller tree under root of larger tree
59        if self.component_size[root_a] > self.component_size[root_b]:
60            self.parent[root_b] = root_a
61            self.component_size[root_a] += self.component_size[root_b]
62        else:
63            self.parent[root_a] = root_b
64            self.component_size[root_b] += self.component_size[root_a]
65      
66        # Decrease component count as two components merged into one
67        self.component_count -= 1
68        return True
69
70
71class Solution:
72    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:
73        """
74        Find maximum number of edges that can be removed while keeping graph 
75        fully traversable for both Alice and Bob.
76      
77        Edge types:
78        - Type 1: Only Alice can traverse
79        - Type 2: Only Bob can traverse  
80        - Type 3: Both Alice and Bob can traverse
81      
82        Args:
83            n: Number of nodes in the graph (1-indexed)
84            edges: List of [type, u, v] representing edges
85          
86        Returns:
87            Maximum number of removable edges, or -1 if impossible to make
88            graph fully traversable for both Alice and Bob
89        """
90        # Create separate Union-Find structures for Alice and Bob
91        alice_uf = UnionFind(n)
92        bob_uf = UnionFind(n)
93        removable_edges = 0
94      
95        # Process Type 3 edges first (beneficial to both Alice and Bob)
96        for edge_type, u, v in edges:
97            if edge_type == 3:
98                # If edge connects new components for Alice, also add for Bob
99                if alice_uf.union(u, v):
100                    bob_uf.union(u, v)
101                else:
102                    # Edge is redundant for both - can be removed
103                    removable_edges += 1
104      
105        # Process Type 1 (Alice only) and Type 2 (Bob only) edges
106        for edge_type, u, v in edges:
107            if edge_type == 1:
108                # Count redundant edges for Alice
109                removable_edges += not alice_uf.union(u, v)
110            elif edge_type == 2:
111                # Count redundant edges for Bob
112                removable_edges += not bob_uf.union(u, v)
113      
114        # Check if both graphs are fully connected (single component)
115        if alice_uf.component_count == 1 and bob_uf.component_count == 1:
116            return removable_edges
117        else:
118            return -1
119
1/**
2 * Union-Find (Disjoint Set Union) data structure with path compression and union by size
3 */
4class UnionFind {
5    private int[] parent;           // parent[i] stores the parent of node i
6    private int[] size;             // size[i] stores the size of the tree rooted at i
7    public int componentCount;      // number of connected components
8  
9    /**
10     * Initialize Union-Find structure with n nodes (0 to n-1)
11     * @param n number of nodes
12     */
13    public UnionFind(int n) {
14        parent = new int[n];
15        size = new int[n];
16      
17        // Initially, each node is its own parent (self-loop)
18        // and each component has size 1
19        for (int i = 0; i < n; i++) {
20            parent[i] = i;
21            size[i] = 1;
22        }
23        componentCount = n;
24    }
25  
26    /**
27     * Find the root of the component containing node x with path compression
28     * @param x the node to find root for
29     * @return root of the component containing x
30     */
31    public int find(int x) {
32        // Path compression: make all nodes on path point directly to root
33        if (parent[x] != x) {
34            parent[x] = find(parent[x]);
35        }
36        return parent[x];
37    }
38  
39    /**
40     * Union two nodes a and b (1-indexed) into the same component
41     * @param a first node (1-indexed)
42     * @param b second node (1-indexed)
43     * @return true if union was performed, false if already in same component
44     */
45    public boolean union(int a, int b) {
46        // Convert to 0-indexed and find roots
47        int rootA = find(a - 1);
48        int rootB = find(b - 1);
49      
50        // Already in the same component
51        if (rootA == rootB) {
52            return false;
53        }
54      
55        // Union by size: attach smaller tree under larger tree
56        if (size[rootA] > size[rootB]) {
57            parent[rootB] = rootA;
58            size[rootA] += size[rootB];
59        } else {
60            parent[rootA] = rootB;
61            size[rootB] += size[rootA];
62        }
63      
64        // Decrease component count after successful union
65        componentCount--;
66        return true;
67    }
68}
69
70/**
71 * Solution for removing maximum number of edges while keeping graph fully traversable
72 * for both Alice and Bob
73 */
74class Solution {
75    /**
76     * Find maximum number of edges that can be removed while keeping the graph
77     * fully traversable for both Alice and Bob
78     * @param n number of nodes (1 to n)
79     * @param edges array of edges where each edge is [type, u, v]
80     *              type 1: only Alice can traverse
81     *              type 2: only Bob can traverse
82     *              type 3: both can traverse
83     * @return maximum number of removable edges, or -1 if impossible
84     */
85    public int maxNumEdgesToRemove(int n, int[][] edges) {
86        // Create separate Union-Find structures for Alice and Bob
87        UnionFind aliceUnionFind = new UnionFind(n);
88        UnionFind bobUnionFind = new UnionFind(n);
89      
90        int removableEdges = 0;
91      
92        // Process type 3 edges first (edges both Alice and Bob can use)
93        // These are most valuable as they benefit both graphs
94        for (int[] edge : edges) {
95            int type = edge[0];
96            int nodeU = edge[1];
97            int nodeV = edge[2];
98          
99            if (type == 3) {
100                // Try to add edge to Alice's graph
101                if (aliceUnionFind.union(nodeU, nodeV)) {
102                    // If successful for Alice, also add to Bob's graph
103                    bobUnionFind.union(nodeU, nodeV);
104                } else {
105                    // Edge creates a cycle in Alice's graph, so it's removable
106                    removableEdges++;
107                }
108            }
109        }
110      
111        // Process type 1 (Alice only) and type 2 (Bob only) edges
112        for (int[] edge : edges) {
113            int type = edge[0];
114            int nodeU = edge[1];
115            int nodeV = edge[2];
116          
117            // Process Alice-only edges
118            if (type == 1 && !aliceUnionFind.union(nodeU, nodeV)) {
119                // Edge creates a cycle in Alice's graph, so it's removable
120                removableEdges++;
121            }
122          
123            // Process Bob-only edges
124            if (type == 2 && !bobUnionFind.union(nodeU, nodeV)) {
125                // Edge creates a cycle in Bob's graph, so it's removable
126                removableEdges++;
127            }
128        }
129      
130        // Check if both graphs are fully connected (single component)
131        // Return -1 if either graph is not fully connected
132        return (aliceUnionFind.componentCount == 1 && bobUnionFind.componentCount == 1) 
133                ? removableEdges : -1;
134    }
135}
136
1class UnionFind {
2public:
3    int componentCount;  // Number of connected components
4
5    // Initialize Union-Find structure with n nodes
6    UnionFind(int n) {
7        parent = vector<int>(n);
8        componentSize = vector<int>(n, 1);
9        // Initialize each node as its own parent (self-loop)
10        iota(parent.begin(), parent.end(), 0);
11        componentCount = n;
12    }
13
14    // Unite two nodes and return true if they were in different components
15    bool unite(int nodeA, int nodeB) {
16        // Convert to 0-indexed and find roots
17        int rootA = find(nodeA - 1);
18        int rootB = find(nodeB - 1);
19      
20        // Already in the same component
21        if (rootA == rootB) {
22            return false;
23        }
24      
25        // Union by size: attach smaller tree under larger tree
26        if (componentSize[rootA] > componentSize[rootB]) {
27            parent[rootB] = rootA;
28            componentSize[rootA] += componentSize[rootB];
29        } else {
30            parent[rootA] = rootB;
31            componentSize[rootB] += componentSize[rootA];
32        }
33      
34        // Decrease component count after successful union
35        --componentCount;
36        return true;
37    }
38
39    // Find root of node with path compression
40    int find(int node) {
41        if (parent[node] != node) {
42            // Path compression: make every node point directly to root
43            parent[node] = find(parent[node]);
44        }
45        return parent[node];
46    }
47
48private:
49    vector<int> parent;        // Parent array for Union-Find
50    vector<int> componentSize; // Size of each component (for union by size)
51};
52
53class Solution {
54public:
55    int maxNumEdgesToRemove(int n, vector<vector<int>>& edges) {
56        // Create two separate Union-Find structures for Alice and Bob
57        UnionFind aliceUF(n);
58        UnionFind bobUF(n);
59        int removableEdges = 0;
60      
61        // Process Type 3 edges first (edges that both Alice and Bob can traverse)
62        for (auto& edge : edges) {
63            int type = edge[0];
64            int nodeU = edge[1];
65            int nodeV = edge[2];
66          
67            if (type == 3) {
68                // Try to unite nodes for Alice
69                if (aliceUF.unite(nodeU, nodeV)) {
70                    // If successful for Alice, also unite for Bob
71                    bobUF.unite(nodeU, nodeV);
72                } else {
73                    // Edge is redundant (nodes already connected)
74                    ++removableEdges;
75                }
76            }
77        }
78      
79        // Process Type 1 (Alice only) and Type 2 (Bob only) edges
80        for (auto& edge : edges) {
81            int type = edge[0];
82            int nodeU = edge[1];
83            int nodeV = edge[2];
84          
85            // Count redundant Type 1 edges for Alice
86            if (type == 1 && !aliceUF.unite(nodeU, nodeV)) {
87                ++removableEdges;
88            }
89          
90            // Count redundant Type 2 edges for Bob
91            if (type == 2 && !bobUF.unite(nodeU, nodeV)) {
92                ++removableEdges;
93            }
94        }
95      
96        // Check if both Alice and Bob can traverse the entire graph
97        // (graph is fully connected for both)
98        if (aliceUF.componentCount == 1 && bobUF.componentCount == 1) {
99            return removableEdges;
100        } else {
101            return -1;  // Graph cannot be fully traversed by both
102        }
103    }
104};
105
1// Parent array for Union-Find structure
2let parent: number[];
3// Size of each component (for union by size optimization)
4let componentSize: number[];
5// Number of connected components
6let componentCount: number;
7
8// Initialize Union-Find structure with n nodes
9function initializeUnionFind(n: number): void {
10    parent = new Array(n);
11    componentSize = new Array(n).fill(1);
12    componentCount = n;
13  
14    // Initialize each node as its own parent (self-loop)
15    for (let i = 0; i < n; i++) {
16        parent[i] = i;
17    }
18}
19
20// Find root of node with path compression
21function find(node: number): number {
22    if (parent[node] !== node) {
23        // Path compression: make every node point directly to root
24        parent[node] = find(parent[node]);
25    }
26    return parent[node];
27}
28
29// Unite two nodes and return true if they were in different components
30function unite(nodeA: number, nodeB: number): boolean {
31    // Convert to 0-indexed and find roots
32    const rootA = find(nodeA - 1);
33    const rootB = find(nodeB - 1);
34  
35    // Already in the same component
36    if (rootA === rootB) {
37        return false;
38    }
39  
40    // Union by size: attach smaller tree under larger tree
41    if (componentSize[rootA] > componentSize[rootB]) {
42        parent[rootB] = rootA;
43        componentSize[rootA] += componentSize[rootB];
44    } else {
45        parent[rootA] = rootB;
46        componentSize[rootB] += componentSize[rootA];
47    }
48  
49    // Decrease component count after successful union
50    componentCount--;
51    return true;
52}
53
54function maxNumEdgesToRemove(n: number, edges: number[][]): number {
55    // Create two separate Union-Find structures for Alice and Bob
56    // Save Alice's state first
57    initializeUnionFind(n);
58    const aliceParent = [...parent];
59    const aliceComponentSize = [...componentSize];
60    let aliceComponentCount = componentCount;
61  
62    // Initialize Bob's Union-Find
63    initializeUnionFind(n);
64    const bobParent = [...parent];
65    const bobComponentSize = [...componentSize];
66    let bobComponentCount = componentCount;
67  
68    let removableEdges = 0;
69  
70    // Process Type 3 edges first (edges that both Alice and Bob can traverse)
71    for (const edge of edges) {
72        const type = edge[0];
73        const nodeU = edge[1];
74        const nodeV = edge[2];
75      
76        if (type === 3) {
77            // Set Alice's state
78            parent = aliceParent;
79            componentSize = aliceComponentSize;
80            componentCount = aliceComponentCount;
81          
82            // Try to unite nodes for Alice
83            if (unite(nodeU, nodeV)) {
84                // Update Alice's state
85                aliceComponentCount = componentCount;
86              
87                // If successful for Alice, also unite for Bob
88                parent = bobParent;
89                componentSize = bobComponentSize;
90                componentCount = bobComponentCount;
91                unite(nodeU, nodeV);
92                bobComponentCount = componentCount;
93            } else {
94                // Edge is redundant (nodes already connected)
95                removableEdges++;
96            }
97        }
98    }
99  
100    // Process Type 1 (Alice only) and Type 2 (Bob only) edges
101    for (const edge of edges) {
102        const type = edge[0];
103        const nodeU = edge[1];
104        const nodeV = edge[2];
105      
106        // Count redundant Type 1 edges for Alice
107        if (type === 1) {
108            parent = aliceParent;
109            componentSize = aliceComponentSize;
110            componentCount = aliceComponentCount;
111          
112            if (!unite(nodeU, nodeV)) {
113                removableEdges++;
114            } else {
115                aliceComponentCount = componentCount;
116            }
117        }
118      
119        // Count redundant Type 2 edges for Bob
120        if (type === 2) {
121            parent = bobParent;
122            componentSize = bobComponentSize;
123            componentCount = bobComponentCount;
124          
125            if (!unite(nodeU, nodeV)) {
126                removableEdges++;
127            } else {
128                bobComponentCount = componentCount;
129            }
130        }
131    }
132  
133    // Check if both Alice and Bob can traverse the entire graph
134    // (graph is fully connected for both)
135    if (aliceComponentCount === 1 && bobComponentCount === 1) {
136        return removableEdges;
137    } else {
138        return -1;  // Graph cannot be fully traversed by both
139    }
140}
141

Time and Space Complexity

Time Complexity: O(E * α(N)) where E is the number of edges and N is the number of nodes. The α(N) is the inverse Ackermann function which grows extremely slowly and is practically constant (≤ 4) for all reasonable values of N.

  • The code iterates through all edges twice: once for type 3 edges and once for type 1 and 2 edges, giving us O(E) iterations total.
  • Each iteration performs union operations which involve find operations. With path compression in the find method, each find operation has an amortized time complexity of O(α(N)).
  • Therefore, the overall time complexity is O(E * α(N)), which is nearly O(E) in practice.

Space Complexity: O(N)

  • Two UnionFind data structures are created (ufa and ufb), each requiring O(N) space:
    • self.p: array of size N storing parent pointers
    • self.size: array of size N storing component sizes
    • self.cnt: single integer
  • The total space used is 2 * O(N) = O(N)
  • The recursion stack for the find operation with path compression can go up to O(N) in the worst case before path compression takes effect, but after compression, subsequent calls will be O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Processing Type 3 Edges Incorrectly

Pitfall: A common mistake is to independently check if a Type 3 edge is useful for Alice and Bob separately, which can lead to incorrectly counting removable edges.

Incorrect approach:

# WRONG: Independent checking
for edge_type, u, v in edges:
    if edge_type == 3:
        alice_useful = alice_uf.union(u, v)
        bob_useful = bob_uf.union(u, v)
        if not alice_useful and not bob_useful:
            removable_edges += 1

Why it's wrong: This approach processes the same edge twice independently. If the edge connects components in Alice's graph but not Bob's (or vice versa), we'd still keep it, but we've already modified both union-find structures.

Correct approach:

# CORRECT: Coordinated checking
for edge_type, u, v in edges:
    if edge_type == 3:
        if alice_uf.union(u, v):
            bob_uf.union(u, v)  # Only union in Bob's if useful for Alice
        else:
            removable_edges += 1  # Redundant for Alice means redundant for both

2. Not Processing Type 3 Edges First

Pitfall: Processing edges in the order they appear or processing type-specific edges before shared edges.

Why it matters: Type 3 edges are the most valuable because they maintain connectivity for both Alice and Bob simultaneously. By processing them first, we maximize the chance of using shared edges instead of person-specific edges, potentially allowing more edges to be removed.

Example scenario:

  • If nodes A and B can be connected by either a Type 1 edge or a Type 3 edge
  • Processing Type 1 first would use it for Alice, then still need the Type 3 for Bob
  • Processing Type 3 first satisfies both Alice and Bob, making the Type 1 edge removable

3. Incorrect Index Handling

Pitfall: Forgetting that the problem uses 1-indexed nodes while the Union-Find implementation typically uses 0-indexed arrays.

Wrong:

def union(self, node_a: int, node_b: int) -> bool:
    # WRONG: Using nodes directly without conversion
    root_a = self.find(node_a)
    root_b = self.find(node_b)

Correct:

def union(self, node_a: int, node_b: int) -> bool:
    # CORRECT: Convert from 1-indexed to 0-indexed
    root_a = self.find(node_a - 1)
    root_b = self.find(node_b - 1)

4. Misunderstanding Edge Redundancy

Pitfall: Thinking that an edge is removable just because there's another path between the nodes, without considering that removing it might disconnect other parts of the graph.

Key insight: The Union-Find approach correctly identifies redundant edges - an edge is only redundant if it connects two nodes that are already in the same connected component. This ensures that removing the edge won't affect connectivity.

5. Forgetting Final Validation

Pitfall: Returning the count of removable edges without checking if both graphs are fully connected.

Wrong:

# WRONG: Assuming graphs are connected
return removable_edges

Correct:

# CORRECT: Verify both graphs have exactly 1 component
if alice_uf.component_count == 1 and bob_uf.component_count == 1:
    return removable_edges
else:
    return -1

This validation is crucial because the initial graph might not have enough edges to make it fully traversable for both Alice and Bob, even without removing any edges.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Recommended Readings

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Graph Fundamentals

https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More