In leetcode, the question is different. Read the movements there. Let's continue the habit of commenting “understood” if you got the entire video. Do follow me on Instagram: striver_79
@@venkatesh.guntreddi i would say learn basics of loop ,for ,if else statement first and then move in to advance topices like stack ,queue etc . all the best and welcome to the coding community my brother
yes, leetcode question is bit different, instead of 8 directions, 4 are considered. its code can be class Solution { public: void bfs(vector&vis,vector&grid,int i,int j) { vis[i][j]=1; int n=grid.size(); int m=grid[0].size(); queueq; q.push({i,j}); while(!q.empty()) { int row=q.front().first; int col=q.front().second; q.pop(); /This part has to be changed int nrow=row-1; int ncol=col; if(ncol>=0 && ncol=0 && nrow=0 && ncol=0 && nrow=0 && ncol=0 && nrow=0 && ncol=0 && nrow
Striver, I Thank You a lot ! I just had a similar question in which this was a part in my GOOGLE interview. Couldn't have done it without this. Thanks again :)
For leetcode Problem... small change in the condition for the directions... class Solution { private: void bfs(vector& grid,int i,int j,vector&vis) { vis[i][j]=1; queueq; q.push({i,j}); int row=grid.size(); int col=grid[0].size(); int delrow[4]={-1,0,1,0}; int delcol[4]={0,1,0,-1}; while(!q.empty()) { int r=q.front().first; int c=q.front().second; q.pop(); for(int k=0;k=0 && newrow=0 && newcol
Amazing 😍😍, I did it with DFS. But i have a small doubt. In numIsland function where you are first time calling the BFS first time. Can we put the grid [i][j] =='1' This would decrease the number of BFS calls? .. Edit: You already Corrected that😎😎.... Means i am on right path🔥🔥🔥
The LeetCode and the GFG problem are vastly different. For starters, the LeetCode problem is only 4 dimensional and the GFG one is 8 dimensional(which is not a big deal, ofc). But the LeetCode problem has the concept of rotation which is different from the GFG problem. LeetCode problem is based on identification of "identical islands". GFG problem deals with identification of "connected islands"
Space complexity for queue will be O(max(M,N)) since bfs is a level order traversal and we start from the first most element, the maxm num elements will be the diagonal
For people who are confused in Leetcode problem: In leetcode, it is specified that we have to check only in 4 direction instead of 8 i.e. top, right, bottom and left. The same code will work, just you have to not consider the remaining 4 directions. You have to add this extra check in your loops: if((i==-1 && j==-1) || (i==-1&&j==1) || (i==1&&j==-1) || (i==1&&j==1)) continue; Updated for loops in bfs() function: for(int i=-1; i=0 && nbrCol < m && grid[nbrRow][nbrCol] == '1' && !vis[nbrRow][nbrCol]){ vis[nbrRow][nbrCol] = 1; q.push({nbrRow, nbrCol}); } } }
Such a great explanation dada... for such a complex question ... took around 2 hrs to understand and code it down... but very well and clear explanation
for current leetcode question, an isalnd is considered as connected only through horizontal and vertical connections. to tackle this, simply skip the diagonal traversals while checking neighbours. to do this, inside the double nested for loop traversing delrow anddel col. include the first line as if(adjrow!=0 && adjcol!=0) continue; rest all remains exactly same.
This grid can also be converted into a graph of adjacency list. But it may be time consuming in an interview. To do this, consider each box on the grid as a node. we need to number the nodes. So in above we can observe node 1 is connected to node 2, node 5, node6 . Node 0 and Node 1 are not connected. Node 0 and Node4 are also not connected. and so on .. But Grid problems are solved faster using the direction vectors to get the neighbours and referring to the node as a pair as shown in the video.. Please watch William Fiset video on graph playlist related to grid. He has explained wonderfully.
Instead of creating another 2d array as visited, we can just mark the visited ones in the given array as 2. Or any number other than 1. Will save space :P . Just my 2 cents.
We don't want to change the original matrix so we have to use extra matrix and see space is same as if we are doing dfs then stack space, or if we are doing via bfs then queue space..
no they are not similar. Province problem was graph represented in a matrix. A grid is different from a matrix. In a grid each box is a node. where as in a matrix representation each row is associated with the node and tells which other nodes this node connects to..
For the people suffering on leetcode, take a check just after that shortcut trick so that we dont check the diagonal elements as connected components - void bfs(int row,int col, vector &vis, vector &grid){ vis[row][col]=1; queue q; int n = grid.size(); int m = grid[0].size(); q.push({row,col}); while(!q.empty()){ int row = q.front().first; int col = q.front().second; q.pop(); //for neighbouring elements or cell. //you could use direct indexes too :) for(int del_row=-1;del_row
@@jonny._.1313evenif i will be explaining then it wont get clear to u untill u dry run the shortcut code itself......anyways...... But, you could even do it directly using indexes.
for LeetCode the solution is slightly different since it only allows movement in 4 directions only The DFS code is as follows: class Solution { public: void dfs(int row, int col, vector&grid, vector &vis){ int n = grid.size(); int m = grid[0].size(); vis[row][col] = 1; int delR[4]= {-1,0,1,0}; int delC[4]= {0,1,0,-1}; for(int i =0; i=0 && nRow=0 && nCol
00:08 Number of islands in a grid 02:19 You can achieve complete coverage of the connected nodes by performing three traversals. 04:34 Three islands exist 06:56 We are using adjacency list to find neighbors 09:18 BFS traversal starting points 11:36 The code describes the implementation of a BFS traversal for a character grid 13:38 Implement BFS algorithm to mark cells in a grid 15:47 Learn a shortcut to find the neighbors of a given location on a grid 17:59 You can easily get all the neighbors using the given technique. 19:58 Use BFS algorithm with a matrix to solve a particular problem. 22:00 The space complexity is approximately O(n^2) and the time complexity is approximately O(n^2) 23:45 The time complexity is roughly n square.
We can also define vector direction = [{0,1},{1,0},{0,-1},{-1,0},{-1,-1},{1,-1},{1,1},{-1,1}] then traverse using for(auto adj: direction){ n_ row = row+adj.first; n_col = col +adj.second; } To get the all the neighbor of (row,col); Thanks Striver :)
Easy and Shortest one for this.......... void DFS(vector& grid, int i, int j) { // boundary checking if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size()) return; // return if current position is of water or is already visited if(grid[i][j] == '2' || grid[i][j] == '0') return; // mark the current as visited grid[i][j] = '2'; // do DFS in all 4 directions DFS(grid, i+1, j); DFS(grid, i, j-1); DFS(grid, i-1, j); DFS(grid, i, j+1); } int numIslands(vector& grid) { // We can treat the matrix grid as a grid. Each Island is a // connected component. The task is to find no. of disconnectedd components // in the graph. int islands = 0; // We make each 1 as 2 in when it is visited for(int i = 0; i < grid.size(); i++) { for(int j = 0; j < grid[0].size(); j++) { // do DFS in case has not been visited and there is land if(grid[i][j] == '1') { DFS(grid, i, j); ++islands; } } } return islands; }
Hey @Striver, explanation is on point, realy helpful. One thing I noticed you explain the bfs storage to be a queue but u always represent on diagram a stack, As per my understanding in bfs we use queue FIFO and in DFS its stack LIFO. Feel free to correct if am wrong.
Since we are reading graphs, am assuming you are well versed with time complexity. If you are not, I think you should get those basics right before getting deep into graphs 😅
@@takeUforward fair enough. Although I do have basic understanding but I always get lost for recursion cases. So does watching your first 7 videos from recursion playlist will do the trick for TC part?
I have done this dfs sol and feel very confident after the solution got submitted successfully thank you striver 😁😁 void bfs(vector &value , vector&vis,int row,int col) { vis[row][col]=1; int r= value.size(); int c= value[0].size();
We can also do it without using another visited array by changing in the same array. Your explanation quality is so smooth and fantastic. Thank You. void f(int i,int j,vector&grid) { if(i=grid[0].size() || grid[i][j]=='0') return; grid[i][j]='0'; for(int dx=-1;dx
How come the TC is 8XN^2. As you said the 9th Iteration will be ignored since it is already visited. The same will happen for the remanining nodes too. If that node is already visited we are not doing the work inside the nested loops for those nodes. So ultimately we will do work for only those nodes which are not visited.(Just like we ignore the 9th iteration since it is already visited, we ignore the remaning nodes too if already visited)> So the time complexity will be O(N^2) but not 8XN^2. Please correct me If I am wrong...:)
In leetcode, the question is different. Read the movements there.
Let's continue the habit of commenting “understood” if you got the entire video.
Do follow me on Instagram: striver_79
Striver, video description me " C++/Java/Codes and Notes Link" galat hai...
@@venkatesh.guntreddi i would say learn basics of loop ,for ,if else statement first and then move in to advance topices like stack ,queue etc . all the best and welcome to the coding community my brother
yes , only four diresctions are considered in it .
Understood
yes, leetcode question is bit different, instead of 8 directions, 4 are considered.
its code can be
class Solution {
public:
void bfs(vector&vis,vector&grid,int i,int j)
{
vis[i][j]=1;
int n=grid.size();
int m=grid[0].size();
queueq;
q.push({i,j});
while(!q.empty())
{
int row=q.front().first;
int col=q.front().second;
q.pop();
/This part has to be changed
int nrow=row-1;
int ncol=col;
if(ncol>=0 && ncol=0 && nrow=0 && ncol=0 && nrow=0 && ncol=0 && nrow=0 && ncol=0 && nrow
This is by far the best graph series ever found on internet, cant thank you enough for this!
for graph check out Luv graph series
I've been hoping from few playlists and books lately to get some confidence in this topic and your series just does that.
Thanks tons.
Striver, I Thank You a lot ! I just had a similar question in which this was a part in my GOOGLE interview. Couldn't have done it without this. Thanks again :)
you appplied the same for loops in 3D DP - when ALICE and BOB wanted to collect the choclates , just amazing how you teach and how we corelate ❤❤
For leetcode Problem... small change in the condition for the directions...
class Solution {
private:
void bfs(vector& grid,int i,int j,vector&vis)
{
vis[i][j]=1;
queueq;
q.push({i,j});
int row=grid.size();
int col=grid[0].size();
int delrow[4]={-1,0,1,0};
int delcol[4]={0,1,0,-1};
while(!q.empty())
{
int r=q.front().first;
int c=q.front().second;
q.pop();
for(int k=0;k=0 && newrow=0 && newcol
ques no?
@@kunalsharma8985 200
@@kunalsharma8985 200
@@kunalsharma8985 200
adding a pseudo code for four directional traversal namely up, down ,left and right.
vector delta = {0,1,0,-1,0};
for(int k =0;k
Amazing 😍😍, I did it with DFS. But i have a small doubt. In numIsland function where you are first time calling the BFS first time. Can we put the grid [i][j] =='1' This would decrease the number of BFS calls? ..
Edit: You already Corrected that😎😎.... Means i am on right path🔥🔥🔥
The LeetCode and the GFG problem are vastly different. For starters, the LeetCode problem is only 4 dimensional and the GFG one is 8 dimensional(which is not a big deal, ofc). But the LeetCode problem has the concept of rotation which is different from the GFG problem. LeetCode problem is based on identification of "identical islands". GFG problem deals with identification of "connected islands"
thanks mate, I didn't read the leetcode problem
there's a simple change to the if condition
if(delrow==0 || delcol==0)
@@sahilbani7020 thanks bhai
Yes in leetcode u need to add the condition of abs value of i == abs j then continue it like that ...
bro its now in premium category...sad me
bro i wasted lot of time because of this bro. thank you so much...
Space complexity for queue will be O(max(M,N))
since bfs is a level order traversal and we start from the first most element, the maxm num elements will be the diagonal
For people who are confused in Leetcode problem:
In leetcode, it is specified that we have to check only in 4 direction instead of 8 i.e. top, right, bottom and left.
The same code will work, just you have to not consider the remaining 4 directions.
You have to add this extra check in your loops:
if((i==-1 && j==-1) || (i==-1&&j==1) || (i==1&&j==-1) || (i==1&&j==1)) continue;
Updated for loops in bfs() function:
for(int i=-1; i=0 && nbrCol < m && grid[nbrRow][nbrCol] == '1' && !vis[nbrRow][nbrCol]){
vis[nbrRow][nbrCol] = 1;
q.push({nbrRow, nbrCol});
}
}
}
if((i==-1 && j==-1) || (i==-1&&j==1) || (i==1&&j==-1) || (i==1&&j==1)) continue;
instead we can write if(i*j!=0) continue;
Such a great explanation dada... for such a complex question ... took around 2 hrs to understand and code it down... but very well and clear explanation
understood so well , that even i can teach it anybody with full confidence , Thankyou Striver 😇
for current leetcode question, an isalnd is considered as connected only through horizontal and vertical connections. to tackle this, simply skip the diagonal traversals while checking neighbours. to do this, inside the double nested for loop traversing delrow anddel col. include the first line as
if(adjrow!=0 && adjcol!=0) continue;
rest all remains exactly same.
you made java code a little complicated because i implemented in dfs and was way easier to understand. but anyway the explaination was realy good
took two days but in the end "UNDERSTOOD" Thank U striver
@@udaypratapsingh8923 not every one is smart as u
Thankyou soo much for deep explanation and also for providing code in java , it really helps
Finally understood this problem completely . Thanks Striver.
This grid can also be converted into a graph of adjacency list. But it may be time consuming in an interview. To do this, consider each box on the grid as a node. we need to number the nodes.
So in above we can observe node 1 is connected to node 2, node 5, node6 . Node 0 and Node 1 are not connected. Node 0 and Node4 are also not connected. and so on ..
But Grid problems are solved faster using the direction vectors to get the neighbours and referring to the node as a pair as shown in the video..
Please watch William Fiset video on graph playlist related to grid. He has explained wonderfully.
the shortcut for visiting all the nodes was awesome
Instead of creating another 2d array as visited, we can just mark the visited ones in the given array as 2. Or any number other than 1. Will save space :P . Just my 2 cents.
can you share your code's link?
We don't want to change the original matrix so we have to use extra matrix and see space is same as if we are doing dfs then stack space, or if we are doing via bfs then queue space..
Bro, saving space should be in the algorithm, not that you change the input data structures, they're just meant to provide you the input...
It's a bad practice and cheating as some interviews might not allow you to modify inputs.
People say we should never modify the inputs
I m touched as well with the dedication, you teach selflessly. ❤
You are gem bro..
I really like his videos for the way he discusses time complexity.
It is similar ques to the previous one , where we calculated the proviences, but the diff is here we are working with matrix
no they are not similar. Province problem was graph represented in a matrix. A grid is different from a matrix. In a grid each box is a node. where as in a matrix representation each row is associated with the node and tells which other nodes this node connects to..
Understood !! how easily you let us understand so much hard questions in a very easy manner :)
For the people suffering on leetcode, take a check just after that shortcut trick so that we dont check the diagonal elements as connected components -
void bfs(int row,int col, vector &vis, vector &grid){
vis[row][col]=1;
queue q;
int n = grid.size();
int m = grid[0].size();
q.push({row,col});
while(!q.empty()){
int row = q.front().first;
int col = q.front().second;
q.pop();
//for neighbouring elements or cell.
//you could use direct indexes too :)
for(int del_row=-1;del_row
Thanks !)
Thanks
Thanks :-)
Intuition behind this shortcut please which is used to check all connected lands
@@jonny._.1313evenif i will be explaining then it wont get clear to u untill u dry run the shortcut code itself......anyways...... But, you could even do it directly using indexes.
instead of using visited matrix we can directly put replace that 1 with 0 reducing the space complexity
UNDERSTOOD....Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Beautifully explained 🎉❤❤❤
He says" I am touched" :))) wonderful explanation..
for LeetCode the solution is slightly different since it only allows movement in 4 directions only
The DFS code is as follows:
class Solution {
public:
void dfs(int row, int col, vector&grid, vector &vis){
int n = grid.size();
int m = grid[0].size();
vis[row][col] = 1;
int delR[4]= {-1,0,1,0};
int delC[4]= {0,1,0,-1};
for(int i =0; i=0 && nRow=0 && nCol
Understood! Super great explanation as always, thank you very much!!
I love this video! It's very clear and easy to follow. Thank you!!
Again I solved this problem by myself only after watching your explanation, Thank you striver for this amazing video 😁
Hello
@@techhelper9054 hi
@@ayushigupta8633 bye
ohh achhha acchaa
Thank you so much bhaiya for this series
Understood
For leetcode problem only made this change
for(int delrow=-1;delrow
We might store the movements in two individual arrays for row and column. And then we may do it.
Question in leetcode and GFG has different neighbor conditions, thanks that I'm able to solve both
The exact solution in python "TLE"s (10/26) 😵
Welp, have to embrace the pain of coding in Python.
Anyways, great to learn something new. Thanks!
Amazing your vedio question always on leectode and which helps to make profile amazing soo much thank you sir
Liked the video, notes taken, understood
Best explaination so far. Appreciate it!
Thanks
Leet code c++ solution:
class Solution {
public:
void solver(int i,int j,vector & grid,vector & visited)
{
int n=grid.size();
int m=grid[0].size();
queue q;
q.push({i,j});
visited[i][j]=1;
while(!q.empty())
{
auto p=q.front();
int row=p.first;
int col=p.second;
q.pop();
int nr=row+1;
int nc=col+0;
if((nr>=0 && nr=0 && nc=0 && nr=0 && nc=0 && nr=0 && nc=0 && nr=0 && nc
you are repeating the code instead use a function to check for adjacent "1".
00:08 Number of islands in a grid
02:19 You can achieve complete coverage of the connected nodes by performing three traversals.
04:34 Three islands exist
06:56 We are using adjacency list to find neighbors
09:18 BFS traversal starting points
11:36 The code describes the implementation of a BFS traversal for a character grid
13:38 Implement BFS algorithm to mark cells in a grid
15:47 Learn a shortcut to find the neighbors of a given location on a grid
17:59 You can easily get all the neighbors using the given technique.
19:58 Use BFS algorithm with a matrix to solve a particular problem.
22:00 The space complexity is approximately O(n^2) and the time complexity is approximately O(n^2)
23:45 The time complexity is roughly n square.
We can also define vector direction = [{0,1},{1,0},{0,-1},{-1,0},{-1,-1},{1,-1},{1,1},{-1,1}] then traverse using
for(auto adj: direction){
n_ row = row+adj.first;
n_col = col +adj.second;
}
To get the all the neighbor of (row,col);
Thanks Striver :)
understood 😀and wow i learn new techniques for visiting all neighbours
Understood 😊
understood!!! learnt new trick for finding neighbours
i first tried it in iterative way then wathed the video
understood.. thanks for this amazing series :)
was a challenging one, also very well explained!!
Understood. Thank you.
Understood 🙏
Understood 😎
understood
Understood. Thank you so much.
Thank you sir 😊
Understood!! Awesome Explanation...
kya baat hai boss, ekdum faadu
Thank you, Striver. Understood.
Easy and Shortest one for this..........
void DFS(vector& grid, int i, int j) {
// boundary checking
if(i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size())
return;
// return if current position is of water or is already visited
if(grid[i][j] == '2' || grid[i][j] == '0')
return;
// mark the current as visited
grid[i][j] = '2';
// do DFS in all 4 directions
DFS(grid, i+1, j);
DFS(grid, i, j-1);
DFS(grid, i-1, j);
DFS(grid, i, j+1);
}
int numIslands(vector& grid) {
// We can treat the matrix grid as a grid. Each Island is a
// connected component. The task is to find no. of disconnectedd components
// in the graph.
int islands = 0;
// We make each 1 as 2 in when it is visited
for(int i = 0; i < grid.size(); i++) {
for(int j = 0; j < grid[0].size(); j++) {
// do DFS in case has not been visited and there is land
if(grid[i][j] == '1') {
DFS(grid, i, j);
++islands;
}
}
}
return islands;
}
Hey @Striver, explanation is on point, realy helpful. One thing I noticed you explain the bfs storage to be a queue but u always represent on diagram a stack,
As per my understanding in bfs we use queue FIFO and in DFS its stack LIFO. Feel free to correct if am wrong.
he only draws it like a stack but he removes from the bottom only, just like a queue
Graph Revision:
Done and dusted in Grarph Revision (DFS)
(9 mins)
Nov'24, 2023 10:58 pm
abs(delrow - delcol) == 1 condition should be added
superb explanation
btw understood and liked.Although please elaborate a little in depth on the TC and SC part atleast in the few videos.
Since we are reading graphs, am assuming you are well versed with time complexity. If you are not, I think you should get those basics right before getting deep into graphs 😅
@@takeUforward fair enough. Although I do have basic understanding but I always get lost for recursion cases. So does watching your first 7 videos from recursion playlist will do the trick for TC part?
@@abhinavkumar6584 First 9 vidoes should be good.
@@sonit9707 thanks..although I finished the playlist already...but thanks again for replying
understood it very well...
Completely UNDERSTOOD
Thank you, Striver 🙂
Thanks so much Striver!!!!
perfect explanation👍👍
Thank you so much striver
thanks brother for explain this question in very easy way thank you so much
Thank you so much, it was superb
Please also make articles for these questions on the website.
In description there is a link
@@takeUforward Yes, But that link in the description is for BFS traversal, not specifically for the "Number of islands" question.
solved DFS of it's by OWN
Thanks
Awesome explanation ... understood
Loved your explanation😍😍😍😍
Thankyou soo much for deep explanation
Understood Striver!!
Leetcode problem dont want to consider diagonal elements:
so slight modify:
for(int delrow = -1;delrow
understood striver
great explanation👍
I have done this dfs sol and feel very confident after the solution got submitted successfully thank you striver 😁😁
void bfs(vector &value , vector&vis,int row,int col)
{
vis[row][col]=1;
int r= value.size();
int c= value[0].size();
for(int i=-1;i
you have written dfs code ,function is bfs ;)
@@amitranjan6998 yaa my function name is bfs but code is dfs 😅😅😅😅
Understood
No one can explain this....as easy as you do....🥹
Jay Jagannath Striver..!
I think we don't have to go all 8 direction only 4 direction is enough but very good video
understood bhaiya
We can also do it without using another visited array by changing in the same array.
Your explanation quality is so smooth and fantastic. Thank You.
void f(int i,int j,vector&grid)
{
if(i=grid[0].size() || grid[i][j]=='0') return;
grid[i][j]='0';
for(int dx=-1;dx
Doing manipulation in the original data is not preferred and not allowed in industry.
best explanation !
understood ,great explanation
Best series
understood!! SIR
How come the TC is 8XN^2. As you said the 9th Iteration will be ignored since it is already visited. The same will happen for the remanining nodes too. If that node is already visited we are not doing the work inside the nested loops for those nodes. So ultimately we will do work for only those nodes which are not visited.(Just like we ignore the 9th iteration since it is already visited, we ignore the remaning nodes too if already visited)> So the time complexity will be O(N^2) but not 8XN^2. Please correct me If I am wrong...:)
Awesome explanation
Bhaiya, Is it possible if we convert this adjacent matrix to list and then just apply the BFS/DFS and count the islands ?
i don't think so because its not an adjacent matrix its a normal matrix .
no you can't here.because, here the indices don't represent nodes or vertices of graph .instead they are coordinates of each point.
Understood Striver!
Understood 💙. Bhaiya one suggestion. Don't display the Java code for a long time.. Keep it for 5 -10 seconds.
Java walon ko dikkat hga bro. C++ wle ko issues nai hota utna
Thanks bhaiya
really u take me forward thanks a lot !
As always you are a rock star ✨