Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞 Do follow me on Instagram: striver_79
bhiya why cant we have no visited matrix in this soln,we can use the matrix given to us and to record the visited we can change it to '1' and while backtracking we can undo the changes
I am so happy to share that from lec 9 10 12 13 14 . I am able to solve them by myself without watching the whole video. After my solution gets accepted . I come and watch your video at 2x
The logic was really great. We instead of finding who will be marked cross , we found out who will not through the boundary connection condition . Kudo striver for making this series.
You've worked really hard to make these videos, mainly without getting irritated, you've coded each and every part. I realised how much time and PATIENCE is required to do that.... Thanks a lot
Yeah, this is the best thing about Striver's videos!! He is EXTREMELY PATIENT while explaining any logic and coding it up till the end!! Just follow his recursion series, you will get to know how much patient he can be...
I know it had something to do with border and how they connect. First attempt was to try to find which ones reach the border but then I realized it would be easier to find what ones the border reaches. From their I had it down, solved it, and watched the video as a refresher/check for tips or tricks.
My initial thoughts: start the ans matrix of size m*n with 'X's. If we have any 'O's on the boundary, treat them as a door or entrance and apply DFS from that cell. The DFS will make sure that it covers every O's cells which are connected to this entrance. Once DFS is done it would have marked all the affected cells as O's and rest are just 'X's. So in this way all the O's cells surrounded by boundary of X's will be marked as X.
i just saw your explanation of what the problem really is in the first few minutes, and then coded it using dfs and passes all the test cases on leetcode, thankyou so much striver , its due to your teaching that i am elevating my coding skills each day
saw 3 min, found intuition thanks to striver bhai and coded it, got AC, came and watched entire video to contribute to takeUForward's watch time and recommendation
Awesome series! Can you cover graph questions that were asked in OAs in your experience or someone else's so that we can learn what type of questions are actually asked?
striver thanks alot fot your effort in making such an amazing in depth free course , i just watched you first 6 - 7 videos and i am telling you i am able to solve medium level questions on leetcode it really boost up up confidence thanks alot striver
Oho man just did number of island Question on leetcode :) it was a daily challenge problem exactly the same type of Question like this one :) ..did with recursion went up ,down left, right and follow up the constraints :)
I made a mistake in edge case, and spent 2 hours figuring where it went wrong. It took me the first hour just to merely accept that there was an error in the edge case
Nice explaination sir but now gfg has increased test cases to 1,120 and with this approach only 1,116 test cases are getting passed thank u for your efforts
19:30 I think rather than creating delRow and delCol arrays you can just mention the dfs function call 4 times. I will save a lot on the parameters per call. Code: void dfs(int row, int col, vector& mat, vector& vis) { if(row
This question can also be done like previous one using bfs we just. Need to put zero which are at the boundary in the queue then we have to run while loop until queue becomes empty and parallely we need to mark visited to the neighbouring zeros of boundary zeros....then we have to convert zero to x which are not visited 😅
// To traverse the boundary for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if ((i == 0 || i == n - 1) || (i > 0 and i < n - 1 and (j == 0 || j == m - 1))) { // ToDo } } }
Will it be a good practice if in dfs traversal I change the boundary connected component to some random character (suppose 'Y') and then traverse the matrix where ever I find a 'O' I convert it to 'X' and change those 'Y' back to 'O'....ultimately this will change only the required 'O' ->'X'
In these type of graph problems, if it is not mentioned whether the neighbors are top, down, left and right; or all the 9 neighbours, then which one do we consider by default?
in order to traverse in the first row, column and last row, column we can use this ( rows & columns will have index either 0 or m-1 or n-1) for(int i =0; i < n ; i++) { for(int j = 0 ; j < m; j++) { if((i == 0 || j == 0 || i == n-1 || j == m-1)&& mat[i][j] == 'O' && vis[i][j]==0) { dfs(i,j, mat , vis,result); } } }
Hello, I also tried to solve without watching this video. Can you help me with this code, why it got stuck at 41/58 TC on leetcode :- class Solution { public: void solve(vector& board) { int n = board.size(); int m = board[0].size(); vector visited(n, vector (m,0)); vector temp(n, vector (m,'X')); queue q; for(int i = 0; i
@@flsh1343 class Solution { public: void solve(vector& board) { int n = board.size(); int m = board[0].size(); vector visited(n, vector (m,0)); vector temp(n, vector (m,'X')); queue q; for(int i = 0; i
BFS version of the logic (With comments 🚀🌟): class Solution { public: void solve(vector& board) { // I did using BFS. Can do it with DFS as well.
// if an 'O' will be on the edge of the board we will not flip it // Start from the O's which are present on the boundary and find all the // O's that are connected to the boundary O's , these all O's will not // be converted , and all the other O's will be converted // have a visited vector ..yes to avoid going back to the parent indexes // (i,j)?? queue q; int r = board.size(); int c = board[0].size(); vector vis(r, vector(c, 0)); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (i == 0 || j == 0 || i == r - 1 || j == c - 1) { if (board[i][j] == 'O') { // shows this can't be fliped board[i][j] = '9'; cout
A little readable java code may be : )) class Solution { public void solve(char[][] board) { //here the boundary zeros cant be converted so we just mark as x and their connectivity //after the connectivities are done from boundaries //we need to check like if its a 'O' and not visited from boundary then it definetly is surrounded by x's so we can make it as x int visited[][] = new int[board.length][board[0].length]; //first row and first col checking for '0s' for(int i=0; i
No visited matrix required. No extra space required. I did it without watching video in first attempt. Here's the code for learning: void dfs (int i, int j, int n, int m, vector& mat) { if (i < 0 || i == n || j < 0 || j == m || mat[i][j] == 'X' || mat[i][j] == '1') return; mat[i][j] = '1'; dfs (i+1, j, n, m, mat); dfs (i, j+1, n, m, mat); dfs (i-1, j, n, m, mat); dfs (i, j-1, n, m, mat); } vector fill(int n, int m, vector mat) { // code here for (int i{0}; i < n; i++) { for (int j{0}; j < m; j++) { if ((i == 0 || i == n-1 || j == 0 || j == m-1) && mat[i][j] == 'O') { dfs (i, j, n, m, mat); } } } for (int i{0}; i < n; i++) { for (int j{0}; j < m; j++) { if (mat[i][j] == 'O') { mat[i][j] = 'X'; } else if (mat[i][j] == '1') { mat[i][j] = 'O'; } } } return mat; }
Simpler version. from the initial loop, perform DFS only on 'O's and the boundary i.e 0, n -1, m-1. Mark the adjacent ''O's. class Solution { void dfs(char[][] board, int i, int j) { int n = board.length; int m = board[0].length; // Boundary check or if the cell is not 'O', stop DFS if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != 'O') { return; } // Mark this cell as part of the boundary region board[i][j] = 'B'; // Visit the 4 connected neighbors dfs(board, i + 1, j); // down dfs(board, i - 1, j); // up dfs(board, i, j + 1); // right dfs(board, i, j - 1); // left } public void solve(char[][] board) { int n = board.length; if (n == 0) return; int m = board[0].length; // Step 1: Perform DFS from all 'O's on the boundary for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // Check the edges if ((i == 0 || i == n - 1 || j == 0 || j == m - 1) && board[i][j] == 'O') { dfs(board, i, j); // Start DFS for boundary 'O's } } } // Step 2: Flip the inner 'O's to 'X' and revert the boundary 'B's back to 'O' for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (board[i][j] == 'O') { board[i][j] = 'X'; // Enclosed 'O' becomes 'X' } else if (board[i][j] == 'B') { board[i][j] = 'O'; // Boundary 'B' becomes 'O' again } } } } }
![[#2024MAMA] BIGBANG (빅뱅) - 뱅뱅뱅 (BANG BANG BANG) + FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/EQsYfiPR9uM/mqdefault.jpg)
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too, you don't 😞
Do follow me on Instagram: striver_79
I am able to solve this question myself!! thanks a lot all this is because of you....
understood.... Best explaination
understood
bhiya why cant we have no visited matrix in this soln,we can use the matrix given to us and to record the visited we can change it to '1' and while backtracking we can undo the changes
Understood Everything Thank you so Much
I am so happy to share that from lec 9 10 12 13 14 . I am able to solve them by myself without watching the whole video. After my solution gets accepted . I come and watch your video at 2x
Same
Same
The logic was really great.
We instead of finding who will be marked cross , we found out who will not through the boundary connection condition .
Kudo striver for making this series.
kudos*
You've worked really hard to make these videos, mainly without getting irritated, you've coded each and every part. I realised how much time and PATIENCE is required to do that.... Thanks a lot
Yeah, this is the best thing about Striver's videos!! He is EXTREMELY PATIENT while explaining any logic and coding it up till the end!! Just follow his recursion series, you will get to know how much patient he can be...
the energy you bring while teaching is just amazing
love how after his all set of examples and intuitions, everything just falls in place perfectly
Honestly, Striver!! Amazing LOGIC! If we think of it like you did it becomes a walk in the park!!
UNDERSTOODD!! THANK YOUUU!!
I know it had something to do with border and how they connect. First attempt was to try to find which ones reach the border but then I realized it would be easier to find what ones the border reaches. From their I had it down, solved it, and watched the video as a refresher/check for tips or tricks.
My initial thoughts: start the ans matrix of size m*n with 'X's. If we have any 'O's on the boundary, treat them as a door or entrance and apply DFS from that cell. The DFS will make sure that it covers every O's cells which are connected to this entrance. Once DFS is done it would have marked all the affected cells as O's and rest are just 'X's. So in this way all the O's cells surrounded by boundary of X's will be marked as X.
i just saw your explanation of what the problem really is in the first few minutes, and then coded it using dfs and passes all the test cases on leetcode, thankyou so much striver , its due to your teaching that i am elevating my coding skills each day
"Understood", Marvelous explanation with high energy !!
Striver bro!!! I just want to hug you.............lots of respect and love and keep doing what you are doing...
Maza aa gya bhayiya ☺☺☺
Lg hi nhi rha tha ki hard problem kr rhe h. Aaisa level set kr dya aapne hm sbka
such a good and refined series absolutely loved it striver bhai
till now in graph series, its all about how well we have understood DFS or BFS , rest is variation !!!
YOURE MY DIAMOND STRIVES :)
saw 3 min, found intuition thanks to striver bhai and coded it, got AC, came and watched entire video to contribute to takeUForward's watch time and recommendation
I was trying to solve this question on leetcode this evening and Guess what You uploaded a solution!
Awesome series! Can you cover graph questions that were asked in OAs in your experience or someone else's so that we can learn what type of questions are actually asked?
Bhai gfg ke jobhathon dekho almost every contest mai hard ques graph based hote hai use bhaiya samjhate hai contest review mai
@@chandannikhil8526 Thank you will check those videos out
Barhe log aa gye ...love you warsaw bhaiya ❤️
badhe***
I understood your explanation, paused your video and tried it with BFS, it worked. Amazing explanation
because of you i am easily able to understand graph
thank you sir......
Able to solve the problem just by seeing till 2:40 of the video...power of Strivers 😎
same
same
Aap question aur code dono ko bahut easy bana dete ho bhaiya😀😍
Awesome, thank you striver as always understood
striver thanks alot fot your effort in making such an amazing in depth free course , i just watched you first 6 - 7 videos and i am telling you i am able to solve medium level questions on leetcode it really boost up up confidence thanks alot striver
Oho man just did number of island Question on leetcode :) it was a daily challenge problem exactly the same type of Question like this one :) ..did with recursion went up ,down left, right and follow up the constraints :)
able to do this question without watching the solution it really boosted my confidence thaku striver
Great explanations, I was wondering here for complex problem solution I am getting training as doctor strange got from guru maa in kathmandu!
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
solved on my own without watching the video on basis of prev videos and now watching
I was so frustrated, I write '0' instead of 'O' and wondering why it is not working for 1 hour 🤦♂🤦♂
Good
I made a mistake in edge case, and spent 2 hours figuring where it went wrong. It took me the first hour just to merely accept that there was an error in the edge case
same dude
compilation error nhi kiya 0 int hai O char hai
Shabash❤😂
using jS one can make a game that contain the player which is surrounded by a protection layer and enemy can enter through the boundry points
thank you striver for creating such amazing content
Nice explaination sir but now gfg has increased test cases to 1,120 and with this approach only 1,116 test cases are getting passed
thank u for your efforts
Understood the solution in first 6 mins.
Paused the video and solved the question in 10 mins 😉
19:30 I think rather than creating delRow and delCol arrays you can just mention the dfs function call 4 times. I will save a lot on the parameters per call.
Code:
void dfs(int row, int col, vector& mat, vector& vis)
{
if(row
Time limit exceeds : 1032/1044 passed
@@arshdeep011 Are you the cricketer Arshdeep Singh?
@@rushidesai2836 I don't watch cricket
Understood, Thank you so much, this was such a beautiful solution.
excellent explanation!
thanks man,same question came in my cohesity interview 40lpa
Thank you striver for all your efforts.
Solved this one by self on BFS and DFS Both.
Understood bhaiya i have done bfs traversal
This question can also be done like previous one using bfs we just. Need to put zero which are at the boundary in the queue then we have to run while loop until queue becomes empty and parallely we need to mark visited to the neighbouring zeros of boundary zeros....then we have to convert zero to x which are not visited 😅
// To traverse the boundary
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ((i == 0 || i == n - 1) || (i > 0 and i < n - 1 and (j == 0 || j == m - 1))) {
// ToDo
}
}
}
kaya bat hai baiya ,maza aagya apka obserwation se
khatarnak insted of finding who will be mark as 'X' we will find whol will not such a great idea
Thanks a lotttt striver for such an amazing playlist
Understood!! Very well explained!!!
understood striver
Awesome explanation as always
Superb as usual. But the first time I found energy and excitement low during explanation.
Keep your uniqueness full of energy and excitement.❤️
Repeated questions, new questions excite me ;)
@@takeUforward 💛 thank you so much striver for these playlists , i learned recursion tree dp nd now graphs too.
Great explanation 👍
Thank you, Striver 🙂
day by day getting confidence while doing graph question able to solve this question myself #thanks Wizard Striver
very nice approach and explanation
Will it be a good practice if in dfs traversal I change the boundary connected component to some random character (suppose 'Y') and then traverse the matrix where ever I find a 'O' I convert it to 'X' and change those 'Y' back to 'O'....ultimately this will change only the required 'O' ->'X'
you can! the main aim of the video is to teach that dfs or bfs can be used to solve the problem, can have various approaches.
i did the same
Legend is back
Thank you so much for such a detailed video
Understood! Is this how to fill by one color in an area surrounded by different color? Anyway, so amazing explanation as always, thank you very much!!
Understood 😊
Understood😁Thanks a lot Striver😃
just watched 1 min and solved the whole problem damn
striver could we add the delrow[] and delcol[] inside the function itself ?rather than passing it as a parameter
understood, thanks for the effort on the great video
In these type of graph problems, if it is not mentioned whether the neighbors are top, down, left and right; or all the 9 neighbours, then which one do we consider by default?
understood very well!!!
Thank you very much. You are a genius.
Thank You striver Bhaiya 🤟
Understood Sir, Thank you very much
You are my inspiration ......................hats offfffffffffffffffffffff
in order to traverse in the first row, column and last row, column
we can use this ( rows & columns will have index either 0 or m-1 or n-1)
for(int i =0; i < n ; i++)
{
for(int j = 0 ; j < m; j++)
{
if((i == 0 || j == 0 || i == n-1 || j == m-1)&&
mat[i][j] == 'O' && vis[i][j]==0)
{
dfs(i,j, mat , vis,result);
}
}
}
It has m*n complexity, our solution has m+n complexity
Majaa Aagaya😜
UNDERSTOOD!!!!!!!!
Solved it without starting the video
Thank you Raj bhaiya for this wonderful playlist!
CODE:
class Solution {
private:
int dir[5] = {0,-1,0,1,0};
void bfs(int r, int c, vector &board, vector &safe){
safe[r][c] = true;
queue q;
q.push({r,c});
while(!q.empty()){
int row = q.front().first;
int col= q.front().second;
q.pop();
for(int i = 0; i < 4; ++i){
int nrow = row + dir[i], ncol = col + dir[i+1];
if(nrow >= 0 && ncol >= 0 && nrow < board.size() && ncol < board[0].size() && board[nrow][ncol] != 'X' && !safe[nrow][ncol]){
safe[nrow][ncol] = true;
q.push({nrow,ncol});
}
}
}
}
public:
void solve(vector& board) {
int m = board.size(), n = board[0].size();
vector safe(m,vector(n,false));
for(int i = 0; i < m; ++i){
for(int j= 0; j < n; ++j){
if(i == 0 || j == 0 || i == m-1 || j == n-1){
if(board[i][j] != 'X' && !safe[i][j]){
bfs(i,j,board,safe);
}
}
}
}
for(int i =0; i < m ; ++i){
for(int j = 0; j < n; ++j){
if(board[i][j] != 'X' && safe[i][j] == true){
continue;
}else{
board[i][j] = 'X';
}
}
}
}
};
Hello, I also tried to solve without watching this video. Can you help me with this code, why it got stuck at 41/58 TC on leetcode :-
class Solution {
public:
void solve(vector& board)
{
int n = board.size();
int m = board[0].size();
vector visited(n, vector (m,0));
vector temp(n, vector (m,'X'));
queue q;
for(int i = 0; i
@@flsh1343 class Solution {
public:
void solve(vector& board) {
int n = board.size();
int m = board[0].size();
vector visited(n, vector (m,0));
vector temp(n, vector (m,'X'));
queue q;
for(int i = 0; i
BFS version of the logic (With comments 🚀🌟):
class Solution {
public:
void solve(vector& board) {
// I did using BFS. Can do it with DFS as well.
// if an 'O' will be on the edge of the board we will not flip it
// Start from the O's which are present on the boundary and find all the
// O's that are connected to the boundary O's , these all O's will not
// be converted , and all the other O's will be converted
// have a visited vector ..yes to avoid going back to the parent indexes
// (i,j)??
queue q;
int r = board.size();
int c = board[0].size();
vector vis(r, vector(c, 0));
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (i == 0 || j == 0 || i == r - 1 || j == c - 1) {
if (board[i][j] == 'O') {
// shows this can't be fliped
board[i][j] = '9';
cout
understood, thanks for such playlist!!
here we go !
#UNDERSTOOD
A little readable java code may be : )) class Solution {
public void solve(char[][] board) {
//here the boundary zeros cant be converted so we just mark as x and their connectivity
//after the connectivities are done from boundaries
//we need to check like if its a 'O' and not visited from boundary then it definetly is surrounded by x's so we can make it as x
int visited[][] = new int[board.length][board[0].length];
//first row and first col checking for '0s'
for(int i=0; i
solved without even looking solution that's the power of striver
Understood Sir!
always love ur vidos and u brother😍
*understood*, day 1 of documenting myself
God of dsa🙏
UNDERSTOOD.
Understood Bhaiya
ek dum mast
Thanks you very much bro for the series
Thank you sir
Great intuition
No visited matrix required.
No extra space required.
I did it without watching video in first attempt.
Here's the code for learning:
void dfs (int i, int j, int n, int m, vector& mat) {
if (i < 0 || i == n || j < 0 || j == m || mat[i][j] == 'X' || mat[i][j] == '1') return;
mat[i][j] = '1';
dfs (i+1, j, n, m, mat);
dfs (i, j+1, n, m, mat);
dfs (i-1, j, n, m, mat);
dfs (i, j-1, n, m, mat);
}
vector fill(int n, int m, vector mat)
{
// code here
for (int i{0}; i < n; i++) {
for (int j{0}; j < m; j++) {
if ((i == 0 || i == n-1 || j == 0 || j == m-1) && mat[i][j] == 'O') {
dfs (i, j, n, m, mat);
}
}
}
for (int i{0}; i < n; i++) {
for (int j{0}; j < m; j++) {
if (mat[i][j] == 'O') {
mat[i][j] = 'X';
} else if (mat[i][j] == '1') {
mat[i][j] = 'O';
}
}
}
return mat;
}
understood bhaiya
understood , thnk u striver
Just Wow observation
Understood thank you sir
Thank you Bhaiya
Simpler version.
from the initial loop, perform DFS only on 'O's and the boundary i.e 0, n -1, m-1. Mark the adjacent ''O's.
class Solution {
void dfs(char[][] board, int i, int j) {
int n = board.length;
int m = board[0].length;
// Boundary check or if the cell is not 'O', stop DFS
if (i < 0 || i >= n || j < 0 || j >= m || board[i][j] != 'O') {
return;
}
// Mark this cell as part of the boundary region
board[i][j] = 'B';
// Visit the 4 connected neighbors
dfs(board, i + 1, j); // down
dfs(board, i - 1, j); // up
dfs(board, i, j + 1); // right
dfs(board, i, j - 1); // left
}
public void solve(char[][] board) {
int n = board.length;
if (n == 0)
return;
int m = board[0].length;
// Step 1: Perform DFS from all 'O's on the boundary
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// Check the edges
if ((i == 0 || i == n - 1 || j == 0 || j == m - 1) && board[i][j] == 'O') {
dfs(board, i, j); // Start DFS for boundary 'O's
}
}
}
// Step 2: Flip the inner 'O's to 'X' and revert the boundary 'B's back to 'O'
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X'; // Enclosed 'O' becomes 'X'
} else if (board[i][j] == 'B') {
board[i][j] = 'O'; // Boundary 'B' becomes 'O' again
}
}
}
}
}
Understood 😀😀
Thank you so much for this. it was helful
understood paaji