Number of Islands | DFS | BFS | Same as Island Perimeter | Leetcode 200 | codestorywithMIK
169Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 91st Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a very good 2D Array problem : Number of Islands | DFS | BFS | Same as Island Perimeter | Leetcode 200 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Number of Islands | DFS | BFS | Same as Island Perimeter | Leetcode 200 | codestorywithMIK
Company Tags : Paytm, Amazon, Microsoft, Samsung, Snapdeal, Citrix, D-E-Shaw, Ola Cabs, Visa, Linkedin, Opera, Streamoid Technologies, Informatica
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Number%20of%20Islands.cpp
Leetcode Link : https://leetcode.com/problems/number-of-islands/
My DP Concepts Playlist : https://youtu.be/7eLMOE1jnls
My Graph Concepts Playlist : https://youtu.be/5JGiZnr6B5w
My Recursion Concepts Playlist : https://www.youtube.com/watch?v=pfb1Zduesi8&list=PLpIkg8OmuX-IBcXsfITH5ql0Lqci1MYPM
My GitHub Repo for interview preparation : https://github.com/MAZHARMIK/Interview_DS_Algo
Instagram : https://www.instagram.com/codestorywithmik/
Facebook : https://www.facebook.com/people/codestorywithmik/100090524295846/
Twitter : https://twitter.com/CSwithMIK
Subscribe to my channel : https://www.youtube.com/@codestorywithMIK
Approach Summary :
Approach-1 (DFS):
- Time Complexity (T.C) : O(m*n), where m is the number of rows and n is the number of columns in the grid.
- Space Complexity (S.C): O(1)
- Summary: In this approach, Depth-First Search (DFS) algorithm is used to traverse the grid. The algorithm checks each cell of the grid. If a cell contains '1', indicating it's a part of an island, DFS is recursively called to mark all adjacent '1's as visited. This process continues until all cells of the current island are visited. Finally, the algorithm counts the number of islands by iterating through all cells of the grid.
Approach-2 (BFS):
- Time Complexity (T.C) : O(m*n), where m is the number of rows and n is the number of columns in the grid.
- Space Complexity (S.C): O(1)
- Summary: This approach utilizes Breadth-First Search (BFS) algorithm to traverse the grid. It iterates through each cell of the grid. If a cell contains '1', indicating it's a part of an island, BFS is performed to explore all neighboring '1's and mark them as visited. The algorithm continues this process until all cells of the current island are visited. Finally, the algorithm counts the number of islands by iterating through all cells of the grid.
Both approaches have the same time and space complexities, making them efficient solutions for finding the number of islands in a given grid.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
06:48 - Approach-1 & Approach-2 Explanation
12:14 - Coding DFS
14:55 - Coding BFS
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024