Redundant Connection

Q: What is the time complexity of Redundant Connection?

O(n α(n)). Each union and find operation runs in nearly constant amortized time due to path compression and union by rank optimizations, and all edges are processed once.

Q: What pattern does Redundant Connection use?

The Pattern: Union Find (Cycle Detection in Undirected Graph) The Heuristic: When detecting cycles in an undirected graph incrementally, use Union Find to track connected components; the first edge that connects two nodes already in the same set is the redundant edge creating a cycle.

Medium Graphs

Problem

Given a list of edges representing an undirected graph that started as a tree with one extra edge added, return the edge that can be removed to restore the tree structure.

3 ≤ edges.length ≤ 1000
edges[i].length == 2
1 ≤ ui, vi ≤ edges.length
ui != vi

Example

Input: edges = [[1,2],[1,3],[2,3]]

Output: [2,3]

The graph initially was a tree with edges [1,2] and [1,3]. Adding the edge [2,3] creates a cycle. The algorithm uses Union-Find to detect this cycle. It processes edges in order: union(1,2) succeeds, union(1,3) succeeds, but union(2,3) fails because 2 and 3 are already connected, indicating the edge [2,3] is redundant and should be returned.

Approach

Straightforward Solution

A brute-force approach would check for cycles after adding each edge using DFS or BFS, resulting in O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

A tree with n nodes has exactly n-1 edges and no cycles. Adding one extra edge creates exactly one cycle. Detecting this cycle is equivalent to finding the first edge that connects two nodes already in the same connected component.

Path to Optimal

The key recognition signals are 'detect cycle in undirected graph' and 'return redundant edge'. These indicate the Union-Find (Disjoint Set Union) pattern because it efficiently tracks connected components and detects cycles in near O(1) amortized time per union/find operation. By maintaining parent and rank arrays, the algorithm quickly determines if two nodes belong to the same set, signaling a cycle when attempting to union them.

Optimal Approach

Initialize Union-Find data structures with each node as its own parent and rank 1. For each edge, perform find operations to get the root parents of both nodes. If the roots are the same, the edge creates a cycle and is returned immediately. Otherwise, union the two sets by attaching the smaller rank tree under the larger rank tree and updating ranks accordingly. This approach guarantees O(n α(n)) time complexity, where α is the inverse Ackermann function, effectively linear for all practical input sizes.

Time

O(n α(n))

Each union and find operation runs in nearly constant amortized time due to path compression and union by rank optimizations, and all edges are processed once.

Space

O(n)

The parent and rank arrays each store one entry per node, scaling linearly with the number of nodes.

Pattern Spotlight

Union Find (Cycle Detection in Undirected Graph)

When detecting cycles in an undirected graph incrementally, use Union Find to track connected components; the first edge that connects two nodes already in the same set is the redundant edge creating a cycle.

Solution

1class Solution:
  def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
      par = [i for i in range(len(edges) + 1)]
      rank = [1] * (len(edges) + 1)
5
      def find(n):
          p = par[n]
          while p != par[p]:
              par[p] = par[par[p]]
              p = par[p]
          return p
12
      def union(n1, n2):
          p1, p2 = find(n1), find(n2)
          
          if p1 == p2:
              return False
          
          if rank[p1] > rank[p2]:
              par[p2] = p1
              rank[p1] += rank[p2]
          else:
              par[p1] = p2
              rank[p2] += rank[p1]
          return True
26
      for n1, n2 in edges:
          if not union(n1, n2):
              return [n1, n2]

1import java.util.*;
2
3class Solution {
  private int[] par;
  private int[] rank;
6
  public int[] findRedundantConnection(int[][] edges) {
      int n = edges.length;
      par = new int[n + 1];
      rank = new int[n + 1];
      for (int i = 0; i <= n; i++) {
          par[i] = i;
          rank[i] = 1;
      }
15
      for (int[] edge : edges) {
          int n1 = edge[0], n2 = edge[1];
          if (!union(n1, n2)) {
              return new int[]{n1, n2};
          }
      }
      return new int[0];
  }
24
  private int find(int x) {
      while (x != par[x]) {
          par[x] = par[par[x]];
          x = par[x];
      }
      return x;
  }
32
  private boolean union(int n1, int n2) {
      int p1 = find(n1);
      int p2 = find(n2);
      if (p1 == p2) {
          return false;
      }
      if (rank[p1] > rank[p2]) {
          par[p2] = p1;
          rank[p1] += rank[p2];
      } else {
          par[p1] = p2;
          rank[p2] += rank[p1];
      }
      return true;
  }
48}

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
  vector<int> findRedundantConnection(vector<vector<int>>& edges) {
      int n = edges.size();
      vector<int> par(n + 1), rank(n + 1, 1);
      for (int i = 0; i <= n; ++i) {
          par[i] = i;
      }
12
      auto find = [&](int x) {
          while (x != par[x]) {
              par[x] = par[par[x]];
              x = par[x];
          }
          return x;
      };
20
      for (auto& edge : edges) {
          int n1 = edge[0], n2 = edge[1];
          int p1 = find(n1);
          int p2 = find(n2);
          if (p1 == p2) {
              return edge;
          }
          if (rank[p1] > rank[p2]) {
              par[p2] = p1;
              rank[p1] += rank[p2];
          } else {
              par[p1] = p2;
              rank[p2] += rank[p1];
          }
      }
      return {};
  }
38};

1var findRedundantConnection = function(edges) {
  const n = edges.length;
  const par = new Array(n + 1);
  const rank = new Array(n + 1).fill(1);
  for (let i = 0; i <= n; i++) {
      par[i] = i;
  }
8
  function find(x) {
      while (x !== par[x]) {
          par[x] = par[par[x]];
          x = par[x];
      }
      return x;
  }
16
  for (const [n1, n2] of edges) {
      const p1 = find(n1);
      const p2 = find(n2);
      if (p1 === p2) {
          return [n1, n2];
      }
      if (rank[p1] > rank[p2]) {
          par[p2] = p1;
          rank[p1] += rank[p2];
      } else {
          par[p1] = p2;
          rank[p2] += rank[p1];
      }
  }
31};

Step-by-Step Solution

Initialize Union-Find Parent and Rank Arrays

3par = [i for i in range(len(edges) + 1)]
4rank = [1] * (len(edges) + 1)

Objective

To set up the data structures that track the connected components and their sizes for efficient union and find operations.

Key Insight

Initializing each node as its own parent represents that initially, all nodes are separate components. The rank array tracks the size or depth of each component, enabling union by rank to keep the tree shallow, which optimizes find operations. This setup is foundational for efficient cycle detection.

Interview Quick-Check

Core Logic

Parent array maps each node to its representative parent; rank array helps keep the union trees balanced.

Common Pitfalls & Bugs

Incorrect initialization of parent or rank arrays can cause incorrect cycle detection or inefficient unions.

Implement Find with Path Compression to Identify Root Parent

6def find(n):
  p = par[n]
  while p != par[p]:
      par[p] = par[par[p]]
      p = par[p]
  return p

Objective

To efficiently find the root parent of a node, compressing paths to speed up future queries.

Key Insight

Path compression flattens the tree structure by making each node on the find path point directly to the root parent. This optimization drastically reduces the time complexity of subsequent find operations, making the Union-Find operations nearly constant time on average.

Interview Quick-Check

Core Logic

Find traverses up the parent chain until it reaches the root, updating intermediate nodes to point directly to the root.

Common Pitfalls & Bugs

Failing to implement path compression leads to deeper trees and slower find operations.

Implement Union by Rank to Merge Sets and Detect Cycles

13def union(n1, n2):
  p1, p2 = find(n1), find(n2)
  
  if p1 == p2:
      return False
  if rank[p1] > rank[p2]:
      par[p2] = p1
      rank[p1] += rank[p2]
  else:
      par[p1] = p2
      rank[p2] += rank[p1]
  return True

Objective

To merge two disjoint sets efficiently and detect if adding an edge creates a cycle.

Key Insight

Union by rank attaches the smaller tree under the larger tree to keep the overall tree shallow, preserving efficient find operations. If the two nodes share the same root parent, union returns False, indicating a cycle caused by the current edge. This immediate detection allows returning the redundant edge without further processing.

Interview Quick-Check

Core Logic

Union compares root parents; if equal, a cycle is detected; otherwise, it merges sets by rank to maintain shallow trees.

State & Boundaries

Union returns False when a cycle is detected, True otherwise.

Common Pitfalls & Bugs

Not updating ranks correctly or merging without rank comparison can degrade performance.

Iterate Over Edges to Detect and Return the Redundant Connection

27for n1, n2 in edges:
28    if not union(n1, n2):
29        return [n1, n2]

Objective

To process each edge, performing union operations and returning the first edge that creates a cycle.

Key Insight

By iterating through edges in order, the algorithm ensures the first edge that connects two nodes already in the same set is identified as the redundant connection. Returning immediately upon detection avoids unnecessary work and guarantees the correct edge is returned as per problem constraints.

Interview Quick-Check

Core Logic

For each edge, attempt to union its nodes; if union fails, return the edge as it creates a cycle.

State & Boundaries

The loop terminates early upon finding the redundant edge, ensuring O(n) time.

Common Pitfalls & Bugs

Failing to return immediately upon cycle detection can lead to incorrect answers or unnecessary computation.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 3 Critical

par = [i for i in range(len(edges) + 1)]

Initialize the parent array where each node is its own parent.

This initialization represents that initially, each node is a separate connected component, which is essential for Union-Find to correctly track connectivity.

Line 4 Critical

rank = [1] * (len(edges) + 1)

Initialize the rank array with 1 for each node.

Rank tracks the size or depth of each component, enabling union by rank to keep trees balanced and optimize find operations.

Line 6 Standard

def find(n):

Define the find function to locate the root parent of a node.

Finding the root parent is fundamental to determining if two nodes belong to the same connected component.

Line 7 Standard

p = par[n]

Start with the parent of node n.

This sets up the traversal to find the root parent by following parent pointers.

Line 8 Standard

while p != par[p]:

Traverse up the parent chain until the root is found.

The loop continues until a node is its own parent, indicating the root of the connected component.

Line 9 Standard

par[p] = par[par[p]]

Apply path compression by linking the current node to its grandparent.

Path compression flattens the tree, reducing the depth and improving the efficiency of future find operations.

Line 10 Standard

p = par[p]

Move up one level in the parent chain.

This advances the traversal towards the root parent.

Line 11 Standard

return p

Return the root parent of the node.

Returning the root parent allows union operations to determine connectivity.

Line 13 Standard

def union(n1, n2):

Define the union function to merge two sets if they are disjoint.

Union attempts to connect two nodes and detect if they are already connected, which signals a cycle.

Line 14 Standard

p1, p2 = find(n1), find(n2)

Find the root parents of both nodes.

Determining root parents is necessary to check if nodes belong to the same set.

Line 15 Standard

Prepare to check if the nodes are already connected.

This sets up the condition to detect cycles.

Line 16 Standard

if p1 == p2:

Check if both nodes share the same root parent.

If they do, adding this edge would create a cycle, so union should fail.

Line 17 Standard

return False

Return False to indicate a cycle was detected.

Returning False signals the caller that the edge is redundant and should be returned.

Line 19 Standard

if rank[p1] > rank[p2]:

Compare ranks to decide which root becomes the parent.

Union by rank attaches the smaller tree under the larger to keep the tree shallow, optimizing future find operations.

Line 20 Standard

par[p2] = p1

Attach the root of the smaller tree to the root of the larger tree.

This merges the two sets while maintaining balanced tree structure.

Line 21 Standard

rank[p1] += rank[p2]

Update the rank of the new root to reflect the combined size.

Updating rank ensures accurate size tracking for future unions.

Line 22 Standard

else:

Handle the case where the second root has equal or larger rank.

This ensures union by rank is consistently applied regardless of which root is larger.

Line 23 Standard

par[p1] = p2

Attach the first root to the second root.

This merges the sets when the second root has equal or larger rank.

Line 24 Standard

rank[p2] += rank[p1]

Update the rank of the second root accordingly.

Maintains accurate rank information after union.

Line 25 Standard

return True

Return True to indicate a successful union without cycle.

Returning True signals that the edge connects two previously disconnected components.

Line 27 Standard

for n1, n2 in edges:

Iterate over each edge in the input list.

Processing edges in order allows detection of the first redundant edge that creates a cycle.

Line 28 Standard

if not union(n1, n2):

Attempt to union the two nodes of the current edge.

Union returns False if the edge creates a cycle, which identifies the redundant connection.

Line 29 Standard

return [n1, n2]

Return the current edge if it creates a cycle.

Returning immediately upon cycle detection ensures the correct redundant edge is identified as per problem requirements.

Test Your Understanding

Why does detecting that two nodes share the same root parent in Union Find indicate a cycle?

Because if two nodes have the same root parent, they are already connected in the graph; adding an edge between them creates a cycle by connecting nodes within the same connected component.

Don't just read it. Drill it.

Reconstruct Redundant Connection from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Redundant Connection drill

or drill a free problem

1	`class Solution:`
2	`def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:`
3	`par = [i for i in range(len(edges) + 1)]`
4	`rank = [1] * (len(edges) + 1)`
5
6	`def find(n):`
7	`p = par[n]`
8	`while p != par[p]:`
9	`par[p] = par[par[p]]`
10	`p = par[p]`
11	`return p`
12
13	`def union(n1, n2):`
14	`p1, p2 = find(n1), find(n2)`
15
16	`if p1 == p2:`
17	`return False`
18
19	`if rank[p1] > rank[p2]:`
20	`par[p2] = p1`
21	`rank[p1] += rank[p2]`
22	`else:`
23	`par[p1] = p2`
24	`rank[p2] += rank[p1]`
25	`return True`
26
27	`for n1, n2 in edges:`
28	`if not union(n1, n2):`
29	`return [n1, n2]`

1	`import java.util.*;`
2
3	`class Solution {`
4	`private int[] par;`
5	`private int[] rank;`
6
7	`public int[] findRedundantConnection(int[][] edges) {`
8	`int n = edges.length;`
9	`par = new int[n + 1];`
10	`rank = new int[n + 1];`
11	`for (int i = 0; i <= n; i++) {`
12	`par[i] = i;`
13	`rank[i] = 1;`
14	`}`
15
16	`for (int[] edge : edges) {`
17	`int n1 = edge[0], n2 = edge[1];`
18	`if (!union(n1, n2)) {`
19	`return new int[]{n1, n2};`
20	`}`
21	`}`
22	`return new int[0];`
23	`}`
24
25	`private int find(int x) {`
26	`while (x != par[x]) {`
27	`par[x] = par[par[x]];`
28	`x = par[x];`
29	`}`
30	`return x;`
31	`}`
32
33	`private boolean union(int n1, int n2) {`
34	`int p1 = find(n1);`
35	`int p2 = find(n2);`
36	`if (p1 == p2) {`
37	`return false;`
38	`}`
39	`if (rank[p1] > rank[p2]) {`
40	`par[p2] = p1;`
41	`rank[p1] += rank[p2];`
42	`} else {`
43	`par[p1] = p2;`
44	`rank[p2] += rank[p1];`
45	`}`
46	`return true;`
47	`}`
48	`}`

1	`#include <vector>`
2	`using namespace std;`
3
4	`class Solution {`
5	`public:`
6	`vector<int> findRedundantConnection(vector<vector<int>>& edges) {`
7	`int n = edges.size();`
8	`vector<int> par(n + 1), rank(n + 1, 1);`
9	`for (int i = 0; i <= n; ++i) {`
10	`par[i] = i;`
11	`}`
12
13	`auto find = [&](int x) {`
14	`while (x != par[x]) {`
15	`par[x] = par[par[x]];`
16	`x = par[x];`
17	`}`
18	`return x;`
19	`};`
20
21	`for (auto& edge : edges) {`
22	`int n1 = edge[0], n2 = edge[1];`
23	`int p1 = find(n1);`
24	`int p2 = find(n2);`
25	`if (p1 == p2) {`
26	`return edge;`
27	`}`
28	`if (rank[p1] > rank[p2]) {`
29	`par[p2] = p1;`
30	`rank[p1] += rank[p2];`
31	`} else {`
32	`par[p1] = p2;`
33	`rank[p2] += rank[p1];`
34	`}`
35	`}`
36	`return {};`
37	`}`
38	`};`

1	`var findRedundantConnection = function(edges) {`
2	`const n = edges.length;`
3	`const par = new Array(n + 1);`
4	`const rank = new Array(n + 1).fill(1);`
5	`for (let i = 0; i <= n; i++) {`
6	`par[i] = i;`
7	`}`
8
9	`function find(x) {`
10	`while (x !== par[x]) {`
11	`par[x] = par[par[x]];`
12	`x = par[x];`
13	`}`
14	`return x;`
15	`}`
16
17	`for (const [n1, n2] of edges) {`
18	`const p1 = find(n1);`
19	`const p2 = find(n2);`
20	`if (p1 === p2) {`
21	`return [n1, n2];`
22	`}`
23	`if (rank[p1] > rank[p2]) {`
24	`par[p2] = p1;`
25	`rank[p1] += rank[p2];`
26	`} else {`
27	`par[p1] = p2;`
28	`rank[p2] += rank[p1];`
29	`}`
30	`}`
31	`};`

6	`def find(n):`
7	`p = par[n]`
8	`while p != par[p]:`
9	`par[p] = par[par[p]]`
10	`p = par[p]`
11	`return p`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Union-Find Parent and Rank Arrays

Implement Find with Path Compression to Identify Root Parent

Implement Union by Rank to Merge Sets and Detect Cycles

Iterate Over Edges to Detect and Return the Redundant Connection

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.