G-14. Surrounded Regions | Replace O's with X's | C++ | Java
ฝัง
- เผยแพร่เมื่อ 27 พ.ย. 2024
- GfG-Problem Link: bit.ly/3QyPr5g
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
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
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.
Honestly, Striver!! Amazing LOGIC! If we think of it like you did it becomes a walk in the park!!
UNDERSTOODD!! THANK YOUUU!!
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
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.
Maza aa gya bhayiya ☺☺☺
Lg hi nhi rha tha ki hard problem kr rhe h. Aaisa level set kr dya aapne hm sbka
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
"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...
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 !!!
Barhe log aa gye ...love you warsaw bhaiya ❤️
badhe***
I was trying to solve this question on leetcode this evening and Guess what You uploaded a solution!
I understood your explanation, paused your video and tried it with BFS, it worked. Amazing explanation
YOURE MY DIAMOND STRIVES :)
Aap question aur code dono ko bahut easy bana dete ho bhaiya😀😍
because of you i am easily able to understand graph
thank you sir......
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
Able to solve the problem just by seeing till 2:40 of the video...power of Strivers 😎
same
same
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 :)
Awesome, thank you striver as always understood
able to do this question without watching the solution it really boosted my confidence thaku striver
thanks man,same question came in my cohesity interview 40lpa
Great explanations, I was wondering here for complex problem solution I am getting training as doctor strange got from guru maa in kathmandu!
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
Thank You So Much for this wonderful video............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
kaya bat hai baiya ,maza aagya apka obserwation se
Understood, Thank you so much, this was such a beautiful solution.
thank you striver for creating such amazing content
Solved this one by self on BFS and DFS Both.
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 😅
excellent explanation!
Thank you striver for all your efforts.
solved on my own without watching the video on basis of prev videos and now watching
Understood bhaiya i have done bfs traversal
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❤😂
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.
Thanks a lotttt striver for such an amazing playlist
Understood the solution in first 6 mins.
Paused the video and solved the question in 10 mins 😉
Thank you so much for such a detailed video
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
understood striver
Awesome explanation as always
very nice approach and explanation
understood, thanks for the effort on the great video
Great explanation 👍
// 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
}
}
}
Thank you, Striver 🙂
Thank You striver Bhaiya 🤟
Understood!! Very well explained!!!
Majaa Aagaya😜
day by day getting confidence while doing graph question able to solve this question myself #thanks Wizard Striver
Understood 😊
understood very well!!!
Thank you very much. You are a genius.
Understood Sir, Thank you very much
Understood😁Thanks a lot Striver😃
Legend is back
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
Thank you Bhaiya
khatarnak insted of finding who will be mark as 'X' we will find whol will not such a great idea
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 bhaiya
just watched 1 min and solved the whole problem damn
Understood Bhaiya
You are my inspiration ......................hats offfffffffffffffffffffff
understood paaji
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!!
ek dum mast
#UNDERSTOOD
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
UNDERSTOOD!!!!!!!!
Thank you sir
God of dsa🙏
here we go !
Great intuition
Understood Sir!
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
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 😀😀
Just Wow observation
UNDERSTOOD
Thanks striver
solved without even looking solution that's the power of striver
understood sir
Understood!
Understood thank you sir
Understood 🙂
reached here
😀
Thank you so much for this. it was helful
Thanks you very much bro for the series
understood , thnk u striver
understood