Surrounded Regions - Graph - Leetcode 130 - Python

[@NeetCode]

💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc

[@EmranKamil-cc9xc]

Honestly, I rarely finish your lectures because you're so genius that after just a few minutes, I start to grasp the way the solution should be solved. I end up solving the problem the same way you do it at the end of the video. Thanks a lot, NeetCode!

[@derekojeda6861]

Thank you! Your videos have been highly beneficial. Keep up the excellent work!

[@luiggymacias5735]

thank you, i really appreciate it!!!

[@ayoubalem865]

Hey Neetcode you can merge the last two for loops on one: you can check if board[i][j] == "O": board[i][j] == "X" elif board[i][j] == "T": board[i][j] = "O"

[@texyo]

Yeah thats what i was thinking; why are these two steps separate?

[@ayoubalem865]

@@texyo he might want make it more Clair and easy to understand !

[@YellowBuffaloNBAvideosmore]

@@ayoubalem865 Nope, because otherwise T will be changed to O, and then it will be changed to X which we don't want!

[@ayoubalem865]

@@YellowBuffaloNBAvideosmore we are not making a depth first search to change the cells with char O, we are visiting each cell one time, ur case would be correct if we are making a dfs to change O to X with dfs wich is not our case !

[@rommeltito123]

@@YellowBuffaloNBAvideosmore That will not happen since we dont revisit a changed cell again.

[@TheNishant30]

it's fairly common in graph problems to have a solution to the inverse of the problem be much easier than the solution to the actual problem itself. The Algorithm book by dasgupta, used in UCB, also mentions this. The backbone idea behind why this works is because if A is reachable from B, then B is also reachable from A. This is why in connected components of a graph, the exploitation of this very simple idea leads to a fairly simpler solution. Pacific-atlantic water flow, 0-1 matrix, surrounded regions, and many more questions can be solved in a much simpler way if we carefully observe the inverse problem. Even when we try to find all the SCC in a graph, we try to find the sink SCC of the graph first, but since it cannot be calculated directly, we reverse the graph (G^-1), find it's source because source can be calculated easily, and this source becomes the sink of the actual graph. Again, calculating the solution to the inverse of a problem leading to an actual solution. I think it's called the kokuraja's algorithm or something.

[@HarisHussain]

This was an awesome comment on how to derive such intuition

[@imerence6290]

Banger comment

[@nivgartzi1686]

Exactly. Btw - the algo u r reffering to is called "Kosaraju-Sharir".

[@irlporygon-z6929]

kokuraja 😭😭 Kosaraju's algorithm

[@Rob-147]

This question was driving me nuts! As soon as you said reverse the question a light popped in my head. Go to the borders and see what nodes shouldn't be flipped! thanks so much. another great video. you are a legend

[@Chewibub]

The talk about "reverse thinking" blew my mind! Just hearing that portion I was able to instantly go back and do this problem (and use the same style of thinking on several future problems that I didnt even consider).

[@WhoMePrime]

Thanks for the video! Just an add on; instead of changing the O's connected to the border to T and then having to change them back at the end, you could simply put the locations in a set and then when running over the matrix to find the O's to switch to X, you can just see if those coordinates are not in the set before you change it.

[@markolainovic]

As a downside, using a set is probably going to slow down the code a lot.

[@Kidpunk98]

@@markolainovic You can use a Matrix, its faster than as set. Whether you store the marked ones, or temporary change them, its good to mention both approaches and their trade offs. One would require a second pass over the 2dArray (slower, less space), and the other will not (faster,more space).

[@pacomarmolejo3492]

@@Kidpunk98 great answer. I would rather use the 'T' approach as a double pass does not affect Time Complexity, but a set or matrix would impact Space Complexity.

[@juggles5474]

@@markolainovic minimally, i would imagine. adding to and checking a set is constant time complexity, as is altering an array element

[@bobert6259]

@@markolainovic No, lookups and additions in sets are O(1). Accessing a grid is O(1) and checking its value is also O(1), so technically it's the same runtime.

[@gabchen3000]

Along the same thought process, I found it easier to 1.mark the "O"s connected to any sides in a set, then 2.flip any "O" that aren't in that set to "X". Very similar to the Pacific Atlantic water flow question. Here is my code: def solve(board): ROWS, COLS = len(board), len(board[0]) noflip = set() def dfs(r,c): if r < 0 or r >= ROWS or c < 0 or c >= COLS or (r,c) in noflip or board[r][c] == "X": return noflip.add((r,c)) dfs(r+1,c) dfs(r-1,c) dfs(r,c+1) dfs(r,c-1) for r in range(ROWS): dfs(r,0) dfs(r, COLS-1) for c in range(COLS): dfs(0,c) dfs(ROWS-1,c) for r in range(ROWS): for c in range(COLS): if board[r][c] == "O" and (r,c) not in noflip: board[r][c] = "X"

[@alial-jabur6453]

I rllly like your approach

[@bobert6259]

Nice, I did the soln the same way as you basically. Minor improvements - you can add a check to see if (r, c) is in noflip before you do dfs so you don't have to do extra checks inside the function before returning.

[@spiceybyte]

Awesome intuition thanks for sharing

[@donghyunsuh4469]

This was the best approach for me, especially since I solved this question right after the pacific atlantic one. Thanks!

[@AsifIqbalR]

I think the step 2 and 3 can be done together. You can just have an else if and check is the value is equal to T just like the third loop

[@anhngo581]

Good point!

[@isaaclian11]

Thanks!

[@NeetCode]

Thank you so much!

[@rrdevyt]

Fantastic video! I've got FB interviews coming up next month and your videos have been unbelievably helpful.

[@osinakayahifeanyi1537]

How did it go?

[@rrdevyt]

@@osinakayahifeanyi1537 I landed an offer 😁

[@osinakayahifeanyi1537]

@@rrdevyt That is really awesome congratulations.😁

[@rrdevyt]

@@osinakayahifeanyi1537 Thank you! :)

[@blutoo1363]

@@rrdevyt You still got your job?

[@hungmol5989]

Reverse thinking, a beautiful solution. Thank you so much!

[@mdk124]

Thank you Neetcode for all the videos you've done, I really do love your content and it gives me confidence to continue down your roadmap knowing that your videos are super clear. I've just signed up for Neetcode pro to give my thanks on how much your videos have helped. I look forward to your channel and site growing!

[@harshitsingh2118]

This question seemed very tough at once but after seeing your solution it became very easy. Thanks a ton.

[@anshitasaxena3992]

recursive dfs is simpler, but for those who are searching for iterative bfs solution, here it is in neetcode style: class Solution: def solve(self, board: List[List[str]]) -> None: rows, cols = len(board), len(board[0]) def bfs(r, c): board[r][c] = "T" q = collections.deque() q.append((r, c)) while q: row, col = q.popleft() directions = [[1, 0], [-1, 0], [0, 1], [0, -1]] for dr, dc in directions: r, c = row + dr, col + dc if r in range(rows) and c in range(cols) and board[r][c] == "O": board[r][c] = "T" q.append((r, c)) for r in range(rows): for c in range(cols): if (r in [0, rows-1] or c in [0, cols-1]) and board[r][c] == "O": bfs(r, c) for r in range(rows): for c in range(cols): if board[r][c] == "O": board[r][c] = "X" for r in range(rows): for c in range(cols): if board[r][c] == "T": board[r][c] = "O"

[@letscode1000]

This is incredible smart method and makes the dfs so meaningful

[@__amkhrjee__]

The whole "reverse thinking" thing was mind blowing!!!

[@DontBlink911]

That is such a GENIUS and CLEVER solution!

[@Dan1FB1mgr]

תודה!

[@NeetCode]

Thank you 🙏

[@cachestache2485]

You don't need the second nested loop, you can just call the if statement for "T" right in nested loop for point #2 right after the check for "O". Just a small optimization.

[@MinhNguyen-lz1pg]

Dude, awesome visualization and explanation. What a champ!

[@Maaaaars]

Got this Problem for my onsite at Amazon. I fumbled it lol.

[@symbol767]

Damnnnnnnnn I am so dumb lol, I marked all the nodes like you did, except I used a visited set, your idea was better to just mutate the matrix and return it to normal at the end. But after turning all the border O's to T's I went and did another DFS, I just looked at my code again and I'm saying to myself "Whyyy am I doing another DFS? I could just iterate and flip all the O's to X's in the double for loops" Silly mistakes lol Thank you man

[@greentea_vsrg]

I initially solved this with BFS, your solution is so much smarter!

[@alanmangroo3656]

Great explanation! You make it sound so simple.

[@nathantokala5643]

Hey do you have a regular donation link available? Prefer one time donations over monthly through Patreon, and want to support the channel that landed me a FB offer!!

[@NeetCode]

Firstly, congrats on the offer! I'm happy your hard work paid off :) Also, donations are completely optional, but if you would like to support the channel there should be a "Thanks" button underneath the video, right next to the "Share" button.

[@SaiPavanPothuri]

Superb explanation :D Defacto standard of KZbin channel which explains the logic of leetcode problems is your channel. Hats off to your work and explanation :D

[@maitreyakanitkar8742]

Brilliant, absolutely brilliant !!!!!

[@gopalchavan306]

pretty impressive the way you wrote the code for checking edges

[@navaneeth67]

Oh boy, reverse thinking got me. How does one come up with that naturally, simple yet brilliant

[@lemonke8132]

Personally instead of "capturing" squares by turning O's into T's, I just added their coordinates to a set and then flipped all O's that weren't in the set.

[@midasredblade236]

would that be faster?

[@anhngo581]

@@midasredblade236 I think so yea, because now you don't have to check the whole board again. But the catch is that this method needs more space to store the set

[@cosepeter2197]

Did the same

[@juggles5474]

@@midasredblade236 i got 90% faster runtime on leetcode by using a set

[@dusvn1484]

Amazing video after half of explanation I'm able to solve by my self.

[@n-julkushwaha2827]

one of the most unique solutions i have seen for this problem.........

[@arzelaascoli6765]

I think a much simpler solution is to check if a region is valid - doesn't touch the edge - and if it is, mark it immediately. This is a simple 2-pass solution (though both passes use DFS).

[@m_jdm357]

Thank you for the easy to understand solution.

[@licokr]

Think differently.. I think that is really important to solve creatively and also find a better way. Like transform a question into another question that has the same answer.

[@dheepthaaanand3214]

The reason we don't need a visit set in the dfs is because already visited cells would be T and we also want to not proceed if we see an X, so a simple comparison to not O is enough

[@nayandhabarde]

I tried combining last two forloops it still works basically do for loop over r and c , then if item is O make it X, if item is T make it O

[@moveonvillain1080]

Thought of it in a slightly different manner. I had solved the Pacific Atlantic before this one so approached it the same way. Move from first row and last row and for each column if it's an 'O' then start exploring and find the connected 'O' and put them in the "safe" set. Do the same thing for left most and right most column and for each rows in those columns. Now loop through the board and if r,c is part of the safe set then continue. Otherwise make it 'X'. Time Complexity: O(m*n) Space Complexity: O(m*n); Main intuition was that if the 'O' on border connects to more 'O' then all of these connected 'O'(s) are safe.

[@LeetCodeMastery-y9d]

The main catch in your solution is that you start from the edges of the board and omit all the regions that for sure won't be captured.

[@kirillzlobin7135]

Amazing explanation and quality of the video

[@karthiklv29]

instead of replacing O to T, just use the visited matrix, and if its not visited make the Os to Xs :). Thanks for the video though

[@ARNAVGUPTA-s1m]

The point of doing board[r][c] != "O" is better than saying == "X" since now we also inculcate the visited_set feature

[@LunaFlahy]

BFS: 1. traver boarder, flood fill the region with '-' 2. set all remaining cells into 'X'

[@Z00keeper54]

For some reason, I find the text of the problem confusing, even though the actual problem is very easy, so here is a version that makes more sense to me and might help others. Problem: You are given a 2-D grid made of water (X) and islands of land (O). Find all islands that don't touch the border (ignoring diagonals), and sink them into the water. Solution: Scan the borders for land and use DFS to "shield" those islands (set O to T). Next sink the unshielded islands (set O to X). Finally remove the shields (set T to O).

[@QuantizedFields]

These videos are all great (thanks for your hard work), but I feel like you spend a lot fo time explaining the simple things, like the logic of the algorithm, and then very quickly go over the hardest part, i.e. the implementation of the idea - coding. For me the hardest part is to code up the idea. Most of the time I cannot relate your codes to your previously explained ideas, they seem to be disconnected (not always, but for most part). I would appreciate it if you could explain the coding itself slowly, and explain why your code is working and what kind of output it generates. I spend a lot of time deciphering your code, and sometimes have to watch other videos that explain the coding part itself clearly, or read some articles, and only then understand your code. Overwall, great job!

[@farazahmed7]

I have a Google interview coming up. Wish me luck

[@NeetCode]

Good luck!

[@luiggymacias5735]

did you pass the interview?

[@a_jaycee8643]

Question : Let's say for Example one , the top of zero (on the border) is zero wouldn't the capture method not work bcuz it pass the base case and change to "T" (as we want to change only the border) . Or unless would that make it a whole region and not pass the case of being surrounded by X lol.

[@electric336]

Really great solution and explanation. Thanks for this.

[@peanutbutter785]

Why don't we have to check if it is already visited or not in a dfs? Would someone explain for me? Btw, thanks for a good video!

[@Techgether]

i came up with another reverse thinking with his base logic: - Add all 'O' elements to a set - BFS through all 'O' elements that are adjacent to the edges, if found 'O' elements (that are not adjacent to the edges) then remove from set - The remaining values in set will be the answers so just replaced to 'X' class Solution: def solve(self, board: List[List[str]]) -> None: ROWS, COLS = len(board), len(board[0]) total = set() visited = set() q = collections.deque() for r in range(1,ROWS-1): for c in range(1,COLS-1): if board[r][c] == 'O': total.add((r,c)) for r in range(ROWS): for c in range(COLS): if board[r][c] == 'O' and (r in [0,ROWS-1] or c in [0,COLS-1]): q.append((r,c)) visited.add((r,c)) directions = [[1,0],[-1,0],[0,1],[0,-1]] while q and total: visited.add((r,c)) r,c = q.popleft() for dr, dc in directions: row = dr + r col = dc + c if (row < 0 or row == ROWS or col < 0 or col == COLS or (row,col) in visited or board[row][col] == "X"): continue if (row,col) in total: total.remove((row,col)) q.append((row,col)) for r,c in total: board[r][c] = "X"

[@hari8568]

I was thinking apply BFS by finding number of connected components,for each component keep 2 separate dictionaries, the first dictionary has key as the connected component (say 1st cc) and value as a list with coordinates stored as tuple, the next dictionary also has key as cc and value as list with 1st index having a set corresponding to row index and second index having a set column index . Now what we do is find each coordinate of cc and store the coordinates in coordinated dict and surrounding region row and column which have x in the 2nd dictionary.Travetse entire array then again pick the conncted components array ,each coordinate of a ,4 sided cc should have left right up or down at least 1 x value if so flip all those O

[@baibhavghimire3827]

This is awesome bro..If i land a job of TC greater then 350k, 1k will be coming as a gift from my side to you!

[@undercoverpepe5642]

earned my sub. great content bro

[@maitreyakanitkar8742]

Dude, I wish I had 1/4th of the intelligence you possess. You could have spent your days churning money at any big company but you chose to teach us mortals.

[@erik-sandberg]

Great solution!

[@ygwg6145]

Except for the first step of finding the starting point, walking around the border clockwise or counterclockwise using dfs would be faster: O(m+n).

[@mahadishakkhor123]

Very helpfull to understand

[@kalyan755]

@NeetCode, I love your explanations. I have a question about this video. You said the first for loop is only to change any O's in the boarder to T's. But when we run dfs if there are any inner(non-boarder) cells which has O and which is attached(horizontally or vertically) to a boarder O then the dfs turning it also to T. For example, [["X","X","X","X"],["X","O","O","X"],["X","O","O","X"],["X","O","X","X"]] [["X"]], this input while debugging, after the first for loop completion all the O's turned into T's(including inner(non-boarder) O's). I know the final answer is accepted in leet code, but i am i missing anything here with respect to your explanation about first for loop.

[@nameless2850]

I think you misunderstood the question... It's not about the cell, it's about the region with 4 directional X's.. so

[@huseyinbarin1653]

Actually, the strategy is correct here because you need to find all the `O`(s) which are connected to border `O`(s). That's why we are doing dfs for each `O` in the border. If they are connected to any border `O` then it cannot be "surrounded" so the rest can be surrounded after marking those `O` as T. Then as a final step we should change all the Ts back to `O`s again.

[@wmiyu5163]

I had the same confusion. In your example, shouldn't the result be the same as the original array? [ ["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "O", "O", "X"], ["X", "O", "X", "X"] ]

[@nikhilaradhya4088]

We can do aspiral traversal on the matrix instead of using recursive function calls

[@thndesmondsaid]

this is the first solution of yours that I've watched but not completely understood. How does this algorithm handle the edge case where within the border you have O's, but along the border you have all O's that you set to T. In that case, what is preventing the O's within the border from being converted to X's?

[@thndesmondsaid]

Oh I see, since you're calling DFS on the border O's, this allows you to travel within the grid and set the neighboring O's within the border to T as well. At first I was thinking that only O's on the border would be converted to T's. Thanks neetcode!

[@linhnguyenduc641]

Reverse thinking is awesome

[@raghavpatnecha8551]

The solution works, but during the explanation , you said we mark the border O's as T and capture everything not surrounded. But what I think is it won't work for this test case : [ "XOX", "XOX", "XOX" ], as it will make the middle 'O' zero which shouldn't be the case

[@SaahasBuricha]

great video

[@pratikmhatre4815]

Superb solution

[@akshayh5795]

Can anyone please help me understand how the "o" in the middle is not turning into "T" because inside capture we are doing multiple recursion in all direction so how does the "o" present either on bottom or top will not a replaced by "T"

[@mercerkace2023]

class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ ROWS, COLS = len(board), len(board[0]) def dfs(r, c): if r < 0 or c < 0 or r == ROWS or c == COLS: return if board[r][c] == "T" or board[r][c] == "X": return board[r][c] = "T" dfs(r+1, c) dfs(r-1, c) dfs(r, c+1) dfs(r, c-1) for c in range(COLS): if board[0][c] == "O": dfs(0, c) if board[ROWS-1][c] == "O": dfs(ROWS-1, c) for r in range(ROWS): if board[r][0] == "O": dfs(r, 0) if board[r][COLS-1] == "O": dfs(r, COLS-1) for r in range(ROWS): for c in range(COLS): if board[r][c] == "T": board[r][c] = "O" else: board[r][c] = "X" Same solution with easy loops

[@AkkiHacks-ob8kb]

For this question, I tried to do by bfs first, and I got a TLE on 56th Testcase in Leetcode. Can anyone tell me why bfs doesn't work?

[@chenzhuo9]

Heyyy!!! Could we have some Patron option like one could ask you to do a question if he has donates X amount!!

[@nickold4499]

How come we can't just check in the first for loop for "O's" in the border and just convert them to T within that loop? I know it doesn't work but can't understand why. Thanks

[@ijustdey]

Because we also want to change the neighboring 'O's of the border 'O's to T as they're unsurrounded as well. That's why we find them recursively. If only the Os in the borders are unsurrounded then we can just capture them in the loop at one without recursion.

[@lukewiles5969]

A little optimization from my solution: I only ran DFS on the border rows/cols.

[@kSergio471]

Is it worth trying to avoid recursion and use heap-based stack (which is not easy)? Or really nobody cares?

[@programming1734]

Doesn't these hurt at situations where O area extends till a border? There we can't capture the whole area since it won't be covered from 4 sides.

[@Andrew-dd2vf]

If O area is connected to the border, the nature of the DFS algorithm (phase 1 of code in the video) will ensure that those areas connected to the border will be turned into a "T", and thus be counted as "unsurrounded" area

[@mr.probable1236]

Great video. Is anyone able to explain why we can’t just iterate through the matrix and see if, once we landed on a O “island”, we can connect that to an edge of the matrix - and return a boolean of whether the value should be “captured” accordingly? I initially tried doing this through DFS, but to no avail, and only then thought to try the approach in the video. However, I still cannot understand why the other method fails. Can anyone explain? Thanks!

[@gabchen3000]

This was my initial approach as well, it doesn't work because the "O"s rely on the decision of another "O". As an example the dfs looks something like this: if out of bound or in visited: return False if board[r][c] == "X": return True visited.add((r,c)) if dfs(right) and dfs(left) and dfs(up) and dfs(down): board[r][c] = "X" return True else: return False [X, O, X, X] [X, O, O, X] [X, X, X, X] When I survey (1,2) I rely on visited to return False, but since I got to (1,2) due to dfs call from (1,1) in the first place, I still don't know (1,1) is on the edge cause I'm still waiting for the result of dfs(right) before I go dfs(left). This will cause a false positive and flip a "O" when you're not suppose to.

[@mehdihassan93]

why can't we add the boarder one into a set and ignore if already in the set

[@asdfgsf9660]

I don't understand how this approach accounts for the edge case when and a surrounded region is directly connected (not diagonally) to an O on the border. Can someone explain?

[@anhngo581]

An O on the border shouldn't be flipped. Since the region is directly connected to this O, this whole regions shouldn't be flipped. So, Neet's way still works as we will mark these regions T when we run capture(r, c) from the border.

[@bluesteel1]

This is very similar to pacific Atlantic water flow

[@TechOnScreen]

we could also do it using hashmap , but seems its not efficient , only 8 percent on LC

[@ary_21]

class Solution { public: bool dfs(vector &m, int row, int col, int i, int j) { if (i < 0 or i >= row or j < 0 or j >= col) { return false; } else if (m[i][j] == 'X') { return true; } else { // its an O hence we return the status of the current O m[i][j]='X'; bool res = dfs(m, row, col, i - 1, j) & dfs(m, row, col, i + 1, j) & dfs(m, row, col, i, j - 1) & dfs(m, row, col, i, j + 1); if (res == false) { m[i][j] = 'O'; } return res; } } void solve(vector &board) { int row = board.size(); int col = board[0].size(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'O') { bool res = dfs(board, row, col, i, j); if(res==false){ board[i][j]='O'; } } } } } };

[@jhguygih]

Why he says we should flip the borders to T and proceeds to mark the center as X. Then later on the code in the dfs he marks everyone to T. I didnt get why that was not brought in the explanation. I actually solved by using DFS and adding to a list and undoing all the wrong flips, which was slow even with visited map.

[@TKNinja007]

Jesus you know its bad when I was reading Only A as O( nlog(A))

[@deyoz1]

Omg this is 👍

[@matthewsaucedo2471]

Not the answer shown here, but: Any ideas why this is incorrect? class Solution: def solve(self, board: List[List[str]]) -> None: i, j, visited = 0, 0, set() def dfs(r, c, visited): if (r, c) in visited: return True visited.add((r,c)) directions = [(r+1,c), (r-1,c), (r,c+1), (r,c-1)] for direction in directions: # check border cases if ( direction[0] == len(board) or direction[0] < 0 or direction[1] == len(board[0]) or direction[1] < 0 ): return False if board[direction[0]][direction[1]] == "O" and not dfs(direction[0], direction[1], visited): return False return True while i < len(board): while j < len(board[0]): if board[i][j] == "O": shouldCapture = dfs(i, j, visited) if shouldCapture: for coord in visited: board[coord[0]][coord[1]] = "X" visited = set() j += 1 i += 1

[@branmuller]

What if all the border cells are 0s?? Does this account for that?

[@anhngo581]

Then, I think this code will run capture on all the border cells

[@rapscalliondave]

This is wrinkling my brain.

[@kingdan9332]

def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ rows, cols = len(board), len(board[0]) visit = set() def dfs(r,c): if ( r not in range(rows) or c not in range(cols) or board[r][c] == "X" or (r,c) in visit): return visit.add((r,c)) dfs(r+1,c) dfs(r-1,c) dfs(r,c+1) dfs(r,c-1) for r in range(rows): for c in range(cols): if board[r][c] == "O" and (r in [0, rows -1] or c in [0, cols -1]): dfs(r,c) for r in range(rows): for c in range(cols): if board[r][c] == "O" and (r,c) not in visit: board[r][c] = "X"

[@kingdan9332]

The swap/swap/swap solution is kind of silly so this looks at the first row/first col/last row/last col and puts them in a set to be ignored on the eventual capture

[@armandomendivil1117]

Leetcode says TC O(N) and SC (ON), I think is O(N*M) like this video

[@amynguy]

board[r][c] = 'O' if board[r][c] == 'T' else 'X'

[@milk_steak_the_original]

isn't that a double negative ? "except unsurrounded regions" != "except surrounded regions"

[@subhamsingh9205]

@NeetCode what would be the complexity of this solution?

[@ChanChan-pg4wu]

Neet solution!

[@Ryan-sd6os]

why don't you just interate through (1, ROWS-1) and (1, COLS-1), that would avoid any borders

[@shuoliu3546]

a boundary pixel can be connected to its next pixel which is not at boundary

[@TheTopProgrammer]

Never got to hear the airplane ✈️ :(

[@CEOofTheHood]

class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ if len(board)==1: return board DIRS=((0,1),(1,0),(-1,0),(0,-1)) visited=set() #simple dfs def dfs(r,c): deq=deque() deq.append((r,c)) visited.add((r,c)) while deq: r,c=deq.popleft() for dir in DIRS: newr,newc=dir[0]+r,c+dir[1] if 0

[@Hiroki-Takahashi]

genius

[@JamesBond-mq7pd]

why do you think about my solution? class Solution: def solve(self, board: List[List[str]]) -> None: ROWS, COLS = len(board), len(board[0]) visited = set() def dfs(r, c): if r < 0 or c < 0 or r >= ROWS or c >= COLS or (r, c) in visited or board[r][c] == "X": return visited.add((r, c)) dfs(r + 1, c) dfs(r - 1, c) dfs(r, c + 1) dfs(r, c - 1) for c in range(COLS): dfs(0, c) dfs(ROWS - 1, c) for r in range(ROWS): dfs(r, 0) dfs(r, COLS - 1) for r in range(ROWS): for c in range(COLS): if board[r][c] == "O" and (r,c) not in visited: board[r][c] = "X"

[@sumitsharma6738]

Reverse Engineering !!

[@saunaknandi1814]

Is there any opening in Google for SDE?

[@nikhil199029]

Dfs is easier