Remove Max Number of Edges to Keep Graph Fully Traversable

Remove Max Number of Edges to Keep Graph Fully Traversable

What is this problem about?

The Remove Max Number of Edges to Keep Graph Fully Traversable interview question gives you a graph with n nodes and three types of edges: Type 1 (only Alice can use), Type 2 (only Bob can use), and Type 3 (both can use). You want to keep the graph fully traversable by both Alice and Bob — meaning each can reach all nodes from any starting point — while removing the maximum number of redundant edges. The goal is to return the count of edges that can be removed, or -1 if full traversal is impossible even with all edges present.

Why is this asked in interviews?

This HARD problem is asked at Uber, DE Shaw, Meta, Google, and Adobe because it requires understanding Union-Find (Disjoint Set Union) and applying it to two parallel graph instances simultaneously. It tests a candidate's ability to recognize that shared edges (Type 3) should be prioritized and that redundant edges within each traversal can be safely discarded. Graph connectivity and greedy edge selection are fundamental to system design problems in networking and distributed systems.

Algorithmic pattern used

The pattern is greedy Union-Find with two DSU instances. Maintain two separate DSU structures — one for Alice and one for Bob. Process Type 3 edges first (they benefit both): for each Type 3 edge, attempt to union in both DSU structures. If it was redundant in BOTH (neither union changed anything), count it as removable. Then process Type 1 edges using only Alice's DSU, and Type 2 edges using only Bob's DSU, similarly counting redundant ones. At the end, verify both DSUs are fully connected.

Example explanation

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

• Type 3: (1,2) — union both DSUs. Not redundant.
• Type 3: (2,3) — union both DSUs. Not redundant.
• Type 1: (1,3) — Alice's DSU: 1 and 3 already connected (via Type 3 edges). Redundant → remove.
• Type 2: (2,4) — Bob's DSU: union 2 and 4. Not redundant.

Removable edges: 1. Both Alice and Bob can reach all 4 nodes. Answer: 1.

Common mistakes candidates make

• Processing Type 1 and Type 2 edges before Type 3 — this misses optimization opportunities since shared edges cover more.
• Using a single DSU for both Alice and Bob instead of two separate ones.
• Forgetting to check full connectivity after all union operations, leading to incorrect answers of -1.
• Counting an edge as removable only if it's redundant in one DSU but not realizing it must be redundant in both for Type 3 edges.

Interview preparation tip

For the Remove Max Number of Edges to Keep Graph Fully Traversable coding problem, the Union-Find graph interview pattern is central. Practice implementing a DSU with path compression and union by rank before the interview. The greedy insight — prioritize Type 3 edges — is what separates good solutions from great ones. Interviewers at Uber and Adobe value candidates who can explain the greedy reasoning clearly: shared edges maximize connectivity gain per edge kept.