Minimum Number of Days to Disconnect Island | Studied Concept | Leetcode 1568 | codestorywithMIK
Вставка
- Опубліковано 12 вер 2024
- Whatsapp Community Link : www.whatsapp.c...
This is the 103rd Video of our Playlist "Array 1D/2D : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a simple 2D Array Problem : Minimum Number of Days to Disconnect Island | Already Studied Concept | Easy Code | Leetcode 1568 | codestorywithMIK
This can be more efficiently solved using "Tarjan's Algorithm". I will soon make a video on Tarjan and will then make a video for this problem using Tarjan.
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 : Minimum Number of Days to Disconnect Island | Already Studied Concept | Easy Code | Leetcode 1568 | codestorywithMIK
Company Tags : will update soon
My solutions on Github(C++ & JAVA) - github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZ...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
Summary :
The approach above uses Depth-First Search (DFS) to determine the minimum number of days required to disconnect all land cells (represented by 1s) in a grid. The problem is treated as finding the number of "islands" in the grid, where an island is defined as a group of connected land cells.
Steps:
DFS Implementation:
The DFS function explores all connected land cells starting from any unvisited cell. It marks cells as visited to avoid reprocessing.
Counting Islands:
The numberOfIslandsDFS function uses DFS to count the number of islands in the grid. This is done by iterating through all cells in the grid and initiating a DFS whenever an unvisited land cell is found.
Determining Minimum Days:
Initially, the function checks if the grid is already disconnected (i.e., has more than one island or no islands). If so, the answer is 0 days.
If the grid is still connected, the function then checks whether removing a single land cell can disconnect the grid. If a single removal causes disconnection, the answer is 1 day.
If neither of the above conditions is met, the grid can always be disconnected in 2 days by removing two cells.
This approach efficiently determines the minimum number of days required by leveraging DFS for island detection and simulating cell removal.
✨ 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
Daily attendance, but one thing i want to appreciate that Your consistency motivates us a lot.
Hats off to you man.
You deserve millions. So underrated
Sorry striver, neetcode etc. this guy here is nailing it
literally bro this guy is amazing
You make the toughest questions so easy to understand. The way you explain things is so smooth that it almost brings me to tears. You make everything so clear and simple. ://
I’ve been staring at this question for over 6 hours, and I still have no clue how to solve it. Even yesterday, it felt the same with a different question. But honestly, I’m almost in tears seeing your consistency. Hats off to you! Seriously, stop it, or I might actually cry. Just kidding-keep going, you’re doing amazing!
I don't know but as soon as video gets uploaded i am here .... much loved person ❤❤
Khudse try nahi karte kya bhai😅
@@rode_atharva subah 5 baje kr chuke bhai but still he gives some new thinking approach about conditions
@@rameshsharma3639 good😊
@@rameshsharma3639 are you student or other?
@@rode_atharva yup
You make it so simple that it feels like solving a basic addition problem. More power to you.
One i will be able to solve problems without your videos, that day i will be considered one of your good student
The concept to find row and col from 1d array , I used in one question today and it is very amazing concept and able to solve question without converting into 2d array.
bs itna consistency chahiye life me
Same 😢
Hi MIK, I am eagerly waiting for the tarjan's Algorithm video. I searched it on entire youtube, but no one explained it well. So, looking forward to it. TIA :)
Once go to know ans: 0,1,2. I coded all by myself & came here to comment. Thanks mik sir for explaining
If you can manage to make vdeo on tarjan . Thnks for this explanation
Consistency++❤❤
Loved it bhaiyan!
Nice approach 👍 ❤
What if after checking for the number of islands, which comes out to be one, i check for the number of neighbours for each 1's. if any of the '1' has just one neighbour, then we can make that particular '1' disconnected by switching its neighbour to 0, thereby seprating islands into 2. if none of the 1's have exactly one neighbour, then it's just sure that it will take 2 days (cause its not one day).
something like this:
public int minDays(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
if(!isItOneIsland(grid)) return 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(grid[i][j] == 1){
int connectedOnes = 0;
if(i < n - 1 && grid[i + 1][j] == 1) connectedOnes++;
if(i > 0 && grid[i - 1][j] == 1) connectedOnes++;
if(j < m - 1 && grid[i][j + 1] == 1) connectedOnes++;
if(j > 0 && grid[i][j - 1] == 1) connectedOnes++;
if(connectedOnes == 1) return 1;
}
}
}
return 2;
}
[THIS FAILS, IK, BUT WAS JUST WANNA KNOW WHAT'S WRONG IN THIS APPROACH EXCEPT THE [[1,1]] TEST CASE FAILING]
Check this test case
[[1,1,0,1,1],
[1,1,1,1,1],
[1,1,0,1,1],
[1,1,0,1,1]]
class Solution {
public:
void bfs(int row,int col,vector &visited, vector &grid){
queue q;
q.push({row,col});
visited[row][col] = 1;
while(!q.empty()){
auto fNode = q.front();
q.pop();
int crow = fNode.first;
int ccol = fNode.second;
int dr[4] = {0,1,-1,0};
int dc[4] = {-1,0,0,1};
for(int i =0 ; i=0 && newc>=0 && newr
Hats off to your hard work and consistency
Hi himani das we are in the same college
Great Explanation
Sir, I can think of the solution to the problem in most cases, but the problem I'm facing is the implementation part. Do you know how I can tackle this problem?
I think to know answer can be 0 1 or 2 only is key here❤
Love you bhai ❤
Please do Leetcode contest problems
Uploading today’s contest Qn-1 and Qn-4
They are good and will help us learn few things.
great explanation
@codestorywithMIK bhai 2972 leetcode question de-shaw k coding round m aaya tha explain krdo
Nice ❤
Should we not consider the stack space for DFS for space complexity?
Yes we should. If the interviewer asks for it, then mention it.
Please make videos for today's contest
Uploading today’s contest Qn-1 and Qn-4
They are good and will help us learn few things.
Thanks 😊
Who needs paid course for DSA when I have this legend
great ,
can you explain again please why can't we do this without the visited array ? a more theoretical answer for the interviewer please..
also TC, leetcode says
O(M∗N)
which is wrong obviously..
you can’t modify the grid (marking the cell visited), because you have to call DFS multiple times for same grid again and again with different configurations.
2556. Disconnect Path in a Binary Matrix by at Most One Flip ye wala question ka video banao bhaiya
great explanation as always but i have a doubt, TC of dfs is O(m+n), isn't it?
In worst case you will have to visit all the cells which will be O(m*n)
@@codestorywithMIK yea. Thanks 👍
❤
Tarjans algo kab hoga bhaiya
please cover todays contests question if possible 🙏love your explanation
Uploading today’s contest Qn-1 and Qn-4
They are good and will help us learn few things.
@@codestorywithMIK thank u bhaiya !
How can you proof that it will take max of 2 days to fulfil the requirement? I can see by intuition but is there any mathematical way or a satisfactory way ?
Lets assume a connected grid with exactly one island of any arbitrary shape.
0000000000000
0011110001110
0011111111100
0111111111110
0001100111000
0001111111000
0000000000000
Now for any arbitrary island there is bound to be a corner .
Or simply an endpoint .
For the 1 on the Corner
0 0 0 . . .
0 1 1 . . .
0 1 1 . . .
. . . . . .
We can see it has 3 neighbours Where if we remove just two that are adjacent to it as a 4 connected neighbour scenario removing those 2 we get
000
010
001
See here we got a new separate island in just 2 moves and we can prove it will be true for any island of any arbitrary shape as all shapes have a corner.[ IN A GRID ]
waiting for contest solutions
Uploading today’s contest Qn-1 and Qn-4
They are good and will help us learn few things.
sir in which paylist you have covered DFS
graphs
ua-cam.com/play/PLpIkg8OmuX-LZB9jYzbbZchk277H5CbdY.html&si=Ncry0OOEJsiSzEHK
please upload lc contest solution also , if possible !!
Uploading today’s contest Qn-1 and Qn-4
They are good and will help us learn few things.
But 2 se jada kyu nahi ho sakta answer 🤔🤔 Wo samajh mein nahi aa aaya 😞 cauz edges remove karne mein to we checked that at least n-1 edges hai to its connected , but here we're disconnecting nodes to uska samajh na aaya
kyuki Koi sa bhi grid ho....kisi bhi corner se first diagonal ko 1 se 0 krdenge...usse vo do parts me cut jayega (for eg . grid[0][1] and grid[1][0] ye do place ko zero karke saaare grids ko do parts me cut krdenge...ab koi sa bhi corner le sake ) isilye max 2 hi ho sakta answer
@@hardikgupta7264 acchaa normal graph soch rha tha isliye confuse ho gya grid mein to sahi keh rhe ....thanks bhaiii 😭😭
❤❤
Wasn't this question just visualizing the fact that the answer is either 0, 1, 2 ...
Face reveal
Bhai 3 hr we tumhari raah dekha raha hu Jaldi upload kiya karo
be kind please , he already mentioned he is travelling .. delay is expected . Keep doing good work MIK .. we appreciate it.