Minimum Number of Days to Disconnect Island | Studied Concept | Leetcode 1568 | codestorywithMIK

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

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

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

[DevOpskagyaan]

Hats off to you man.
You deserve millions. So underrated
Sorry striver, neetcode etc. this guy here is nailing it

[spdh]

Daily attendance, but one thing i want to appreciate that Your consistency motivates us a lot.

[someshnayakrollno.-sec-b]

One i will be able to solve problems without your videos, that day i will be considered one of your good student

[shraddhayadav]

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. ://

[ujjwaldobliyal]

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.

[k-CE-OmkarPathak]

Once go to know ans: 0, 1, 2. I coded all by myself & came here to comment. Thanks mik sir for explaining

[manasdeora]

You make it so simple that it feels like solving a basic addition problem. More power to you.

[rameshsharma]

I don't know but as soon as video gets uploaded i am here .... much loved person ❤❤

[stardust]

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 :)

[iamnoob]

Thanks Mik, I do think there is way to solve it efficiently by knowing adjacent connected 1s count for each land cell and find min count return, min count will be always be 1 or 2 provided its not disconnected. if count=1 then mindays =1 else mindays=2;

[abcd]

If you can manage to make vdeo on tarjan . Thnks for this explanation

[hypewaali]

Hats off to your hard work and consistency

[ayushpanwar]

@codestorywithMIK bhai 2972 leetcode question de-shaw k coding round m aaya tha explain krdo

[solosanskar]

class Solution {
public:

void bfs(int row, int col, vector<vector<int>> &visited, vector<vector<int>> &grid){



queue<pair<int, int>> 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<4 ; i++){


int newr = crow + dr[i];
int newc = ccol + dc[i];


if(newr>=0 && newc>=0 && newr<grid.size() && newc<grid[0].size() && grid[newr][newc]==1 && !visited[newr][newc]){

visited[newr][newc] = true;
q.push({newr, newc});
}
}



}


}

int minDays(vector<vector<int>>& grid) {


vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), 0));

int count = 0;
for(int i =0 ; i< grid.size() ; i++){
for(int j =0 ; j<grid[0].size() ; j++){

if(!visited[i][j] && grid[i][j]==1){
bfs(i, j, visited, grid);
count++;
}
}
}


if(count ==0 || count>=2){
return 0;
}

vector<pair<int, int>> testing;

for(int i =0 ; i< grid.size() ; i++){
for(int j =0 ; j<grid[0].size() ; j++){

if(grid[i][j]==1){
testing.push_back({i, j});
}
}
}


for(auto &i : testing){

vector<vector<int>> gridCopy = grid;

gridCopy[i.first][i.second] = 0;

vector<vector<int>> visited(grid.size(), vector<int>(grid[0].size(), 0));

int count = 0;

for(int i =0 ; i< grid.size() ; i++){
for(int j =0 ; j<grid[0].size() ; j++){

if(!visited[i][j] && gridCopy[i][j]==1){
bfs(i, j, visited, gridCopy);
count++;
}
}
}

if(count>=2 || count<1){
return 1;
}

}


return 2;
}
};

[VanisreeSunkara]

I think to know answer can be 0 1 or 2 only is key here❤

[aws_handles]

Who needs paid course for DSA when I have this legend

[-NITIN]

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?

[rishidangi]

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]

[shivani]

2556. Disconnect Path in a Binary Matrix by at Most One Flip ye wala question ka video banao bhaiya

[chc_]

great explanation as always but i have a doubt, TC of dfs is O(m+n), isn't it?