LeetCode 30 day Challenge | Day 17 | Number of Islands (C++, Java, Python) | LeetCode 200
Вставка
- Опубліковано 19 вер 2024
- Complete Playlist LeetCode Solutions: • LeetCode Solutions | L...
*** Best Books For Data Structures & Algorithms for Interviews:*********
1. Cracking the Coding Interview: amzn.to/2WeO3eO
2. Cracking the Coding Interview Paperback: amzn.to/3aSSe3Q
3. Coding Interview Questions - Narasimha Karumanchi: amzn.to/3cYqjkV
4. Data Structures and Algorithms Made Easy - N. Karumanchi: amzn.to/2U8FrDt
5. Data Structures & Algorithms made Easy in Java - N. Karumanchi: amzn.to/2U0qZgY
6. Introduction to Algorithms - CLR - Cormen, Leiserson, Rivest: amzn.to/2Wdp8rZ
*****************************************************************************
LeetCode 30 day Challenge | Problem 17 | Number of Islands | 17 April
LeetCode #200
Facebook Coding Interview question,
google coding interview question,
leetcode,
number of islands,
#Amazon #Facebook #CodingInterview #LeetCode #30DayChallenge #Google #NumberOfIslands
Please share you alternate approaches here and make it a more meaningful and knowledgable experience for other viewers.
Awesome explanation. I've seen more of your videos. Trust me that is not enough for the community. We need more of these videos. Your intuition of data structures is simply awesome.
Thank you.
Always liking your reasoning behind these problems.
Thanks.
It helped! I had seen solution video of other channels but this one was a crystal clear explanation!!!
Thanks.
Nice explanation sir...but how the time complexity is o(n*m) what about the dfs call present inside the two nested for loop???
Please reply sir..
Appreciate and thanks for your effort.
My pleasure
Thanks for the solution! What is the time and space complexity and how can I easily be able to find them for such problems? :(
Time Complexity = O(N), where N = number of nodes in grid,
Space Complexity = O(1). No extra space used.
Here you see that, none of the nodes/cells are visited multiple times. So, time complexity = O(N)
Also, if you must be familiar with DFS and BFS of Graph. Each of these take O(V+E) time for traversal, where V= number of vertices, E = Number of edges in the graph. Here we are doing DFS of graph. In this problem none of the nodes can have more than 4 neighbours, top left, bottom & right. So, max 4 edges. So, max number of edges can be 4*N.
By that logic also V + E --> N
I don't understand why you called the function dfs - there is no notion of searching depth first.the function is simply a recursive search implementation for this problem right? - Correct me if im wrong
anyways great video :)
We are doing DFS here. We find first unvisited cell, then start visiting all connected cells in dfs manner, until all options are exhanusted. Then we look for next unvisited cell and again start dfs there.
Refer video from approx 4:00 to 12:00.
Here maximum degree of a node can be 4, so max a node can be connected to 4 other nodes. We mark current node visited, then look for a connected node(grid cell), and start dfs there... So, we go as deep as possible, till we reach dead-end or already visited node. This is DFS.
@@KnowledgeCenter That makes sense.Thanks for ur quick reply
can you show how to solve from union rank algo.
Can anyone explain how the first example in the actual question has 1 island as output?
Input:
11110
11010
11000
00000
You can connect all 1's by visiting top, left, bottom, right 1's, so, there is just cluster/group/island of 1's here. Hence, output is 1.
@@KnowledgeCenter Thanks for the reply, I was assuming the island needs to be a rectangle or square.
The c++ method is showing runtime error