Skip to main content
Talentd

Remove Max Number of Edges to Keep Graph Fully Traversable - Solution & Explanation

HardUnion FindGraph19 min readAsked at: Amazon, Meta, Uber +1
Practice this problem

Problem Statement

Alice and Bob have an undirected graph of n nodes and three types of edges:

  • Type 1: Can be traversed by Alice only.
  • Type 2: Can be traversed by Bob only.
  • Type 3: Can be traversed by both Alice and Bob.

Given an array edges where edges[i] = [typei, ui, vi] represents a bidirectional edge of type typei between nodes ui and vi, find the maximum number of edges you can remove so that after removing the edges, the graph can still be fully traversed by both Alice and Bob. The graph is fully traversed by Alice and Bob if starting from any node, they can reach all other nodes.

Return the maximum number of edges you can remove, or return -1 if Alice and Bob cannot fully traverse the graph.

 

Example 1:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]
Output: 2
Explanation: If we remove the 2 edges [1,1,2] and [1,1,3]. The graph will still be fully traversable by Alice and Bob. Removing any additional edge will not make it so. So the maximum number of edges we can remove is 2.

Example 2:

Input: n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]
Output: 0
Explanation: Notice that removing any edge will not make the graph fully traversable by Alice and Bob.

Example 3:

Input: n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]
Output: -1
Explanation: In the current graph, Alice cannot reach node 4 from the other nodes. Likewise, Bob cannot reach 1. Therefore it's impossible to make the graph fully traversable.

 

 

Constraints:

  • 1 <= n <= 105
  • 1 <= edges.length <= min(105, 3 * n * (n - 1) / 2)
  • edges[i].length == 3
  • 1 <= typei <= 3
  • 1 <= ui < vi <= n
  • All tuples (typei, ui, vi) are distinct.

Approach Overview

Problem Overview: You are given a graph where edges can be used by Alice, Bob, or both. The goal is to remove the maximum number of edges while ensuring both Alice and Bob can still traverse the entire graph. If either cannot reach all nodes, return -1.

Approach 1: Edge Removal with Connectivity Check (DFS/BFS) (Time: O(E * (V + E)), Space: O(V))

Start with the full graph and attempt removing each edge one by one. After removing an edge, run a connectivity check for Alice and Bob separately using DFS or BFS. If both graphs remain fully connected, the edge is unnecessary and can stay removed; otherwise restore it. This brute-force method works conceptually but is extremely expensive because each removal requires a full traversal of the graph. It demonstrates the problem constraint: connectivity must be preserved for two different users.

Approach 2: Union-Find with Prioritized Edge Inclusion (Time: O(E α(N)), Space: O(N))

The optimal solution treats the problem like a connectivity construction task. Use Union-Find (Disjoint Set Union) to track connected components. Edges of type 3 (usable by both Alice and Bob) provide the most value, so process them first and union nodes in both DSU structures simultaneously. Then process type 1 edges for Alice’s DSU and type 2 edges for Bob’s DSU. If a union operation fails because the nodes are already connected, the edge is redundant and can be counted as removable.

The key insight: prioritize shared edges to maximize reuse across both traversals. If you used separate edges first, you might miss opportunities where one edge satisfies both graphs. This greedy ordering guarantees the minimum edges required to keep both graphs connected. The algorithm relies on efficient component merging from graph connectivity theory and the near-constant amortized cost of DSU operations.

After processing all edges, verify that both DSU structures have exactly one connected component. If either graph is disconnected, return -1. Otherwise, the count of redundant edges represents the maximum number of removable edges.

Recommended for interviews: The Union-Find greedy strategy is the expected solution. Interviewers want to see you recognize the similarity to Kruskal-style edge selection and apply prioritized processing of shared edges. Mentioning the brute-force connectivity check shows understanding of the constraints, but implementing the optimized DSU approach demonstrates strong algorithmic design.

Approach 1: Union-Find with Prioritized Edge Inclusion

This approach utilizes the Union-Find (or Disjoint Set Union, DSU) data structure to manage the connectivity of nodes. The critical idea is to process edge types in a specific order to ensure that both Alice and Bob can fully traverse the graph while maximizing the number of removable edges:

  1. Process all type 3 edges first since they can be used by both Alice and Bob, reducing the total number of edges needed to ensure graph connectivity for both.
  2. Then process type 1 edges for Alice only and type 2 edges for Bob only.
  3. While processing, count only the edges that result in actual unions, hence contributing to the graph connectivity.
  4. Ensure after processing, both Alice’s and Bob’s components are fully connected individually.

This code defines a struct DSU representing the Disjoint-Set Union data structure for managing connected components. The functions createDSU, find, and unionSet handle initialization, set finding, and union operations, respectively.

The main function, maxNumEdgesToRemove, processes the edges by type. Type 3 edges are processed first because they serve both Alice and Bob. Then type 1 and 2 edges are processed separately for Alice’s and Bob’s connectivity. The variable savedEdges stores the number of redundant edges found. After processing, checking the number of connected components in alice and bob determines if the graph is fully traversable, and returns the maximum number of removable edges.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(E * α(n)), where E is the number of edges and α(n) is the inverse Ackermann function, effectively constant.
Space Complexity: O(n) for storing the disjoint sets for both Alice and Bob.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Union-Find with Prioritized Edge Inclusion

Time Complexity: O(E * α(n)), where E is the number of edges and α(n) is the inverse Ackermann function, effectively constant.
Space Complexity: O(n) for storing the disjoint sets for both Alice and Bob.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Edge Removal + DFS/BFS Connectivity CheckO(E * (V + E))O(V)Conceptual baseline or when demonstrating brute-force reasoning in interviews
Union-Find with Prioritized Edge InclusionO(E α(N))O(N)Optimal solution for large graphs; standard interview and competitive programming approach
Dual DSU with Kruskal-Style ProcessingO(E α(N))O(N)Alternative implementation of the same idea emphasizing MST-style edge selection

Video Solution

Remove Max Number Of Edges To Keep Graph Fully Traversable | Leetcode - 1579 | DSU | GOOGLE | Live • codestorywithMIK • 14,275 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Remove Max Number of Edges to Keep Graph Fully Traversable easy or hard?
This problem is categorized as Hard because it combines graph connectivity, greedy ordering, and Union-Find implementation. The tricky part is recognizing that shared edges must be processed first to maximize reuse between Alice and Bob's graphs.
Remove Max Number of Edges to Keep Graph Fully Traversable Python/Java solution
Implement two Union-Find structures: one for Alice and one for Bob. Process type 3 edges first and attempt union operations in both DSUs. Then process type 1 edges for Alice and type 2 edges for Bob. If a union fails because nodes are already connected, count that edge as removable.
How to solve Remove Max Number of Edges to Keep Graph Fully Traversable in O(n)?
The problem cannot be solved strictly in O(n) because every edge must be inspected. The closest optimal complexity is O(E α(N)) using Union-Find. Process shared edges first, union components for both Alice and Bob, then handle individual edges while counting redundant ones.
What is the best approach for Remove Max Number of Edges to Keep Graph Fully Traversable?
The best approach uses Union-Find (Disjoint Set Union) with prioritized edge processing. Type 3 edges that both Alice and Bob can use are processed first, then type 1 and type 2 edges for each user separately. This greedy ordering maximizes shared connectivity and identifies redundant edges efficiently. The overall complexity is O(E α(N)) time and O(N) space.
Is Remove Max Number of Edges to Keep Graph Fully Traversable asked at Google/Amazon/Meta?
Graph connectivity and Union-Find problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of disjoint sets, greedy edge selection, and connectivity validation. It is considered a strong signal question for graph fundamentals.
What data structure is used in Remove Max Number of Edges to Keep Graph Fully Traversable?
The core data structure is Union-Find (Disjoint Set Union). It efficiently tracks connected components while edges are added. Path compression and union by rank ensure near-constant time merges and lookups during graph construction.
What is the time complexity of Remove Max Number of Edges to Keep Graph Fully Traversable?
The optimal Union-Find solution runs in O(E α(N)) time, where α(N) is the inverse Ackermann function from path compression and union by rank. This is effectively constant for practical input sizes. Space complexity is O(N) for the disjoint set structures tracking connected components.

Ready to solve this problem?

Practice Remove Max Number of Edges to Keep Graph Fully Traversable with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Consecutive Sequence

Next

Surrounded Regions