LeetCode 1579. Remove Max Number of Edges to Keep Graph Fully Traversable - solution with TypeScript

Daily LeetCode Challenge: Day 117: leetcode.com/problems/remove-...
GitHub: github.com/RuslanTsykaliak/Le...
When I first read the problem, I realized that the key to solving it lies in efficiently managing the connectivity of the graph for both Alice and Bob. Since there are three types of edges, we need to carefully choose which edges to keep and which ones to remove while ensuring that both Alice and Bob can still traverse the entire graph. The Union-Find data structure is perfect for this task as it helps manage connected components efficiently.
Approach
To solve the problem, we use the following approach:
Union-Find Data Structure: We use two instances of the Union-Find data structure, one for Alice and one for Bob. This helps us keep track of the connected components for both Alice and Bob separately.
Sort Edges: We sort the edges in descending order of their types. This way, we process type 3 (common) edges first, as they are the most beneficial for both Alice and Bob.
Process Edges: We iterate through the sorted edges and perform union operations:
For type 3 edges, we attempt to connect nodes in both Alice's and Bob's graphs.
For type 1 edges, we connect nodes only in Alice's graph.
For type 2 edges, we connect nodes only in Bob's graph.
Count Edges Used: We keep a count of the edges used during the union operations.
Final Check: After processing all edges, we check if both Alice and Bob have a single connected component (i.e., they can traverse the entire graph). If they do, we return the number of edges that can be removed. If not, we return -1.
Hashtags: #LeetCode #RemoveMaxNumberOfEdges #Problem1579 #Coding #Programming #TypeScript #JavaScript #Algorithm #DataStructures #ProblemSolving #UnionFind #DisjointSet #GraphTheory #CodingTutorial #CodingChallenge #DailyLeetCodeChallenge #day117 #RuslanTsykaliak #CodeExplanation #JunLeetCodeChallenge