Solution: Redundant Connection
Let's solve the Redundant Connection problem using the Union Find pattern.
Statement
We’re given an undirected graph consisting of nodes. The graph is represented as an array called edges
, of length , where edges[i] = [a, b]
indicates that there is an edge between nodes a
and b
in the graph.
Return an edge that can be removed to make the graph a edges
.
Constraints:
edges.length
edges[i].length
2-
a
b
- There are no repeated edges.
- The given graph is connected.
- The graph contains only one cycle.
Solution
So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
We can solve this problem using techniques like DFS or BFS, however, the naive approach using DFS or BFS has a time complexity of in the worst-case scenario. This is because the DFS or BFS algorithm will explore the graph by visiting each node and its edges, which may result in visiting many nodes multiple times, and not necessarily finding the redundant connection in an efficient manner.
Optimized approach using union find
We are going to solve this problem with the help of the union find pattern and will be using union by rank and path compression.
-
Union by rank: We connect the nodes that come afterward to the nodes that came before them. This allows us to add new nodes to the subset of the representative node of the larger connected component. Using ranks to connect nodes in this manner helps reduce the depth of the recursion call stack of the
find
function, since the trees within each disjoint set remain relatively shallow. -
Path compression: On each
find
operation on a node of a tree, we update the parent of that node to point directly to the root. This reduces the length of the path of that node to the root, ensuring we don’t have to travel all the intermediate nodes on futurefind
operations.
The slides below illustrate how the algorithm runs:
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.