Graph Valid Tree - Leetcode 261 - Python
Vložit
- čas přidán 24. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Problem Link: neetcode.io/problems/valid-tree
0:00 - Read the problem
2:45 - Drawing Explanation
10:06 - Coding Explanation
leetcode 261
This question was identified as a facebook interview question from here: github.com/xizhengszhang/Leet...
#graph #tree #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
💡 GRAPH PLAYLIST: czcams.com/video/EgI5nU9etnU/video.html
This was indirectly the best video explaining how to find a loop in an undirected graph
Wow, me just realizing that all this problem was is literally finding a loop in an undirected graph, damn.
Not necessarily.. what if this is the case, edges are [0,1], [2,3], [3,4], [2,4].. Here the function returns False even though it has a loop (2,3,4).
if it has a loop, it should return false.
@@lavanyam3224 it should return False if it has a loop
@@lavanyam3224Here the graph contains 2 islands and maybe your code is not handling the unconnected components. For a graph to be a tree, it should not contain any loops and all the nodes should be connected. Since you are not accounting the unconnected component, the program will never reach the 2nd island where it has a loop. The program will finish after traversing 0 and 1 and will return true. To get around this, check if the size of the visited nodes == N. If not, return false. In your case, size of visited nodes should be 2 and hence should return false.
Another use case of union find. In love with the algorithm!!
With your kind of explanation skills, I wish someday you create videos on System Design preparation videos.
You must have future vision
It's possible to solve this problem using basic tree properties - it's connected and has |V|-1 edges, so doing a single traversal to check if graph is connected combined with check that len(edges) == n - 1 should suffice.
but its also possible that one node is isolated, that way one loop has to exist in the graph, and this would return true even though the graph had a loop in it.
we can keep a check of all the n-1 numbered nodes, whether they have been visited or not
@@BCS_AatirNadim I agree with Taras. The connected check ( if len(visited) == number_of_nodes) and edges check (len(edges) == number_of_nodes -1) should suffice. In the case that a node is isolated, the connected check would fail or if it is a single node with a self-loop, the edges check would fail.
I agree, but I think going through coding it out is good traversal practice. If anything, it helps the solver appreciate and understand this property of graphs more :)
yes it possible, with union-find algorithm to check cycle and use property tree E = (V - 1) to check connectivity of graph.
very clear and I could learn DFS in a very logic way. Thanks!!!
Since this problem is focusing on determine there is no cycle or not, so the first idea come up with me is using the Union find algorithm. Also, it can be solved with the normal DFS.
Union-Find Solution:
def valid_tree(self, n: int, edges: list):
if n - 1 != len(edges):
return False
parent = [i for i in range(n)]
rank = [1] * n
def find(n):
p = parent[n]
while p != parent[p]:
parent[p] = parent[parent[p]]
p = parent[p]
return p
def union(n1, n2):
p1, p2 = find(n1), find(n2)
if p1 == p2:
return 0
if rank[p1] > rank[p2]:
parent[p2] = p1
rank[p1] += rank[p2]
else:
parent[p1] = p2
rank[p2] += rank[p1]
return 1
res = n
for n1, n2 in edges:
res -= union(n1, n2)
return res == 1
Can we just return false immediately when we meet the p1 == p2 condition?
@@snoopyuj No. cause the return value of the nested function is int, not Boolean.
@@danielsun716 hmm... Maybe I can cache preRes to check that from outside.
Thank you :)
@@snoopyuj I do not think it can be broken into subproblems. But if you can do that, you could give a try.
@@AMKSD Good to know! Thanks!
Hey there! Firstly, your videos are AMAZING. I love watching your videos whenever I'm stuck. I can't thank you enough for existing Neetcode.
Recently, I've found out that I get stuck on recursive solutions. I don't have much knowledge on recursion. What reading material would you suggest so that I can become a pro on recursion?
Wonderful DFS approach ! My solution is to use BFS without tracking prev. Observation: In BFS, there is NO way we can form a cycle without 2 nodes from the same level. Cycle can only be formed by connecting two nodes in the same level, OR visiting a node more than once in a level (it has >=2 parents from the previous level). Either way, it requires two nodes from the same level be connected directly (when we have odd number nodes in a cycle) or indirectly (through a common offspring, when we have even number), together with the root we started from, they form a cycle. Another BFS solution thought I first have is to revisit a node from a offspring two levels after. It can be accepted and has the same time complexity. But it is slower, because we have to go at least 2 more levels before realizing we are actually in a cycle, compared to the first solution. Correct me if I am wrong. Thx guys!
Another person who made a YT account just for leetcode. Do you work at google yet?
Your videos and explanations are just amazing. I was wondering if you can create some system design videos as well as it would be of great help to many people.
could also run union-find to check for cycles and then return n - 1 == len(edges) to check for connectedness
Really cool how the problem is a combo of Redundant Connection and Number of Connected Components In An Undirected Graph
excellent explanation as usual, thanks!
Love this one, great explanation
Additionally it is mentioned in the constrained n is greater than or equal to 1 so we can omit the n==0 check
You deserve so many more views
After solving all NeetCode Graph problems in JavaScript, I just found that JS is not responsive every time to the same technique in DFS. For example: the construction of visit = new Set(); sometimes you have to add value.toString() in order to work out sometimes don't; most of the times you cannot establish this visit array, you just use grid[r][c] to keep track of the visited value. The union find is also problematic, esp. the find() method (sometimes you write p = par[n], sometimes you write p = n in the beginning)and the way you use union(), all variates according to different problems. What a weird and frustrating experience! I found DP easier to implement.
It is possible solve this problem with time complexity O(E) using union-find algorithm to check cycle and using property of tree E = (V - 1) to check connectivity of graph.
4:40 - wouldn't an array of booleans of size N be more efficient than a hashset? We are going to end up with all of them in the set anyway, so array would be less memory and also marginally quicker to access.
I guess we do not need to check the previous node conditions if we save the nodes as directed edges in the adjacency matrix. @neetcode?
How about Union Find Algo?
# Union Find Algorithm
def Solution():
def graphValidTree(self, n, edges):
parent = [i for i in range(n)]
ranks = [i for i in range(n)]
# Build Find
def find(n1):
p = parent[n1]
while p != parent[p]:
parent[p] = parent[parent[p]] # Path Compression
p = parent[p]
return p
# Build Union
def union(n1, n2):
p1, p2 = find(n1), find(n2)
if p1 == p2:
return False
if ranks[p1] > ranks[p2]:
ranks[p1] += ranks[p2]
parent[p2] = p1
else:
ranks[p2] += ranks[p1]
parent[p1] = p2
return True
for n1, n2 in edges:
if union(n1, n2):
n -= 1
else:
return False
return n == 0
nodes = set()
no_of_edges = 0
for i in edges:
no_of_edges +=1
nodes.add(i[0])
nodes.add(i[1])
if no_of_edges < len(nodes):
return True
return False
Awesome explanation bro
Can we do this by union join to Chek for loop and then checking if parent of each node is root to check for connected components??
I was thinking the same thing
I have a dumb question . For example : in this example , when precessing node 1 and previous node is 0, then these two line of code' for j in adj[i] ; if j== previous' .That's mean prev node is 0, i=1, j=4. Are we comparing node 4 with node 0 instead of node 4 with node 1? Do I misunderstood anything there? Thanks! 🤔
could we also do a union find algo?
if number of components == 1 and no nodes share the same parent then were good?
Yes
Great explanation. Really easy to understand. Thanks
why is the complexity O(e+v)?? if you visit each node once it should be O(v) right? going to an already visited node results in an immediate return of O(1)
He's using an Adjacency list, so for every V you have to visit all of its E (to get to the other V)
Great video, is there any advantage of using dfs instead of bfs?
No, I think either one is fine. I'm more use to DFS but sometime BFS can make problems easier.
great video thanks, better at 0.75
Doing God's work!
Can we use union find to do this ?
Nice! Can you please tell which mic and drawing software you use? Affiliate links would be great way to support you on this thanks .
Sure, this is the mic I use: amzn.to/2RRrLQd
And I just use Paint3D for the drawings with a mouse.
@@NeetCode thanks! I read a little bit about this mic I think this is really great choice from what I saw then this mic is comparable to blue yeti but has less base I think this only contributes to the clarity of voice! so it's better in that manner than blue yeti. I'm pretty surprised your are able to write letters pretty precisely with mouse. On top of all the explanations are brilliant (so even with the worst mouse/mic you would still rule the explanations) but somehow the clarity of this mic + drawing + the brilliant undoing of drawing while drawing to keep screen clear is a winning combination on top of the super clear brilliant explanations.
For anyone that came from Redundant Connection, a little adjustment from that problem's solution can be applied here.
if n == 1: return True
if not edges or len(edges) < (n-1): return False
With the above two lines added, you are good to go.
I'm not sure if this solution works. Think about A->B, B->C, C->A, in this case, A is C's neighbor, but not C's prev. but there is a loop, and it's not a tree. Please correct me if I'm wrong.
It would return false because A, and B would already be in the visited set when you visit C. So when you visit C's neighbor then you would encounter A (or B) and since it is already visited then a cycle has been detected.
i tried this problem on directed and my approach didnt worked for undirected and when saw your video my respect for you using prev went through sky ...hats off to you bro
Not sure if this is the right place for this question. Interviewing for a Solutions Architect role. Have not coded fundamentals in a while. Wondering if given a position for the car how to get the associated string for example, If given the car is at position 25, what string sequence(s) would allow a car to achieve this position, the second part of the following question. I know from the problem statement/example, this would be achieved by AAAAARAAARA. However could other strings be obtained and how could i generate all this in code- what algo and ds should be considered, naive first and then optimized. Thanks!
A (fictional) early version of self-driving car had some limitations:
it could only travel in a straight line, and
it was pre-programmed with a sequence of instructions
from an instruction set of two.
The two instructions are:
[A]ccelerate: move in the current direction for one second, then double your speed.
[R]everse: stop immediately, change direction, then reset your speed.
The initial speed, and the speed after a Reverse instruction, is 1 unit per second
So, for example, the sequence AAAAARAAARA moves the car (1+2+4+8+16)-(1+2+4)+(1) = 25.
f(AAAAARAAARA)
a) Take a sequence string and produce the final position
def position(sequence):
final_pos = 0
speed = 1
for command in range (len(sequence)):
if sequence(command) == “A”:
final_pos = final_pos + speed
speed = speed * 2
else sequence(command) == “R”:
speed = -1* speed/abs(speed)
return final_pos
b) Second part, given position get string
Thanks for your feedback!
If possible, would you please explain line 25 - 26 in your code? I don't understand why dfs(j, i) should be in the if condition.
to check if there is a loop. If there is a loop then return false and it is not a tree. To be a tree, all the "if" loop detection guards need to be skipped during recursion and return true at the end.
self notes - Prev used to detect a cycle because it is an undirected graph.
thank you so much
Check connected and n=e+1?
what is the use of adj list?
great explanation :) I was just wondering why this problem cannot be solved using UnionFind algorithm ? can anyone help, please!
Surely, It can be done that way. It's just one of possible solutions
You can also, solve this by Union Find Algorithm
Python:
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
par = [i for i in range(n)]
rank = [1]*n
conCom = n
def find(n):
p = par[n]
while p != par[p]:
par[p] = par[par[p]]
p = par[p]
return p
def union(n1,n2):
nonlocal conCom
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]
conCom -= 1
return True
for n1,n2 in edges:
if not union(n1,n2):
return False
if conCom != 1:
return False
return True
謝謝！
Thank you so much, I really appreciate it! 😊
What happens if the root node is not node 0 ? This implementation assumes node 0 is not a leaf for example.
in a tree, any node can be treated a root. It will still be acyclic and connected. try redrawing any tree with some other node as root. Can always be done.
@@petersiracusa5281 I forgot that the question states the edges are undirected. If the edges were directed, my comment would make sense.
Thanks!
this problem could be solved via DSU (disjoint set union)
Which part of this takes care of the condition of having a node that isn't connected to the rest of the nodes ?
return dfs(0, -1) and "len(visited) == n"
Amazing
union find would have been better/easier approach for this problem
Can you do binary tree cameras please Neetcode? 😭
I took a look at the problem, I havent solved it before but I will try to do it eventually, but maybe not soon.
After all prev questions being union find I didn't even though of dfs and did union find solution:
class Solution:
def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) < n-1:return False
par = [i for i in range(n)]
rank = [1] * n
def find(n):
while n != par[n]:
par[n] = par[par[n]]
n = par[n]
return n
def union(n1:int, n2:int):
r1, r2 = find(n1), find(n2)
if r1 == r2:return False
if rank[r1] > rank[r2]:
par[r2] = r1
rank[r1] += rank[r2]
else:
par[r1] = r2
rank[r2] += rank[r1]
return True
for n1, n2 in edges:
if not union(n1, n2): return False
return True
heyyyy!!! your video come in priority when leetcode word is used.
can you please update your SEO such that when a problem statement is given also your video pops up!!!!! without degrading current efficiency of you SEO
I don't see where in the problem it says 0 is the root node.
the is no root, the nodes are labeled from 0 to n-1
I'm not sure why but it seems that I need to have both of these conditions to pass the test cases
if n==1: return true
if n>0 and len(edges)==0: return false
you are not wrong, i think it was a mistake, that's a bug there.
why are we using it?
how to code recursively.
Anyone having problem with Lintcode login??
one testcase doesn't display the desired outcome
Takes 20.80MB to run..."eFfiCientLY"
I found out union find can work
class Solution:
"""
@param n: An integer
@param edges: a list of undirected edges
@return: true if it's a valid tree, or false
"""
def valid_tree(self, n: int, edges: List[List[int]]) -> bool:
# write your code here
id = [i for i in range(n)]
self.n = n
def find(v):
if v != id[v]:
root = find(id[v])
id[v] = root
return root
else:
return v
def union(a, b):
rootA = find(a)
rootB = find(b)
if rootA == rootB:
return False
else:
id[rootA] = rootB
self.n -= 1
return True
for a, b in edges:
if not union(a, b):
return False
if self.n != 1:
return False
return True
why does guy sound passively mad
this mf always does dfs
class Solution:
def validTree(self, n: int, edges: List[List[int]]) -> bool:
if len(edges) != n - 1:
return False
if n == 1:
return True
nodes = set()
for e in edges:
nodes.add(e[0])
nodes.add(e[1])
return len(nodes) == n
This code works
LeetCode, LintCode and NeetCode, lol
Dont take this the wrong way but you shouuld just state the complexities yhou should rather explain them. DOnt just say its O(E+V) rather explain why we are using E+V and why is it? I am thinking time complexity should just be O(E) where E is number of edges. It takes O(E) to make adjacency list and then it takes O(E) to visit all edges(in other words we do E number of recursion calls, i dont understand why the number of vertices matters here) and the space complexity is O(number of vertices * number of edges) because in worst case, we can have a fully connected graph input and so the dictionary has keys equal to number of vertices and for each vertex key in the dictionary, we have a list of edges.