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

Redundant Connection

Explore the concept of Union Find to solve graph connectivity problems by identifying and removing redundant edges that create cycles. Understand how to ensure a graph becomes a tree by finding the edge that can be eliminated, and implement the solution effectively in JavaScript.

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.js 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.

JavaScript
usercode > main.js
/*

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

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

*/

import UnionFind from './union_find.js'



export function redundantConnection(edges){



   // Replace this placeholder return statement with your code

   return []

}
Redundant Connection