Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Redundant Connection

Explore how to identify and remove a redundant edge in an undirected graph to create a cycle-free tree. This lesson covers applying the Union Find algorithm to solve problems involving detecting cycles and ensuring connectivity in graphs.

We'll cover the following...

Statement

We’re given an undirected graph consisting of nn nodes. The graph is represented as an array called edges, of length nn, 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 treeA tree is an undirected graph that is connected and has no cycles. of nn nodes. If there are multiple candidates for removal, return the edge that occurs last in edges.

Constraints:

  • 3≤3 \leq nn ≤100\leq 100
  • edges.length== nn
  • edges[i].length == 2
  • 1≤1 \leq a << b ≤n\leq n
  • a≠ba \neq b
  • There are no repeated edges.
  • The given graph is connected.
  • The graph contains only one cycle.

Example

canvasAnimation-image
1 / 5

Understand the problem

Let’s take a moment to make sure we have correctly understood the problem. The quiz below helps us to check that we are solving precisely the right problem:

Redundant Connection

1.

What is the output if the following array of edges is provided as input?

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

A.

[2, 3]

B.

[3, 4]

C.

[1, 4]

D.

[1, 5]

1 / 2

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3

Try it yourself

Implement your solution in RedundantConnections.java in the following coding playground. You will need the provided supporting code to implement your solution.

Note: To solve this problem, you may need to change the implementation of the functions in the given Union Find class.

Java
usercode > RedundantConnections.java
/*
⬅️ We have provided a UnionFind.java file under the "Files" tab 
of this widget. You can use this file to build your solution.
*/
import java.util.*;
public class RedundantConnections{
    public static int[] redundantConnection(int[][] edges) {
        // Replace this placeholder return statement with your code
        return new int[]{};
    }
}
Redundant Connection