Redundant Connection - Union Find - Leetcode 684 - Python 

💡 GRAPH PLAYLIST: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-EgI5nU9etnU.html

DFS can be O(N) and >90%. I wouldn't recommend learning rare patterns by heart if not required. My solution uses a dict instead of a set to find the cycle because it preserves insertion order and is also O(1) to delete/add/find: adj_list, cycle = {}, {} for a,b in edges: adj_list.setdefault(a,[]).append(b) adj_list.setdefault(b,[]).append(a) def dfs(node, parent): if node in cycle: for k in list(cycle.keys()): if k == node: return True del cycle[k] cycle[node] = None for child in adj_list[node]: if child != parent and dfs(child,node): return True del cycle[node] return False dfs(edges[0][0],-1) for a,b in edges[::-1]: if a in cycle and b in cycle: return (a,b)

The explanation keeps getting better 🔥 BRO!

Thanks for the video! Wondering if there could also be a DFS version of this video since it would follow what was previously done in course schedule 1 and 2, somewhat creating a template kind of answer and building up on it

Great job explaining this! I finally understand it.

This is the best channel, your explanation is great and code is clear. Keep it up

very good explanation, thanks for the idea

I am really grateful that you have explained the Union Find Algo brilliantly using this example. Thanks buddy 😄👍👍

Wow, very clear explanation ~ help me a lot, TY!

Thank you mate, you are great!

This dude is changing lives. I wonder if he grasps the full extent of it.

Thank you so much for proving best explanation ever

Thank you so much. I learnt union find because of you.

This is so easy to understand! But could you also cover 685. redundant connection II and compare these two..?

12:20 the path compression doesn't make par[n] point to the ultimate root parent of the sub-tree, it only makes its parent, par[par[n]] have this property, because you used par[p] = par[par[p]], where p is initially = par[n]. Ideally, you want all intermediate parents to point to the root parent, but the code skips one level. Interesting to compare with ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-8f1XPm4WOUc.html, where you do it correctly, by changing L7 (first line under find()) to be p = n. In this way, you don't skip one level.

great tutorial....thanks :)

Can also construct the disjoint set DS with negative values meaning parents, and absolute value in the parent as the number of nodes in that disjoint set.

At 12:45: wouldn't your path compression code only shorten the links (up to the root) by 1? For example if we have: 5 -> 4 -> 3 -> 2 -> 1, where 1 is the root and we call find() on 5. At the end of your find() function, I believe the parent of 5 will be 3, not 1, is that correct?

Nice Explanation

Great video!

Thanks!

@Neetcode At 14:15, did you take care of the cases where the rank of both are the same?

The path compression you have done looks like return par[par[par[n]]]; I think the find function should be implemented recursively to update the parents for each node in the root. Also, the question asks to return the edge that satisfies the condition and is nearer to the end of the input array, has it been done above? Please let me know if I'm missing something.

Hi @neetcode, Is in the worst case O(nlogn) time will take this approach because of find operation? Please correct me if am wrongly analysis

Awesome explanation

I think you can do O(N) with DFS. You shouldn't tackle the problem "which edge should we add?" You should tackle the problem: "traverse the whole graph, find all the edges part of a cycle and then figure out which one is the last edge from the input." Traversing the whole graph while finding all the edges part of a cycle is O(V+E). Figuring out which edge is the last one is O(E) thanks to storing the edges that are part of a cycle in a cycle set. I use a stack and a set combined to keep track of the cycle path. I keep the edges that are part of a cycle stored in a set and then I just iterate from the last input edge towards the first input edge and check my cycle set. That should be O(V+E) The JavaScript code is a bit messy, I'll refactor it for more learnings. I use closures a lot so I can have "scoped globals". It means I don't need to worry about return semantics, I can just store whatever result I need in my "scoped global". /** * @param {number[][]} edges * @return {number[]} */ var findRedundantConnection = function(edges) { const cycleSet = new Set() //stores edges found in cycles //create adjacency list const adjList = {} for (const [source, dest] of edges) { adjList[source] = new Set() adjList[dest] = new Set() } for (const [source, dest] of edges) { adjList[source].add(dest) adjList[dest].add(source) } const visited = new Set() findCycles(1) //assuming graph is connected for (let i = edges.length - 1; i >= 0; i--) { const edgeKey = edges[i].sort((a, b) => a - b).join(',') if (cycleSet.has(edgeKey)) return edges[i] } return //done function findCycles(node) { const pathSet = new Set() const pathStack = [] dfs(node) function dfs(node) { if (pathSet.has(node)) { //cycle found const last = pathStack[pathStack.length - 1] const edge = [last, node].sort((a, b) => a - b).join(',') if (pathStack.length === 1) return cycleSet.add(edge) for (let i = pathStack.length - 1; i >= 0; i--) { const prev = pathStack[i-1] const curr = pathStack[i] if (curr === node) break const edgeKey = [prev, curr].sort((a, b) => a - b).join(',') cycleSet.add(edgeKey) } return } if (visited.has(node)) return pathSet.add(node) pathStack.push(node) visited.add(node) for (const neighbor of adjList[node] ) { adjList[neighbor].delete(node) dfs(neighbor) } pathSet.delete(node) pathStack.pop() } } };

i got it. you are right. Sorry about the misception

Hey! Why are we connecting subtree root having a lesser rank with another having larger? Can't we connect opposite of this?

@neetcode is there any other video of yours that you would recommend to watch union find? I feel like union find is not explained in detail very much in this video.

Here is the simplified C++ version, the core idea is to find the redundant, and we don't really need the rank here: Hope it helps vector findRedundantConnection(vector& edges) { vector parent(edges.size() + 1, -1); for (auto e: edges) { int x = findRoot(e[0], parent); int y = findRoot(e[1], parent); // find cycle if (x == y) { return {e[0], e[1]}; } else { parent[y] = x; } } return {}; } int findRoot(int n, const vector& parent) { return parent[n] == -1 ? n : findRoot(parent[n], parent); }

oh, i get it, there is a condition that two nodes have the same parent which leads to a cycle by connecting them since they form a triangle.

@Neetcode At 14:15 why did you use rank[p1] += rank[p2] instead of rank[p1] += 1?

best channel forever

@Neetcode, can you explain this to me please? The code for path compression in recursive format is def find(n): if par[n] != n: par[n] = find(par[n]) return par[n] In iterative format like the one you did with while loop, shouldn't it be def find(n): while n != par[n]: par[n] = par[par[n]] n = par[n] return par[n]

You could implement edge compression in the find() function to make it more efficient. If you have a long path parent

At 3:14, he added 4 to the graph but that was not possible. The question said the graph was a tree with out cycle before adding an extra edge. The extra edge had to choose two nodes from an already existed list. You cant just add a 4? I am reading the question correctly?

This solution is easier to understand, hope it helps. class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: # variables n = len(edges) parents = [i for i in range(n + 1)] def find_group_root(node): group_root = node while group_root != parents[group_root]: group_root = parents[group_root] return group_root for v1, v2 in edges: group_root1 = find_group_root(v1) group_root2 = find_group_root(v2) if group_root1 == group_root2: return [v1, v2] # union two groups parents[group_root2] = group_root1

Two easier approaches to that 'find' function: (TypeScript) //1 function findParent(node: number): number { if (node != par[node]) return findParent(par[node]) else return node; } //2 function findParent(node: number): number { while (node != par[node]) { node = par[node] } return node; }

Thanks

thanks

thanks for video. Nice explanation. path compression can be improved here. def find(self, p): if self.parent[p] != p: self.parent[p] = self.find(self.parent[p]) # Path compression return self.parent[p]

Omg I'm terrified. What a coincidence. I have a SC interview in a week. 😭

is keeping track of rank necessary? This solution works for me: class Solution: def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: parent = list(range(len(edges) + 1)) def find(x): if x != parent[x]: parent[x] = find(parent[x]) return parent[x] def union(x, y): rootX, rootY = find(x), find(y) if rootX == rootY: return [x, y] parent[rootX] = rootY for x, y in edges: if union(x, y): return [x, y]

very nice

what is the time and space complexity here @NeetCode ?

Thanks for the video. I am one comment regarding the rank array. Do we really need the rank array for this problem specifically? As we already know there's one solution and return the first redundant edge. So we can return the redundant edge at the union method when we find p1 == p2. Please let me know if that's the case.

So when we updating the parent we are actually updating the parent of the updating node to point parent of other node . this took me a while to understand since it is not seen every testcase simpler solution class Solution { int[] par; int[] rank; public int[] findRedundantConnection(int[][] edges) { int n = edges.length; par = new int[n + 1]; rank = new int[n + 1]; for (int i = 1; i 0) { n = par[n]; } return n; } public boolean union(int n1, int n2) { int p1 = find(n1); int p2 = find(n2); if (p1 == p2) { return false; // Already in the same set } if (rank[p1] > rank[p2]) { par[p2] = p1; rank[p1] += rank[p2]; } else { par[p1] = p2; rank[p2] += rank[p1]; } return true; // Successfully unioned } }

why is the result guaranteed to be the last redundant edge in the input?

What an explanation 😃

Can we apply union find for both directed and undirected graphs?

create a hashset to remember nodes, and just go through the edges array, and check whether both the two nodes are in the hashset, if not just add them, if yes, then that is the edge that is causing the issue?

thaank

Looks like you don't need ranks for this particular problem

How would. you explain the time complexity for this problem during an interview?

mmmm i didn't feel like the ranks and compressed path-find were elements of the resolution and the algorithm kinda works just fine without them? I think it feels simpler without them wdyt? def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: n = len(edges) par = [i for i in range(n+1)] def find(n): p = par[n] while par[p]!=p: p = par[p] return p def union(n1,n2): p1,p2 = find(n1), find(n2) if p1==p2: return False par[p2] = p1 return True for a,b in edges: if not union(a,b): return [a,b]

Excellent video. We don't need to do par[p] = par[par[p]] while n!=par[n] n = par[n] return n would suffice too

How is this O(n) though ? As we are looping through every edge we are using find function which has a while loop. Shoudn't it be O(n^2) ?

Is time complexity O(nlogn) and Space Complexity O(n)?

So I'm getting ready for an interview and try to find the time complexity. I think he forgot to mention it. In this case the find function is O(logV) because of the line 9, where we assign the grandparent to the current parent, so we shorten the search. Otherwise it works without that line, but then the time complexity would be O(V). So due to it, the time complexity of finding the redundant connection is O(ElogV).

i have a request i love your solutions, and they perhaps are intuitive, but i have trouble coming to the solutions myself, i mean can you feature more hints that you pick up when reading a question that helps you come up with the solution, somthing like, oh the question is asking for unique entries in the answer perhaps we can just use a set, this is just an example but you get what i mean?

Correct "Path compression" code alternatives here: 1. Recursive: def find(node): if par[node] != node: par[node] = find(par[node]) # Path compression, 1 line recursive return par[node] 2. Iterative: def find(node): root = node while root != par[root]: root = par[root] while root != node: # Path compression, while loop nxt = par[node] par[node] = root node = nxt return root

feels like you jumped a bit too much on this one man.

I think this should be a hard problem.

if would just add - if par[par[p]]: par[p] = par[par[p]] on row 9.

Hi there, thanks for the video explanations which help a lot. Am I right that you have mentioning n_edges == n_nodes leads a cycle? I doubt it since for n_edges == n_nodes == 5, we can have a disconnected graph.

Pre-req to solve this problem: Know union() and find(), know union find by rank, know Path compression Also isn't it UNION BY SIZE instead of UNION BY RANK? Because we are using size of disjoint sets/ trees and not height/ depth

This part is very confusing: while p!= par[p]: par[p] = par[par[p]] p = par[p]

def find(x): if par[x] != x: return find(par[x]) else: return x

685. Redundant Connection II

Here's the summary I wrote out for my Anki flashcard in case anyone else finds it helpful: --- union-find Explanation via analogy: imagine you have chopsticks and Play-Doh balls with alphabetical letters on them, and you have a list of instructions that specify two balls to connect via a chopstick, similar to the instructions in a Lego kit. You will connect two Play-Doh balls with a chopstick as you read each new instruction (each new edge). As you go through the instructions (edges), you'll notice that early on you will have multiple different groups of balls-and-chopsticks (aka disjoint sets), but as you go on you will start combining the different groups. With each new instruction you will combining two groups (where a ball by itself is considered a group), UNTIL you get to a very special instruction that asks you to combine two Play-Doh balls that are already in the same group. That's the instruction (edge) you will return as output. My summary: If a question ever mentions a tree, you should remember that a disjoint set is one type of tree data structure. Iterate through the edges, adding each edge one-at-a-time to a disjoint-set data structure (aka a union-find data structure); this involves maintaining one array to keep track of the reference/parent vertex that each vertex has as its ultimate parent, and another array to keep track of the size of the different sets (so you know how to most-efficiently combine sets to make it fast to look up the reference/parent vertex for any given vertex). When you come across an edge that would be redundant (both vertices are already in the same set / have the same reference vertex), that's the one you want to return. One optimization you can use in this case is path compression, since we don't need to maintain the original shape of the graph to answer the question of which edge is redundant.

This is more like By Size, not by Rank and path compression wastes a cycle by not going to parent first. Also we can use maps/objects instead of arrays for more speed. Here is a JS implementation employing both path compression and ranking: ```js function findRedundantConnection(edges) { const par = {}, rank = {} for(let i = 1; i par[x] === x ? x : par[x] = find(par[x]) function union(n1, n2) { let p1 = find(n1), p2 = find(n2) if (p1 == p2) return true if (rank[p1] < rank[p2]) par[p1] = p2 else if (rank[p1] > rank[p2]) par[p2] = p1 else par[p1] = p2, rank[p2]++ } for (const [n1, n2] of edges) if (union(n1, n2) === true) return [n1, n2] } ```

Leetcode 968 please

Dang gave me spoilers before explaining the question. :(

and also for those of you who are confused about why line 9, the code works just without that line

There is actually no reason to use a rank array in this problem. It doesn't matter which component's root node will end up being the root node of two previously unconnected components.

How does this problem have 64% submission rate?

If someone is not able to understand the above explanation Below is one of the easy explanation ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-P4alLDv9rCk.html

Please solve leetcode 749: contain virus

p = par[n] while p!= par[n] doesn't make sense. do you mean n != par[n]

Why are ranks getting added to each other? As per my understanding, it is something like: if rank[p1] < rank[p2]: parent[p1] = p2 elif rank[p1] > rank[p2]: parent[p2] = p1 else: parent[p2] = p1 rank[p1] += 1 # Rank of a tree only increases by 1 if both trees have equal ranks. # If the ranks are unequal, then we append the smaller tree below the larger tree's root and the larger tree's rank stays the same.

First time I’ve had to slow down playback speed on YT. I’d suggest going slower with complex things like graphs

def findParent(node): while node != parent[node]: parent[node] = parent[parent[node]] node = parent[node] return node or def findParent(node): p = parent[node] while p != parent[p]: parent[p] = parent[parent[p]] p = parent[p] parent[node] = p return p

Check this video out for better solution! ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-P4alLDv9rCk.html

1489,1553,1011,124,684,2328

I think we don't need both rank and parent to track the cycle, with parent array itself we can achieve... Below is my solution beats 98% in leetcode and simple array addition + find ------------------------------------------------------------------------------------------------------------------------------------ def findRedundantConnection(self, edges: List[List[int]]) -> List[int]: parents = [-1] * (len(edges) + 1) def find_parent(node): if parents[node] == -1: return node return find_parent(parents[node]) def union(node1, node2): parents[node1] = node2 for edge in edges: node1, node2 = edge node1_parent, node2_parent = find_parent(node1), find_parent(node2) if node1_parent == node2_parent: return edge union(node1_parent, node2_parent) ----------------------------------------------------------------------------------------------------------------------------------------- Thank you soo much for all your videos, From your videos, I can see a good improvement in my thinking towards a solution

Thanks!