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

0% completed

Solution: Redundant Connection

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:

.....

.....

.....

Like the course? Get enrolled and start learning!