What is the time complexity of Redundant Connection?

The optimal solution has a time complexity of O(n α(n)).

What data structures are used to solve Redundant Connection?

This problem uses Depth-First Search, Breadth-First Search, Union Find, Graph. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Redundant Connection?

Insight 1: The redundant edge is the one that introduces a cycle in the graph. Detecting cycles is crucial. Insight 2: Union Find (Disjoint Set) data structure is an efficient way to detect cycles in a graph. It maintains connected components and can quickly determine if adding an edge would connect two already connected components, thus forming a cycle.

Which companies ask LeetCode 684. Redundant Connection in interviews?

This problem is frequently asked at Box, InMobi.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Redundant Connection - LeetCode 684 Solution

Redundant Connection - Complete Solution Guide

Redundant Connection is LeetCode problem 684, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

In this problem, a tree is an undirected graph that is connected and has no cycles. You are given a graph that started as a tree with n nodes labeled from 1 to n , with one additional edge added. The added edge has two different vertices chosen from 1 to n , and was not an edge that already existed. The graph is represented as an array edges of length n where edges[i] = [a i , b i ] indicates that there is an edge between nodes a i and b i in the graph. Return an edge that can be removed so that

Detailed Explanation

The problem asks us to find the redundant edge in a graph that was initially a tree (a connected graph with no cycles) to which one extra edge has been added. This extra edge creates a cycle, and we need to identify which edge, if removed, would restore the tree structure. If multiple edges could be removed to form a tree, the problem specifies that we should return the edge that appears latest in the input list of edges. The input is given as a list of edges, where each edge is a pair of node numbers [a, b], indicating an undirected connection between nodes 'a' and 'b'. The node numbers range from 1 to n, where n is the number of nodes and also the number of edges in the input. The graph is guaranteed to be connected before the extra edge is added.

Solution Approach

The solution uses the Union Find algorithm (also known as the Disjoint Set Union algorithm) to detect cycles in the graph. The core idea is to represent each node as a set. When an edge (u, v) is encountered, we check if nodes u and v belong to the same set. If they do, it means adding this edge would create a cycle because they are already connected. If they don't, we merge the sets containing u and v to indicate they are now connected. The first edge that causes a cycle is the redundant edge.

Step-by-Step Algorithm

Step 1: Initialize a `parent` array where `parent[i] = i` for all nodes from 1 to n. This means each node initially forms its own disjoint set.
Step 2: Initialize a `rank` array with all elements set to 0. This array is used for optimizing the Union Find operations by attaching smaller trees to the root of larger trees.
Step 3: Iterate through the given list of edges.
Step 4: For each edge (u, v), find the root (representative) of the sets containing u and v using the `find` operation with path compression. Path compression optimizes the find operation by flattening the tree structure.
Step 5: Use `union` operation to merge the sets of u and v. This function returns `true` if the sets were successfully merged (no cycle formed) and `false` if u and v were already in the same set (cycle formed).
Step 6: If the `union` operation returns `false`, it means adding the current edge (u, v) would create a cycle. Return this edge as the redundant edge.
Step 7: If the loop finishes without finding a redundant edge, it indicates an error (as the problem statement guarantees one redundant edge exists). In the code, in this scenario an empty list/array is returned but for the given problem description, this code should not be reached.

Key Insights

Insight 1: The redundant edge is the one that introduces a cycle in the graph. Detecting cycles is crucial.
Insight 2: Union Find (Disjoint Set) data structure is an efficient way to detect cycles in a graph. It maintains connected components and can quickly determine if adding an edge would connect two already connected components, thus forming a cycle.
Insight 3: The problem specifies that if there are multiple possible edges, return the one that appears latest. The provided solution naturally handles this by iterating through the edges in the given order and returning the first edge that causes a cycle.

Complexity Analysis

Time Complexity: O(n α(n))

Space Complexity: O(n)

Topics

This problem involves: Depth-First Search, Breadth-First Search, Union Find, Graph.

Companies

Asked at: Box, InMobi.

Redundant Connection | LeetCode 684

Medium

Depth-First Search Breadth-First Search Union Find Graph

Time: O(n α(n))Space: O(n)

Solution Code

Available in:

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        int[] parent = new int[n + 1];
        int[] rank = new int[n + 1];

        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }

        for (int i = 0; i <= n; i++){
            rank[i] = 0;
        }
        

        function find = (i) => {
            if (parent[i] == i) {
                return i;
            }
            parent[i] = find(parent[i]);
            return parent[i];
        };

        function union = (i, j) => {
            int root_i = find(i);
            int root_j = find(j);
            
            if (root_i != root_j) {
                if (rank[root_i] < rank[root_j]) {
                    parent[root_i] = root_j;
                } else if (rank[root_i] > rank[root_j]) {
                    parent[root_j] = root_i;
                } else {
                    parent[root_j] = root_i;
                    rank[root_i]++;
                }
                return true;
            } else {
                return false;
            }
        };
        
        function find = (i) => {
            if (parent[i] == i){
                return i;
            }
            parent[i] = find(parent[i]);
            return parent[i];
        };

        function union = (i, j) => {
            int root_i = find(i);
            int root_j = find(j);

            if (root_i != root_j){
                if(rank[root_i] < rank[root_j]){
                    parent[root_i] = root_j;
                } else if (rank[root_i] > rank[root_j]) {
                    parent[root_j] = root_i;
                } else {
                    parent[root_j] = root_i;
                    rank[root_i]++;
                }
                return true;
            } else {
                return false;
            }
        };

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            
            if (!union(u, v)) {
                return new int[]{u, v};
            }
        }

        return new int[0]; // Should not reach here if the input is valid
    }

    private int find(int i, int[] parent) {
        if (parent[i] == i) {
            return i;
        }
        parent[i] = find(parent[i], parent);
        return parent[i];
    }

    private boolean union(int i, int j, int[] parent, int[] rank) {
        int root_i = find(i, parent);
        int root_j = find(j, parent);

        if (root_i != root_j) {
            if (rank[root_i] < rank[root_j]) {
                parent[root_i] = root_j;
            } else if (rank[root_i] > rank[root_j]) {
                parent[root_j] = root_i;
            } else {
                parent[root_j] = root_i;
                rank[root_i]++;
            }
            return true;
        } else {
            return false;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 684: Redundant Connection - Detailed explanation and solution approaches.

Topics

Depth-First Search Breadth-First Search Union Find Graph

Companies

BoxInMobi

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:684

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Initialize a `parent` array where `parent[i] = i` for all nodes from 1 to n. This means each node initially forms its own disjoint set.
2
Step 2: Initialize a `rank` array with all elements set to 0. This array is used for optimizing the Union Find operations by attaching smaller trees to the root of larger trees.
3
Step 3: Iterate through the given list of edges.
4
Step 4: For each edge (u, v), find the root (representative) of the sets containing u and v using the `find` operation with path compression. Path compression optimizes the find operation by flattening the tree structure.
5
Step 5: Use `union` operation to merge the sets of u and v. This function returns `true` if the sets were successfully merged (no cycle formed) and `false` if u and v were already in the same set (cycle formed).
6
Step 6: If the `union` operation returns `false`, it means adding the current edge (u, v) would create a cycle. Return this edge as the redundant edge.
7
Step 7: If the loop finishes without finding a redundant edge, it indicates an error (as the problem statement guarantees one redundant edge exists). In the code, in this scenario an empty list/array is returned but for the given problem description, this code should not be reached.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n α(n))

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by iterating through the edges once (O(n)) and performing Union Find operations for each edge. Each Union Find operation takes O(α(n)) on average due to path compression and rank optimization. The space complexity is determined by the size of the `parent` and `rank` arrays, which are both of size n+1.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

We can use DFS to detect cycles. For each edge, temporarily remove it and check if the graph remains connected using DFS. If the graph becomes disconnected, then the removed edge is crucial and not redundant. If the graph remains connected after removing the edge, it means there is another path between the nodes, so the removed edge forms a cycle and is the redundant edge. Perform this operation for each edge and select the last redundant edge detected.

Time: O(n^2), where n is the number of nodes. We perform DFS n times, and each DFS can take O(n) time.Space: O(n) for the DFS stack and visited set.

Trade-offs: DFS is more intuitive to understand, but it has a higher time complexity than the Union Find approach. The Union Find solution is generally preferred for its better performance, especially for larger graphs.

✨

Key Insights

1Insight 1: The redundant edge is the one that introduces a cycle in the graph. Detecting cycles is crucial.
2Insight 2: Union Find (Disjoint Set) data structure is an efficient way to detect cycles in a graph. It maintains connected components and can quickly determine if adding an edge would connect two already connected components, thus forming a cycle.
3Insight 3: The problem specifies that if there are multiple possible edges, return the one that appears latest. The provided solution naturally handles this by iterating through the edges in the given order and returning the first edge that causes a cycle.

📚

Key Terms Explained

For Students

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: Input graph is already a tree. The problem states that the input graph is a tree with one additional edge added, so this case will not occur.
Edge case 2: Self-loops (an edge from a node to itself). The problem constraints state that a<sub>i</sub> != b<sub>i</sub>, so there are no self-loops to consider.
Edge case 3: Multiple possible redundant edges. The solution correctly identifies the redundant edge that occurs *last* in the input order. The problem statement requires the algorithm to return the redundant edge that appears latest. Because we iterate through edges in their provided order, we stop at the *first* redundant edge, which necessarily is also the *last* (or latest).

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting path compression in the `find` operation, or neglecting rank optimization in the `union` operation. This can lead to a much worse time complexity (O(n log n) instead of O(n α(n))).

✗Common mistake 2: Not initializing the `parent` array correctly, leading to incorrect results. Ensure each node is initially its own parent before starting the Union Find process.

✗Common mistake 3: Not understanding the subtle differences between the 'find' and 'union' operations and incorrectly implementing them. Ensure the root nodes are being compared and that parent pointers are updated correctly during the union operation.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Network connectivity analysis. Determining if adding a new connection to a network would create a loop, which can cause issues like broadcast storms.

🏦Real-world scenario 2: Detecting cycles in dependency graphs. For example, in software engineering, this could be used to identify circular dependencies between modules, which can prevent compilation or lead to runtime errors.

🎮Real-world scenario 3: Social network analysis. Identifying redundant connections in social networks to optimize recommendations or understand relationships between users.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Always test your solution with edge cases: empty input, single element, and boundary values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 23, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 14

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 7

❓

Frequently Asked Questions

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Redundant Connection"?

For this medium-level Depth-First Search problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether breadth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?