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
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"
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
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}); } } }
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🔥🔥🔥
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
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 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 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..
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; }
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..
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 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
Leetcode code for cpp -> //the intution is just that we need to count the total number of disconnected components while doing bfs or dfs in the graph class Solution { public: void bfs(int r,int c,vector& grid,vector& vis) { int n=grid.size(); int m=grid[0].size(); vis[r][c]=1; queue q; q.push({r,c});
while(!q.empty()) { int row=q.front().first; int col=q.front().second; q.pop();
int delRow[4]={-1,0,1,0}; int delCol[4]={0,1,0,-1};
We dont even need visited array: class Solution { public: void bfs(int startI, int startJ, vector& grid) { int n = grid.size(); int m = grid[0].size(); queue q;
q.push({startI, startJ}); grid[startI][startJ] = '0'; // Mark as visited by changing to '0'
// 4 directions: up, right, down, left int dr[] = {-1, 0, 1, 0}; int dc[] = {0, 1, 0, -1};
while (!q.empty()) { int row = q.front().first; int col = q.front().second; q.pop();
// Check all 4 directions for (int i = 0; i < 4; i++) { int newRow = row + dr[i]; int newCol = col + dc[i];
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && grid[newRow][newCol] == '1') { grid[newRow][newCol] = '0'; // Mark as visited q.push({newRow, newCol}); } } } }
int numIslands(vector& grid) { if (grid.empty()) return 0;
int islands = 0; int n = grid.size(); int m = grid[0].size();
for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] == '1') { islands++; bfs(i, j, grid); } } }
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();
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?
leetcode - number of islands (not identical islands, that is a different question) // explore the vertex's 4 neighbours for(int drow = -1; drow = 0 and ncol < grid[0].size()) and (grid[nrow][ncol] == '1') and (!vis[nrow][ncol])) { vis[nrow][ncol] = true; q.push({nrow, ncol}); } } } }
leetcode version, where we only have to check in 4 directions: class Solution { private: void bfs(vector& grid, vector& visited, int r, int c){ int n = grid.size(); int m = grid[0].size(); visited[r][c]=1; queueq; q.push({r,c}); while(!q.empty()){ int r=q.front().first; int c=q.front().second; q.pop(); for(int rdelta=-1;rdelta
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.
Why does this algorithm need visited array? Without visited array also it should work. Because a value of 0 in grid essentially means that it is either water or already visited Just add grid[newX][newY] = '0' at line 27 and grid[row][col] = '0' at line 9 and space complexity needed will O(1). No need for vis array
He said in the later part of the video that without even using an additional grid, we can use the same grid to mark islands as visited (replacing 1s with 0s) but yeah, considering the given grid to be part of space or not depends on us.
Space complexity is never O(1) when you use some thing to modify, the definition of space complexity is the space used in an algorithm, and is not what you recreated, you need to understand this.
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 :)
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
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 ❤❤
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
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...
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
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;
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🔥🔥🔥
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
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 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.
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
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.
the shortcut for visiting all the nodes was awesome
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.
took two days but in the end "UNDERSTOOD" Thank U striver
@@udaypratapsingh8923 not every one is smart as u
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 really like his videos for the way he discusses time complexity.
understood so well , that even i can teach it anybody with full confidence , Thankyou Striver 😇
Understood !! how easily you let us understand so much hard questions in a very easy manner :)
Thankyou soo much for deep explanation and also for providing code in java , it really helps
Finally understood this problem completely . Thanks Striver.
instead of using visited matrix we can directly put replace that 1 with 0 reducing the space complexity
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!
Understood
For leetcode problem only made this change
for(int delrow=-1;delrow
I m touched as well with the dedication, you teach selflessly. ❤
You are gem bro..
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 :)
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
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".
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;
}
Understood, thanks for you efforts.
But for space optimisation, we can use the same grid matrix for visited. Maybe marking it with "-1".
UNDERSTOOD....Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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..
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.
He says" I am touched" :))) wonderful explanation..
I love this video! It's very clear and easy to follow. Thank you!!
Understood! Super great explanation as always, thank you very much!!
Graph Revision:
Done and dusted in Grarph Revision (DFS)
(9 mins)
Nov'24, 2023 10:58 pm
understood!!! learnt new trick for finding neighbours
i first tried it in iterative way then wathed the video
We might store the movements in two individual arrays for row and column. And then we may do it.
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.
understood 😀and wow i learn new techniques for visiting all neighbours
Question in leetcode and GFG has different neighbor conditions, thanks that I'm able to solve both
Amazing your vedio question always on leectode and which helps to make profile amazing soo much thank you sir
here instead of taking visited array we can directly update grid array to '0' to decrease space complexity
Thank you so much bhaiya for this series
Understood 😊
Understood 😎
Leetcode code for cpp ->
//the intution is just that we need to count the total number of disconnected components while doing bfs or dfs in the graph
class Solution {
public:
void bfs(int r,int c,vector& grid,vector& vis)
{
int n=grid.size();
int m=grid[0].size();
vis[r][c]=1;
queue q;
q.push({r,c});
while(!q.empty())
{
int row=q.front().first;
int col=q.front().second;
q.pop();
int delRow[4]={-1,0,1,0};
int delCol[4]={0,1,0,-1};
for(int i=0;i=0 && nrow=0 && ncol
Why striver code isn't working on leetcode?? My code which is similar to striver ran successfully on gfg but not on leetcode??
Best explaination so far. Appreciate it!
Thanks
was a challenging one, also very well explained!!
kya baat hai boss, ekdum faadu
Beautifully explained 🎉❤❤❤
Leetcode problem dont want to consider diagonal elements:
so slight modify:
for(int delrow = -1;delrow
Understood 🙏
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
Liked the video, notes taken, understood
We dont even need visited array:
class Solution {
public:
void bfs(int startI, int startJ, vector& grid) {
int n = grid.size();
int m = grid[0].size();
queue q;
q.push({startI, startJ});
grid[startI][startJ] = '0'; // Mark as visited by changing to '0'
// 4 directions: up, right, down, left
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
while (!q.empty()) {
int row = q.front().first;
int col = q.front().second;
q.pop();
// Check all 4 directions
for (int i = 0; i < 4; i++) {
int newRow = row + dr[i];
int newCol = col + dc[i];
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m
&& grid[newRow][newCol] == '1') {
grid[newRow][newCol] = '0'; // Mark as visited
q.push({newRow, newCol});
}
}
}
}
int numIslands(vector& grid) {
if (grid.empty()) return 0;
int islands = 0;
int n = grid.size();
int m = grid[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') {
islands++;
bfs(i, j, grid);
}
}
}
return islands;
}
};
Understood. Thank you.
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 😅😅😅😅
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
abs(delrow - delcol) == 1 condition should be added
Thank you, Striver. Understood.
Thank you sir 😊
Understood!! Awesome Explanation...
leetcode - number of islands (not identical islands, that is a different question)
// explore the vertex's 4 neighbours
for(int drow = -1; drow = 0 and ncol < grid[0].size())
and (grid[nrow][ncol] == '1')
and (!vis[nrow][ncol]))
{
vis[nrow][ncol] = true;
q.push({nrow, ncol});
}
}
}
}
understood.. thanks for this amazing series :)
Completely UNDERSTOOD
Thank you, Striver 🙂
Understood. Thank you so much.
Understood Striver!!
leetcode version, where we only have to check in 4 directions: class Solution {
private:
void bfs(vector& grid, vector& visited, int r, int c){
int n = grid.size();
int m = grid[0].size();
visited[r][c]=1;
queueq;
q.push({r,c});
while(!q.empty()){
int r=q.front().first;
int c=q.front().second;
q.pop();
for(int rdelta=-1;rdelta
here we go!
superb explanation
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.
perfect explanation👍👍
Thanks so much Striver!!!!
Understood Striver!
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
solved DFS of it's by OWN
No one can explain this....as easy as you do....🥹
thanks brother for explain this question in very easy way thank you so much
Thank you so much, it was superb
understood it very well...
Why does this algorithm need visited array? Without visited array also it should work. Because a value of 0 in grid essentially means that it is either water or already visited
Just add grid[newX][newY] = '0' at line 27 and grid[row][col] = '0' at line 9 and space complexity needed will O(1). No need for vis array
He said in the later part of the video that without even using an additional grid, we can use the same grid to mark islands as visited (replacing 1s with 0s) but yeah, considering the given grid to be part of space or not depends on us.
nice !
Can you share your code?
Space complexity is never O(1) when you use some thing to modify, the definition of space complexity is the space used in an algorithm, and is not what you recreated, you need to understand this.
@@takeUforward Sir, is that auxiliary Space Complexity you're talking about!
Thank you so much striver
Awesome explanation ... understood
understood striver
great explanation👍
Thankyou soo much for deep explanation
Loved your explanation😍😍😍😍
As always you are a rock star ✨
understood bhaiya
Best series
Understood bhaiya
best explanation !
Jay Jagannath Striver..!
I think we don't have to go all 8 direction only 4 direction is enough but very good video
understood!! SIR