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

Redundant Connection

Understand how to solve the Redundant Connection problem by applying the Union Find data structure. Learn to detect cycles in an undirected graph, identify which edge can be removed to transform the graph into a tree, and implement a solution efficiently in Go.

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 main.go 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.

Go
usercode > main.go
/*

⬅️ We have provided a union_find.go file under the "Files" tab 

of this widget. You can use this file to build your solution.

*/

package main



func redundantConnections(edges [][]int) []int {



    // Replace this placeholder return statement with your code

    return make([]int, 0)

}
Redundant Connection