Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Redundant Connection (medium)
On this page

Problem Statement

Examples

Try it yourself

Problem Statement

Given an undirected graph containing 1 to n nodes. The graph is represented by a 2D array of edges, where edges[i] = [a<sub>i</sub>, b<sub>i</sub>], represents an edge between a<sub>i</sub>, and b<sub>i</sub>.

Identify one edge that, if removed, will turn the graph into a tree.

A tree is a graph that is connected and has no cycles.

Assume that the graph is always reducible to a tree by removing just one edge.

If there are multiple answers, return the edge that occurs last in the input.

Examples

  1. Example 1:
    • Input: [[1,2], [1,3], [3,4], [1,4], [1,5]]
Image
  • Expected Output: [1,4]
    • Justification: The edge [1,4] is redundant because removing it will eliminate the cycle 1-3-4-1 while keeping the graph connected.
  1. Example 2:
    • Input: [[1,2], [2,3], [3,1], [3,4]]
Image
  • Expected Output: [3,1]
  • Justification: The edge [3,1] creates a cycle 1-2-3-1. Removing it leaves a tree with no cycles.
  1. Example 3:
    • Input: [[1,2], [2,3], [3,4], [4,2], [5,6]]
Image
  • Expected Output: [4,2]
  • Justification: The edge [4,2] adds a cycle 2-3-4-2 in one part of the graph. Removing this edge breaks the cycle, and the remaining graph is a tree.

Constraints:

  • n == edges.length
  • 3 <= n <= 1000
  • edges[i].length == 2
  • 1 <= a<sub>i</sub> < b<sub>i</sub> <= edges.length
  • a<sub>i</sub> != b<sub>i</sub>
  • There are no repeated edges.
  • The given graph is connected.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

On this page

Problem Statement

Examples

Try it yourself