Surrounded Regions | Leetcode

This video explains a very important programming interview problem which is to mark all surrounded regions of zeroes with all X.A group of zero is called a region when the group doesn't have any boundary zero.If a group of zeroes have one or more boundary zero then they will not form a valid region and hence remain unchanged in the result.I have shown 2 approaches for this problem.The first approach is by using 2 DFS calls.Call once to verify if the region is valid and if it is valid then call the second DFS call to convert all 0s to X.The second method is an efficient approach which makes use of DFS to mark all non-region zeroes to 1s and then iterate over the entire matrix to convert all remaining 0s to X and all 1s to 0s again and skip all X.At the end of the video, i have explained the code-walk through for both the depth first search traversal methods.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
DFS: • Depth first search | D...
BFS: • Breadth first search |...
Number of islands: • Number of islands | Le...

[@agileprogramming7463]

OMG Method 2 is just Mind blowing!!..That was grand

[@techdose4u]

😁

[@BoobalanMunusamy]

6:36 Ha ha.. "I know you don't understand anything from this statement " 😀😀😀🤣🤣🤣

[@techdose4u]

😅

[@utkarshdevgan6199]

​@@techdose4u In fact I understood from 6:36 only it is more intuitive and easy approach

[@Learner010]

very nicely explained.. TYPO:- the first block is for first column and last column and ssecond block is for row in second method

[@techdose4u]

😅

[@shubhamedappanavar5660]

Consistency Level==Tech Dose😎😎

[@techdose4u]

😅

[@toofangaming6380]

i am the happiest when i find your video for my problem

[@janvimahajan8447]

Awesome Explanation !!! Thank you :)

[@prernachauhan6262]

the best explanation ever! You are a lifesaver :D

[@techdose4u]

Thanks :)

[@pulkitahuja4750]

I first came up with first approach and submitted but on some case it gave TLE so I had to come up with second approach on my own. Glad I watched your previous videos, I was able to do the second approach myself.

[@techdose4u]

Nice :)

[@fahadisrar2195]

Good work.
Your videos are helpful.

[@Voice_Of_Thoughts]

Every day I will wait for your videos bro thanks for the help...love you bro...

[@techdose4u]

Thanks :)

[@linli7049]

Such clever approaches

[@ishmam8643]

Bro, I have to say this, I watched a lot of videos on different channels bt ur videos are exceptional.

[@techdose4u]

Thanks 😊

[@jolly_dollyyy]

thank you !!!!!!

[@indranilchakraborty4965]

chha gaye guru!

[@kumarnishchay7771]

I think we didn't need to make seen = true in line 55 of 1st solution code since it's a global variable.
If the boundary 0 is touched it seen will automatically mark seen = true as per code and when we go to next iteration we are marking it as false.

[@nagajaswanth831]

The second approach is lit really wooow
Thanks for the explanation sir

[@techdose4u]

Welcome :)

[@SectionF4]

That version is what nearly everyone uses on leetcode. Didn't understand it until this video.

[@spk9434]

Excellent second approach.

[@techdose4u]

Thanks :)

[@videomaster1393]

coool that was helpfulll!

[@techdose4u]

👍🏼

[@ASocial093]

Second approach is 🔥

[@techdose4u]

👍

[@manishsalvi2901]

my approach was similar to 2nd approach
First I called DFS on every O's on boundary and marked all the elements connected to it in DP
and then Iterate through every elements and change O to X if its not marked in DP
here is my code..
class Solution {
public:
void dfs(vector &board,int n,int m,int i,int j,vector &dp)
{
if( im-1 )
{
return;
}
else if(dp[i][j] || board[i][j]=='X' )
{
return;
}
dp[i][j]=true;
dfs(board,n,m,i-1,j,dp);
dfs(board,n,m,i+1,j,dp);
dfs(board,n,m,i,j-1,dp);
dfs(board,n,m,i,j+1,dp);
}
void solve(vector& board) {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n=board.size();
if(n==0)
{
return;
}
int m=board[0].size();
vector dp(n,vector(m,false));
for(int i=0;i

[@venuvenu2719]

I too thought the same approach like this 🙂

[@kushalhu7189]

Perfect

[@thecodingjournal4726]

Omg second approach blew my mind

[@techdose4u]

:)

[@tecocode6070]

Hey there, which app do you use for drawing?

[@ShubhamMahawar_Dancer_Actor]

Hello can you explain a lil'further i am not getting your this condition if(i=r-1 || j=c-1)
ch=true; ..how this says that region is not surrounded?

[@santoshkumar-sh3sb]

in the previous if we had written if he had seen x then return , so we would come to this case only if we see a O at the end of the row or column and as stated in qn surrounding regions should not be in border

[@siddhartha.saif25]

thank you!

[@techdose4u]

Welcome :)

[@noobCoder26]

2nd approach is insane

[@techdose4u]

👍🏼

[@upendraroul343]

The explanation is very good. Just curious, what is the notepad you are using in your videos?

[@techdose4u]

Wacom pro

[@davidjonson303]

2nd approach mast hai😅

[@ankurgupta4696]

thanks for the explanation😊😊

[@techdose4u]

Welcome :)

[@shivamkumar_0924]

ultimate destiny for my doubts 🙏

[@techdose4u]

👌🏼

[@gnanaeswarm727]

Approach - 2 was smoooooth

[@techdose4u]

Yea :)

[@sandeepraja1470]

THANKS FOR THE EXPLANATION!!!
JAVA SOLUTION
---------------------------
class Solution {
public void solve(char[][] board) {
if(board == null || board.length == 0) return;
int rows = board.length;
int cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];
//traverse all boundary elements
//when encounter O, make all the connected O's to 1
//first and last row
for(int j = 0; j < cols; j++) {
if(board[0][j] == 'O') {
dfs(board, 0, j, visited);
}
if(board[rows - 1][j] == 'O') {
dfs(board, rows - 1, j, visited);
}
}
//first and last column
for(int i = 0; i < rows; i++) {
if(board[i][0] == 'O') {
dfs(board, i, 0, visited);
}
if(board[i][cols - 1] == 'O') {
dfs(board, i, cols - 1, visited);
}
}

//traverse through all the elements
//change 1's to O and Os to Xs
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(board[i][j] == 'O') {
board[i][j] = 'X';
}
if(board[i][j] == '1') {
board[i][j] = 'O';
}
}
}
}

public void dfs(char[][] board, int i, int j, boolean[][] visited) {
if(i < 0 || j < 0 || i >= board.length || j >= board[0].length || board[i][j] == 'X' || visited[i][j]) {
return;
}
//visited to true to avoid traversing the same elements
visited[i][j] = true;
//when encounter O, make all the connected O's to 1
board[i][j] = '1';
dfs(board, i, j - 1, visited);
dfs(board, i, j + 1, visited);
dfs(board, i - 1, j, visited);
dfs(board, i + 1, j, visited);
}
}

[@techdose4u]

👍

[@raviagarwal4287]

ProgrammingMeans == TECH DOSE
Thank You!

[@ece116pranaykumar4]

best

[@kushagragupta979]

Same as islands problem ☺️☺️

[@techdose4u]

Correct. Very similar :)

[@ritesh1211]

Getting runtime error in second approach

[@nobita7231]

Sir I'm bad at maths. Can i still become good programmer?? Or give me suggestions

[@techdose4u]

Nobody good at maths from the beginning. Also, most important chapters are permutation combination, series expansion, probability, graph theory, game theory. Syllabus is not very big.

[@arinmodi8884]

Another Solution Is to store the border points then do DFS for each of the border points and store the index of traversed element, then we can just traverse over matrix and check weather that element is traversed or not, if not we will change it to X otherwise leave it O

[@kushgupta1187]

Another approach is to first check boundaries by calling dfs and fill all surrounding region 0 with v.
Now simply iterate and change 0 to x and v to 0

[@techdose4u]

Please watch the complete video. This is approach-2.

[@kushgupta1187]

Thanks for replying :)

[@user-cp1px6vm9t]

in solution1, at line 55, seen = true is redundant.

[@chandrukumar8131]

sir you did any bfs video? if did please send.

[@techdose4u]

I gave a link for BFS in description. Also, check my ROTTEN ORANGES lecture.

[@chandrukumar8131]

@@techdose4u thank you sir

[@techdose4u]

👍

[@karankanojiya7672]

Excellent Sir! Respect ++ for explaining the 2nd Approach.
Java Code for 2nd Approach
class Solution {
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0) return;
if (board.length < 3 || board[0].length < 3) return;
int m = board.length;
int n = board[0].length;
for (int i = 0; i < m; i++) {
if (board[i][0] == 'O') helper(board, i, 0);
if (board[i][n - 1] == 'O') helper(board, i, n - 1);
}
for (int j = 1; j < n - 1; j++) {
if (board[0][j] == 'O') helper(board, 0, j);
if (board[m - 1][j] == 'O') helper(board, m - 1, j);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 'O') board[i][j] = 'X';
if (board[i][j] == '*') board[i][j] = 'O';
}
}
}

private void helper(char[][] board, int r, int c) {
if (r < 0 || c < 0 || r > board.length - 1 || c > board[0].length - 1 || board[r][c] != 'O') return;
board[r][c] = '*';
helper(board, r + 1, c);
helper(board, r - 1, c);
helper(board, r, c + 1);
helper(board, r, c - 1);
}
}

[@techdose4u]

Thanks

[@shivanisen4356]

Getting wrong output in second approach

[@nikhilnaidu1383]

time limit exceeded for approach 1

[@HimanshuSingh-ob9qo]

👌👌👌👌👌👌🤘👍🙏

[@techdose4u]

👍

[@sivasudharshan2917]

I like your videos...

[@thunderbolt8632]

Bhai dekh to le puri video pehle

[@spetsnaz_2]

@@thunderbolt8632 xD

[@techdose4u]

😂LOL Thanks.....enjoy :)

[@sivasudharshan2917]

@@thunderbolt8632 dekne ki pehle bata sakthe hoo q ki mee iska vedios already dhek chuka hoon dynamic programming ka..

[@techdose4u]

Thanks bro :)

[@rks3522]

11:05 , 11:50
12:35

[@najimali32]

Java Code for Second Approach:
class Solution {
int direction[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, 0 - 1 } };
public void solve(char[][] board) {
int row = board.length;
int col = board[0].length;
if (row < 3 || col < 3)
return;
for (int j = 0; j < col; j++) {
if (board[0][j] == ZERO) {
fill(board, 0, j);
}
if (board[row - 1][j] == ZERO) {
fill(board, row - 1, j);
}
}
for (int i = 1; i < row - 1; i++) {
if (board[i][0] == ZERO) {
fill(board, i, 0);
}
if (board[i][col - 1] == ZERO) {
fill(board, i, col - 1);
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == ONE)
board[i][j] = ZERO;
else if (board[i][j] == ZERO)
board[i][j] = CROSS;
}
}
for (char rows[] : board) {
System.out.println(Arrays.toString(rows));
}
}
final char CROSS = 'X';
final char ZERO = 'O';
final char ONE = '1';
void fill(char board[][], int x, int y) {
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != ZERO)
return;
board[x][y] = ONE;
for (int i = 0; i < direction.length; i++) {
int nx = x + direction[i][0];
int ny = y + direction[i][1];
fill(board, nx, ny);
}
}
}

[@dhananjaysinghsawner2324]

Thank you for explanation. I have been following this series of videos from beginning. I like your method of explaining.
I am trying to solve this question with another approach(although not optimum) but I am stuck on a step from last 3-4 days and can't figure out why it's not working. Please help me out in this, any sort of help would be appreciated. Below is my code :
class Solution {
public:
bool dfs(vector& board,int i,int j)
{
if(board[i][j]=='X')
{return true;}

if(i==0||j==0||i==board.size()-1|| j==board[0].size()-1)
{return false;}

if(board[i+1][j]=='X' && board[i-1][j]=='X' && board[i][j+1]=='X' && board[i][j-1]=='X')
{
board[i][j] = 'X';
return true;

}

board[i][j] = 'X';
//making current O as X and checking if all of its neighbours return true then keep it as X else turn it back to O

bool b1 = dfs(board,i+1,j);
if(b1==false)
{
board[i][j]='O';
return false;
}
bool b2 = dfs(board,i-1,j);
if(b2==false)
{
board[i][j]='O';
return false;
}
bool b3 = dfs(board,i,j+1);
if(b3==false)
{
board[i][j]='O';
return false;
}
bool b4 = dfs(board,i,j-1);
if(b4==false)
{
board[i][j]='O';
return false;
}

if(board[i][j]=='O')
{return false;}

return true;
}

void solve(vector& board) {

for(int i=0;i

[@md_aaqil8027]

Java Solution
class Solution {
public void mark(char[][] b,int x,int y,int r,int c)
{
if(b[x][y]=='O')
{
b[x][y]='1';
if(x>1)mark(b,x-1,y,r,c);
if(y+1

[@techdose4u]

👍