Find All Groups of Farmland | DFS | BFS | Brute Force | Leetcode 1992 | codestorywithMIK
181Whatsapp Community Link : https://www.whatsapp.com/channel/0029Va6kVSjICVfiVdsHgi1A
This is the 92nd Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve another very good 2D Array problem : Find All Groups of Farmland | DFS | BFS | Brute Force | Same as Island Perimeter | Leetcode 1992 | 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 : Find All Groups of Farmland | DFS | BFS | Brute Force | Same as Island Perimeter | Leetcode 1992 | codestorywithMIK
Company Tags : Amazon, Microsoft
My solutions on Github(C++ & JAVA) : https://github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Arrays/Find%20All%20Groups%20of%20Farmland.cpp
Leetcode Link : https://leetcode.com/problems/find-all-groups-of-farmland/
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):**
This approach utilizes Depth-First Search (DFS) to traverse the land matrix. It starts from each unvisited land cell marked as 1 and explores all connected land cells, marking them as visited (0). During the traversal, it records the coordinates of the top-left and bottom-right corners of each connected land area. The time complexity of this approach is O(m*n), where m and n are the dimensions of the land matrix. The space complexity is O(1) auxiliary space and O(m*n) due to system stack space because of recursion.
**Approach-2 (BFS):**
Here, Breadth-First Search (BFS) is employed to traverse the land matrix. Similar to DFS, it starts from unvisited land cells and explores all connected land cells iteratively. It also records the coordinates of the top-left and bottom-right corners of each connected land area. The time complexity remains O(m*n), while the space complexity is O(m*n) due to the usage of a queue for BFS.
**Approach-3 (Brute Force Greedy):**
This approach utilizes a brute-force greedy strategy. It iterates through each cell of the land matrix, identifying the start of each unvisited land area. It then extends the area to the right and downwards, marking all contiguous land cells as visited (0) and recording the coordinates of the top-left and bottom-right corners. The time complexity is O(m*n), and the space complexity is O(1) since it doesn't require additional space proportional to the input size.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#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