NUMBER OF PROVINCES (Leetcode) - Code & Whiteboard
Vložit
- čas přidán 8. 01. 2021
- CORRECTION: The time complexity is actually O(N). See the discussion in the pinned comments for an explanation :)
Leetcode 547 has been super popular with Amazon and Goldman Sachs recently! Have a look and let me know if you have any questions or comments :)
leetcode.com/problems/number-...
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Let's connect on LinkedIn!
/ aleksmitrovic
Follow me on Medium!
/ mitrovic.aleksandar
Questions or suggestions for new videos? Email me!
babybear4812@gmail.com - Věda a technologie
Is that really O(N^2) time complexity? I would have thought it would be O(N) since you would not need to run DFS on all cities, since some are connected and will be added to the "visited" set
@@babybear-hq9yd I would ask that you reconsider your complexity analysis. I think your solution is actually O(n) and Kevin is right. The way to look at it is: check how many times you actually touch each city. And since all the code paths are protected with the condition if a city was already visited (O(1) lookup in a set) and then break out if true, you will only touch each city once. ........ Yes, it is one of those confusing cases where there are two nested loops (one for loop, and one recursive loop) but because of the marking and checking of each node, you don't handle any node more than once..... hence O(N)
@@chriswysocki8816 I think y'all are right. Thank you so much for auditing my comment here. I've removed the last one, will pin @Kevin's original comment, and update the description. Thanks again :)
It is O(N^2) for sure. In the worst case we have N disconnected components, and if the algorithm is run on such a graph then the "for start" loop is run N times, and each time the DFS is called which takes N itself since it needs to check all connections. This yields O(N^2). It's incorrect to say that you don't need to run DFS on all cities so it's O(N), since that wouldn't be the worst case to begin with.
If all cities are disconnected, then it is O(N^2) and this is the worst-case scenario.
If cities are connected then you can try making a case for O(N) but this is a best-case scenario.
It is O(N^2)
Man...I’ve been watching other videos for this problem and I now actually understand it. Appreciate the knowledge! Thanks!!
Your explanation is very helpful. Thank you!
Subscribed!
Lucky to found your channel
Thanks for such a nice explanation.
Great video my dude, great explanation, keep up the good work
Thanks brotha 🙇♂️
Really well explained logic! Thanks!
Thanks Denes :)
very helpful. i like the way you teach, thanks :)
thanks joe :)
great explanation, loved it
thx mohar!
very clear explanation , thank you !
Thx Anabelle :)
Good explanation. Thanks!!
Welcome :)
@babybear4812 - The time complexity of the code will O(N^2) as in the worst case when none of the cities is connected, in that case, the DFS method will called N times, and the outer loop will also be executed n times making it O(N^2).
I just did Amazon's coding demo, and there is a similar one just like this, but it's grouped matching, so you have to check adjacent provinces. Think of top right bottom left in a zelda grid or whatever. I only past 2 tests but can't get past it. 1 day left before my SDE assessment expires, I'm screwed lol
well explained!
This problem was so confusing for me to understand, thanks for explaining
my pleasure bud!!
Good explanation, keeping it simple
thanks nikhil :)
Great Explanation thank you. Can you please also do a video on number of enclaves problem on leetcode.
Thanks Ritesh! Don’t think I’ll be back on leetcode any time soon unfortunately
The visual helped a lot, great explanation! Kind of weird, but I get number of island vibes from this problem 😅
Glad to hear it! Not weird at all, the problems are virtually identical :)
you are the best
I think there is confusion in the complexity, lets say the graph is only directly connected pairwise (like 1-2, 3-4, 5-6 ... etc) in that case the dfs function will be called N/2 time and therefore time complexity is O(N^2) only. We are supposed to track how many times dfs function will be called, not how many times a node gets visited.
could not come up with any solution until I saw your brilliant solution. I am also not familiar with Python so this really helped me!
How come it’s enough for you to DFS from the curr as START only? How come we don’t have to also consider other STARTS for this (using curr as END)
So if for example were iterating on START =2. So yes we check all the [2][0…5]. But how about checking the [0…5][2] ones too?
Hi Can you tell any problem with union find approach really struggling to understand this approach. Thanks in advance
I'll be honest with you brotha I've never in my life even come close to touching union find stuff. I really can't think of any scenario where you'd need it for a coding interview; there's always an easier way.
If you're purely interested in the math then i'd recommend you check out Set Theory to get a fundamental understanding of sets and how to work with them, but I got nothing from a purely coding perspective for ya. Sorry about that!
Its that simple? 😲😲😲 OMG thanks a lot for this
:)
I was coding my own solution in parallel with watching your video. In haste, I made the problem more difficult for myself by assuming that the graph could be directed (if city A goes to city B, it does not imply that city B goes to city A). I was wandering if you could provide a solution to the problem of "counting the number of directed trees (provinces) in a forest". Just asking ..... thanks
I'll add that one to the list dude :) I'm a bit backed up as I haven't taken a look at this stuff in a while!
@@babybear-hq9yd No problem, man. Keep up the good work you're doing. (BTW, I am a former employee of Intel, a programmer and an interviewer too)
@@chriswysocki8816 Oh no way that's awesome!! If you're ever interested in doing any form of collab video and/or have tips & tricks that can be shared with the world, feel free to drop me a line and connect (contact's in the description) :) Take care!
im super confused, how is this different from number of islands????
for example
[
[1,0,0,1],
[0,1,1,0],
[0,1,1,1],
[1,0,1,1],
]
this is actually just one province, but in number of island it'll be 4 islands
the problems are def very similar!
Hi Jay,
I had to look at this problem for a really long time because I couldn't understand how it was different from number of islands.
In this problem, the 2d array is actually representative of an adjacency matrix, which is actually why you can see that all cities along the diagonal are 1; that is, all cities[ i ] [ i ] = 1. This is because in this case, every city is connected to itself. Best way to look at these kind of graphs is like so:
A B C D
A 1 0 0 1
B 0 1 1 0
C 0 1 1 1
D 1 0 1 1
where isConnected[ A ] [ B ] = 1 means City A "is connected to" City B.
Also notice the symmetrical structure of the graph along the diagonal; that is because it is undirected. so if ...
isConnected[ i ] [ j ] = 1
then it must be true that
isConnected [ j ] [ i ] = 1.
So if you were to draw that graph, it would look like A - D - C - B. Which is one province, since every node is connected. I hesitated to type (->) arrows for clarity, because the graph is undirected. Finding connected components with DFS traversal is a great way to find this path and of course solve the problem.
5 months later, but hopefully this helps anyone seeing this problem as "Number of Islands" like I did! :)
Goat
🐐
can someone do it's bfs ?
yea its doable, i did it in bfs