This is crazy. This problem should be hard. Is it just me who solved island type problems 10+ times but could not associate this is similar to that? I was looking at if there are patterns to count regions row wise.
take the grid and make it 3 times bigger, no way a normal person would think of exactly that in an interview. Thanks for the run Neetcode! Btw no streams for a quite a while, hope to see them back soon
I managed to solve that question with 2n X 2n grid instead of 3x X 3x. I replace / with 1 and \ with -1 and call dfs for all direction as well as for diagonal for specific condition and it works! class Solution: def regionsBySlashes(self, grid: List[str]) -> int: n = len(grid) main_grid = [[0 for _ in range(n*2)] for _ in range(n*2)] m = n*2 for i in range(n): for j in range(n): if grid[i][j] == '/': main_grid[i*2 + 1][j*2] = 1 main_grid[i*2][j*2 + 1] = 1 elif grid[i][j] == '\\': main_grid[i*2][j*2] = -1 main_grid[i*2 + 1][j*2 + 1] = -1 visited = set()
def dfs(i, j): if i == -1 or j == -1 or i == m or j == m or main_grid[i][j] or (i, j) in visited: return
visited.add((i, j)) dfs(i, j+1) dfs(i+1, j) dfs(i, j-1) dfs(i-1, j) if i != 0 and j != m-1 and main_grid[i-1][j] != -1 and main_grid[i][j+1] != -1: dfs(i-1, j+1)
if i != m-1 and j != 0 and main_grid[i][j-1] != -1 and main_grid[i+1][j] != -1: dfs(i+1, j-1)
if i != m-1 and j != m-1 and main_grid[i][j+1] != 1 and main_grid[i+1][j] != 1: dfs(i+1, j+1)
if i != 0 and j != 0 and main_grid[i][j-1] != 1 and main_grid[i-1][j] != 1: dfs(i-1, j-1)
ans = 0 for i in range(m): for j in range(m): if main_grid[i][j] == 0 and (i, j) not in visited: dfs(i, j) ans += 1
You need to check to definition of big o notation. You don't add the constants to the notation as they are not defining factors on runtime complexity or space complexity as the input size reaches infinity.
Hey @neetcodeIO .You can use Ctrl+D to "select next occurrence". It will help you correct stuff faster/more easily. I've noticed you edit separately (like you did in 15:36 with the grid2) in several vids and just thought to point it out.
This is flood fill algorithm. I realized it the moment I read the problem statement. I watched this video, the moment i heard that i can divide the char into a grid of 3x3, I understood the problem, solved it myself.
I managed to solve this one by dividing each cell into 4 triangular quadrants along the diagonals - this way each cell has a top, left, right, and bottom. If a "/" is in the cell, the top and left of that cell are connected, and right and bottom are connected. If a "\" is found, the top and right are connected, and the left and bottom are connected. If " " is found, the top, left, bottom, and right are connected. Each cell's edge is also connected to its neighbouring cell's edge (eg. a cells top edge is connected to the above cell's bottom edge). I made an adjacency list of these connections, and then ran union find on them. Similar to you, although my solution worked it didn't rank very high in either time or space metrics.
Same way as I did it. But I did not create an extra adj list, coz u can find the indices of elements in the "parent" to join directly while iterating through the grid.
Great approach! But you don't have to separately create an adjacency list of these connections, just look for neighboring elements of the cell based on your diagram. Also, you can solve it using simple dfs as well (i.e. without union-find).
@@corrogist692 That's a very good point about the need to not have an adjacency list, and I'm a little embarrassed that I didn't think of that. Thank you for pointing that out to me!
@@33galactus That's a very good point about the adjacency list being unnecessary, I honestly can't believe I didn't think of it. 😅 You're right that a DFS would have been more straightforward than a union find, too. I'm trying to get a little more practice implementing the latter, so that's the main reason I had opted for it. 🙂
I am not able to see the intuition behind scaling every block to 3x3 matrix, I mean how do you think of it? Is this some important concept which I am missing out on?
@@AakashKumar-vf3dh Even i feel the same brother, if you have coded your DSU implementation, please share it, i am not able to think of how to implement it...
i did the 2*2 square for each 1*1 and quickly found out 😅. then thought of the diagonals and immediately realised that my 1s were blocking some diagonals but not others. that is when I thought I need to follow corner to corner paths with the slashes but then I couldn't come up with an idea to avoid double counting and I knew it was time for neetcode
I think the visited set is not needed as the newly constructed grid can be modified during each run of dfs such that all reachable 0 doing a run of dfs are marked as 1. eg. class Solution: def regionsBySlashes(self, grid: List[str]) -> int: m,n = len(grid),len(grid[0]) M,N = 3*m,3*n grid1 = [[0]*N for _ in range(M)] directions = [[-1,0],[1,0],[0,-1],[0,1]] res = 0 for i in range(m): for j in range(n): if grid[i][j] == '/': i1,j1 = 3*i,3*j grid1[i1][j1+2] = 1 grid1[i1+1][j1+1] = 1 grid1[i1+2][j1] = 1 elif grid[i][j] == '\\': i1,j1 = 3*i,3*j grid1[i1][j1] = 1 grid1[i1+1][j1+1] = 1 grid1[i1+2][j1+2] = 1 def dfs(r,c): if r in [-1,M] or c in [-1,N] or grid1[r][c] == 1: return grid1[r][c] = 1 for dx,dy in directions: dfs(r+dx,c+dy) for i in range(M): for j in range(N): if grid1[i][j] == 0: dfs(i,j) res+=1 return res
@@afsalts5872 Newly constructed grid takes O(rows*cols) space, therefore removing visited set will not affect space complexity. Even if you don't construct a new grid array (let's say in problems like number of islands) your space complexity is still O(rows*cols) because of the implicit recurisive stack of the dfs function.
Okay, I have solved few hard problems which are easier than this, I didn't had any idea what to do. I have Google Interview, if this would be asked I doomed(not now of course).
Did you come up to idea about scaling yourself ? or did you use any hint ? Actually even coming to idea about scaling for two, how one will get idea to go for three times ?
exist OUT of THE BOX solution: with standard flood fill build around input square square with doubled square and ROTATE it in 45gradus then standard floodfill for counting
Why mine is TLE ???😭😭😭 class Solution: def regionsBySlashes(self, grid: List[str]) -> int: # 1. transform grid into grid of 1 and 0 total = 0 n = len(grid) s = n * 3 square = [[0] * s for _ in range(s)] for i in range(n): for j in range(n): char = grid[i][j] if char == '/': ii, jj = i * 3, j * 3 + 2 square[ii][jj] = 1 square[ii + 1][jj - 1] = 1 square[ii + 2][jj - 2] = 1 elif char == '\\': ii, jj = i * 3, j * 3 square[ii][jj] = 1 square[ii + 1][jj + 1] = 1 square[ii + 2][jj + 2] = 1 # 2. 200. number of islands deq = collections.deque() visited = set() for i in range(s): for j in range(s): if square[i][j] == 0: total += 1 deq.append((i, j)) while deq: r, c = deq.popleft() if square[r][c] == 0: square[r][c] = 1 visited.add((r, c)) if 0
# Two reasons : 1) visited is redundant, can be removed. 2) mark a reachable cell as visited (square[*][*]=1) when append it to deq can speed up BFS. Here is my modified version: class Solution: def regionsBySlashes(self, grid: List[str]) -> int: # 1. transform grid into grid of 1 and 0 total = 0 n = len(grid) s = n * 3 square = [[0] * s for _ in range(s)] for i in range(n): for j in range(n): char = grid[i][j] if char == '/': ii, jj = i * 3, j * 3 + 2 square[ii][jj] = 1 square[ii + 1][jj - 1] = 1 square[ii + 2][jj - 2] = 1 elif char == '\\': ii, jj = i * 3, j * 3 square[ii][jj] = 1 square[ii + 1][jj + 1] = 1 square[ii + 2][jj + 2] = 1 def bfs(i,j): deq = collections.deque() deq.append((i, j)) square[i][j] = 1
while deq: r, c = deq.popleft() for nr,nc in [ [r-1, c], [r+1, c], [r, c-1], [r, c+1]]: if 0
@@lavanya_m01 I apologise for my long ass code lol ```python class Solution: def regionsBySlashes(self, grid: List[str]) -> int: #initalize parent & size array : 4*row*col, separating every small 1x1 square to TOP(1), LEFT(2), RIGHT(3), BOTTOM(4) row=len(grid) col=len(grid[0]) self.parent=[i for i in range(4*row*col)] self.size=[1 for i in range(4*row*col)] #Implement Union-Find def find(i): if i!=self.parent[i]: self.parent[i]=find(self.parent[i]) return self.parent[i]
def union(x, y): px, py= find(x),find(y) if px==py: return if self.size[px]
Is there any particular reason you avoided using union find and euler's formula as a solution? I tried to understand it by myself but the solutions are mostly unclean and I couldn't understand them since I am not familiar with the language
Personally I think the problem lends itself more to flood fill solutions. Disjointed sets and Euler's work but you have to perform a lot of setup in order to convert the initial problem into one that these two can solve.
It took me two hours to solve it. 30 mins for planning and writing code and 1.5 hours for debugging. 😂😂 Initially, I scaled it to 2 x 2 grid instead of 3 x 3.
@@NeetCodeIO bro i thought this was a very small change, but it just shot me from 5% best runtime to 84% best runtime XD c++, i guess the thing pulling me back was the dynamic memory allocation stuff that set in c++ does when u push a new element to it, they are indeed very costly XD
4:33 In 2x2 matrix, 4 directions gave wrong answers as we couldn't count the gaps correctly. But we couldn't use 8 directions (including diagonals) because it might cross the blocked path and reach the next region. To solve this issue, we use 3x3 matrix so that we could just use 4 directions and cover all the gaps correctly.
6:32 When you see in 2X2 matrix it has less squares around the current square so it cannot travel as diagonal traversal is not applicable in DFS but if we take 3X3 matrix then we get extra squares around so DFS is possible and it counts all the squares as 1 region and not separate regions.
6:32 When you see in 2X2 matrix it has less squares around the current square so it cannot travel as diagonal traversal is not applicable in DFS but if we take 3X3 matrix then we get extra squares around so DFS is possible and it counts all the squares as 1 region and not separate regions.
nope. The problem statement is the most confusing I've ever come across. I usually just ignore these kinds of problems since the chances of facing something like this in an interview are low.
@@rambabupatidar3092 Draw matrix how ? The problem says it's a nxn matrix, but we're instead given a single dimension array of strings. How does this [" /" , "/ "] translate to a matrix ?
Is there anything specific that was confusing? If you're not familiar with graph traversals, and havent solved a problem like Number of Islands, then I probably wouldn't attempt this problem yet. Otherwise, this one isnt too bad after the scaling part.
How can you even come up with that bruhhh ?? anyway java code : class Solution { public int regionsBySlashes(String[] grid) { //0 means free 1 means blocked int rows = grid.length; int cols = grid[0].length(); int largeRows = rows*3; int largeCols = cols*3; int lmx[][] = new int[largeRows][largeCols]; for(int i=0; i
This is crazy. This problem should be hard. Is it just me who solved island type problems 10+ times but could not associate this is similar to that? I was looking at if there are patterns to count regions row wise.
The fuck
Lmao
my honest reaction
my honest reaction fr
True
lmaoooooo
I wish I came up with this solution. I would have jumped out of my window because I could fly
take the grid and make it 3 times bigger, no way a normal person would think of exactly that in an interview.
Thanks for the run Neetcode! Btw no streams for a quite a while, hope to see them back soon
Future ain't waiting for normal people
@@krishnabisht-o4e it is just need to work hard though
5:32 At this point I even do not undertand the problem.
I don't even understand how we are supposed to parse the input
Learned a lot from the problem, but it's definitely not a medium :) Thanks for the explanation!
I managed to solve that question with 2n X 2n grid instead of 3x X 3x.
I replace / with 1 and \ with -1 and call dfs for all direction as well as for diagonal for specific condition and it works!
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
n = len(grid)
main_grid = [[0 for _ in range(n*2)] for _ in range(n*2)]
m = n*2
for i in range(n):
for j in range(n):
if grid[i][j] == '/':
main_grid[i*2 + 1][j*2] = 1
main_grid[i*2][j*2 + 1] = 1
elif grid[i][j] == '\\':
main_grid[i*2][j*2] = -1
main_grid[i*2 + 1][j*2 + 1] = -1
visited = set()
def dfs(i, j):
if i == -1 or j == -1 or i == m or j == m or main_grid[i][j] or (i, j) in visited:
return
visited.add((i, j))
dfs(i, j+1)
dfs(i+1, j)
dfs(i, j-1)
dfs(i-1, j)
if i != 0 and j != m-1 and main_grid[i-1][j] != -1 and main_grid[i][j+1] != -1:
dfs(i-1, j+1)
if i != m-1 and j != 0 and main_grid[i][j-1] != -1 and main_grid[i+1][j] != -1:
dfs(i+1, j-1)
if i != m-1 and j != m-1 and main_grid[i][j+1] != 1 and main_grid[i+1][j] != 1:
dfs(i+1, j+1)
if i != 0 and j != 0 and main_grid[i][j-1] != 1 and main_grid[i-1][j] != 1:
dfs(i-1, j-1)
ans = 0
for i in range(m):
for j in range(m):
if main_grid[i][j] == 0 and (i, j) not in visited:
dfs(i, j)
ans += 1
return ans
The space complexity will be 9*n^2 bcoz each cell needs 9 more cells for scaling .
You don't count constants when calculating space complexity so it will be n^2
You need to check to definition of big o notation. You don't add the constants to the notation as they are not defining factors on runtime complexity or space complexity as the input size reaches infinity.
can you use that same logic for the runtime complexity. 9*n^2 rather than 3*n^2
5:31 Jumpscare warning
Hey @neetcodeIO .You can use Ctrl+D to "select next occurrence". It will help you correct stuff faster/more easily. I've noticed you edit separately (like you did in 15:36 with the grid2) in several vids and just thought to point it out.
This is flood fill algorithm. I realized it the moment I read the problem statement. I watched this video, the moment i heard that i can divide the char into a grid of 3x3, I understood the problem, solved it myself.
Crazy and actually a great problem. thanks for video!!
I managed to solve this one by dividing each cell into 4 triangular quadrants along the diagonals - this way each cell has a top, left, right, and bottom. If a "/" is in the cell, the top and left of that cell are connected, and right and bottom are connected. If a "\" is found, the top and right are connected, and the left and bottom are connected. If " " is found, the top, left, bottom, and right are connected. Each cell's edge is also connected to its neighbouring cell's edge (eg. a cells top edge is connected to the above cell's bottom edge). I made an adjacency list of these connections, and then ran union find on them.
Similar to you, although my solution worked it didn't rank very high in either time or space metrics.
class Solution:
def regionsBySlashes(self, g: List[str]) -> int:
n,c,d=len(g),0,[[-1,0],[0,1],[1,0],[0,-1]]
a=[[[0]*4 for _ in range(n)]for _ in range(n)]
b={ '/':[[3],[2],[1],[0]],
'\\':[[1],[0],[3],[2]],
' ':[[1,3],[0,2],[1,3],[0,2]]}
def f(y,x,z):
if 0
Same way as I did it. But I did not create an extra adj list, coz u can find the indices of elements in the "parent" to join directly while iterating through the grid.
Great approach! But you don't have to separately create an adjacency list of these connections, just look for neighboring elements of the cell based on your diagram. Also, you can solve it using simple dfs as well (i.e. without union-find).
@@corrogist692 That's a very good point about the need to not have an adjacency list, and I'm a little embarrassed that I didn't think of that. Thank you for pointing that out to me!
@@33galactus That's a very good point about the adjacency list being unnecessary, I honestly can't believe I didn't think of it. 😅
You're right that a DFS would have been more straightforward than a union find, too. I'm trying to get a little more practice implementing the latter, so that's the main reason I had opted for it. 🙂
Has this channel covered the Grind 75 list ?
you're killing it Neet, thanks for the daily consistency you push us to be better daily as well
I am not able to see the intuition behind scaling every block to 3x3 matrix, I mean how do you think of it? Is this some important concept which I am missing out on?
It's pretty hard to come up with this unless u have seen this so don't be sad u r not alone
@@avneetsingh6194 ok, thanks bro
I feel it is more intuitive to come up with DSU than this approach.
@@AakashKumar-vf3dh Even i feel the same brother, if you have coded your DSU implementation, please share it, i am not able to think of how to implement it...
Using disjoint set is the most efficient way to this question, but DFS is more general.
That's why Neetcode is the goat!
Damn, this is a really good problem.
Thank you , another great explanation!
First comment. Remember to take breaks champ ❤ We all owe you our sanity
Hello Everyone,
Kindly share some similar practice list like this problem.
Kind of new type of upgrading the grid.
i did the 2*2 square for each 1*1 and quickly found out 😅. then thought of the diagonals and immediately realised that my 1s were blocking some diagonals but not others. that is when I thought I need to follow corner to corner paths with the slashes but then I couldn't come up with an idea to avoid double counting and I knew it was time for neetcode
PS : if you declare the matrix element as bool and declare empty as false and block as true, you won't need a separate visited matrix.
This solution is f'in genius! 🤯
Now we're getting in computer vision stuff!
UA-cam video inside a youtube video. Now that's recursion folks!
thanks neetcode! visited set is a bit redundant, we better just mark cell as 1
you made grid2 so you could just paint over it instead of allocating visit. it would more memory efficient
I think the visited set is not needed as the newly constructed grid can be modified during each run of dfs such that all reachable 0 doing a run of dfs are marked as 1. eg.
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
m,n = len(grid),len(grid[0])
M,N = 3*m,3*n
grid1 = [[0]*N for _ in range(M)]
directions = [[-1,0],[1,0],[0,-1],[0,1]]
res = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '/':
i1,j1 = 3*i,3*j
grid1[i1][j1+2] = 1
grid1[i1+1][j1+1] = 1
grid1[i1+2][j1] = 1
elif grid[i][j] == '\\':
i1,j1 = 3*i,3*j
grid1[i1][j1] = 1
grid1[i1+1][j1+1] = 1
grid1[i1+2][j1+2] = 1
def dfs(r,c):
if r in [-1,M] or c in [-1,N] or grid1[r][c] == 1: return
grid1[r][c] = 1
for dx,dy in directions: dfs(r+dx,c+dy)
for i in range(M):
for j in range(N):
if grid1[i][j] == 0:
dfs(i,j)
res+=1
return res
Agree. But it will not improve overall space complexity.
Y@@33galactus
@@afsalts5872 Newly constructed grid takes O(rows*cols) space, therefore removing visited set will not affect space complexity. Even if you don't construct a new grid array (let's say in problems like number of islands) your space complexity is still O(rows*cols) because of the implicit recurisive stack of the dfs function.
Why don't you store visited cells in scaled array? Mark 1 for visited, -1 - barrier, 0 - not visited. Like optimisation
you can even treat visited and barriers as the same thing, then it's just a boolean array
Is there any reason we pass in the visit set as a parameter to DFS as opposed to adding to a global visit set? Thank you!
I really like your videos , Full support from India
Can you please make a video on Maximum Value at a Given Index in a Bounded Array | Leetcode - 1802?
Amazing explanation...❤
great explanation as usual
This problem really made me want to learn DSA again. 💀
Okay, I have solved few hard problems which are easier than this, I didn't had any idea what to do. I have Google Interview, if this would be asked I doomed(not now of course).
Instead of using visit set, using the same enlarged grid and marking visited cells with 2 is better
Did you come up to idea about scaling yourself ? or did you use any hint ?
Actually even coming to idea about scaling for two, how one will get idea to go for three times ?
Shouldn't "grid2[r][c] != 0" in the dfs function create an index out of range error?
Can you please make a video on Leetcode 2145 Count the Hidden Sequences?
I am not able to understand how to tackle prefix sum questions.
exist OUT of THE BOX solution: with standard flood fill
build around input square square with doubled square and ROTATE it in 45gradus then standard floodfill for counting
Could you please also explain how Union Find works on this question? Thanks!
How do you think so, u r so good at what ur work, thats y , eyeglasses are thicker 😄
Can we implement the Union - Find algorithm here ?
Brilliant!!
Why mine is TLE ???😭😭😭
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
# 1. transform grid into grid of 1 and 0
total = 0
n = len(grid)
s = n * 3
square = [[0] * s for _ in range(s)]
for i in range(n):
for j in range(n):
char = grid[i][j]
if char == '/':
ii, jj = i * 3, j * 3 + 2
square[ii][jj] = 1
square[ii + 1][jj - 1] = 1
square[ii + 2][jj - 2] = 1
elif char == '\\':
ii, jj = i * 3, j * 3
square[ii][jj] = 1
square[ii + 1][jj + 1] = 1
square[ii + 2][jj + 2] = 1
# 2. 200. number of islands
deq = collections.deque()
visited = set()
for i in range(s):
for j in range(s):
if square[i][j] == 0:
total += 1
deq.append((i, j))
while deq:
r, c = deq.popleft()
if square[r][c] == 0:
square[r][c] = 1
visited.add((r, c))
if 0
I just did it with dfs and it works.. Are functions faster than iterative solutions!?
# Two reasons : 1) visited is redundant, can be removed. 2) mark a reachable cell as visited (square[*][*]=1) when append it to deq can speed up BFS. Here is my modified version:
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
# 1. transform grid into grid of 1 and 0
total = 0
n = len(grid)
s = n * 3
square = [[0] * s for _ in range(s)]
for i in range(n):
for j in range(n):
char = grid[i][j]
if char == '/':
ii, jj = i * 3, j * 3 + 2
square[ii][jj] = 1
square[ii + 1][jj - 1] = 1
square[ii + 2][jj - 2] = 1
elif char == '\\':
ii, jj = i * 3, j * 3
square[ii][jj] = 1
square[ii + 1][jj + 1] = 1
square[ii + 2][jj + 2] = 1
def bfs(i,j):
deq = collections.deque()
deq.append((i, j))
square[i][j] = 1
while deq:
r, c = deq.popleft()
for nr,nc in [ [r-1, c], [r+1, c], [r, c-1], [r, c+1]]:
if 0
I chopped every 1x1 to four parts then implemented union-find to join them...lol
Can u pls show the code
@@lavanya_m01 I apologise for my long ass code lol
```python
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
#initalize parent & size array : 4*row*col, separating every small 1x1 square to TOP(1), LEFT(2), RIGHT(3), BOTTOM(4)
row=len(grid)
col=len(grid[0])
self.parent=[i for i in range(4*row*col)]
self.size=[1 for i in range(4*row*col)]
#Implement Union-Find
def find(i):
if i!=self.parent[i]:
self.parent[i]=find(self.parent[i])
return self.parent[i]
def union(x, y):
px, py= find(x),find(y)
if px==py:
return
if self.size[px]
@@lavanya_m01 but it is quite a standard implementation, many lines but the only tricky part is to sort out the indices
Is there any particular reason you avoided using union find and euler's formula as a solution? I tried to understand it by myself but the solutions are mostly unclean and I couldn't understand them since I am not familiar with the language
Personally I think the problem lends itself more to flood fill solutions. Disjointed sets and Euler's work but you have to perform a lot of setup in order to convert the initial problem into one that these two can solve.
It took me two hours to solve it. 30 mins for planning and writing code and 1.5 hours for debugging. 😂😂
Initially, I scaled it to 2 x 2 grid instead of 3 x 3.
Would anyone mind explaining where did the ROWS and COLS defined which are used in dfs function
great
Are these live streams or why doesn't he look up the difference between slashes and backslashes?
can't we make grid2[r][c] = 1 instead of adding them to the set?
Yeah that's right, I'm just used to not modifying the input but in this case it doesn't matter
@@NeetCodeIO bro i thought this was a very small change, but it just shot me from 5% best runtime to 84% best runtime XD c++, i guess the thing pulling me back was the dynamic memory allocation stuff that set in c++ does when u push a new element to it, they are indeed very costly XD
ROWS1 and COLS1 would be same and equal to n, so no need for 2 declarations right?
Yeah good point
union find is weakness 😭
How i am supposed to came up with this kind of solutions?
This has to be the worst problem on leetcode
Why only 3X3 ? Please help
Coz it just works ;-;
4:33 In 2x2 matrix, 4 directions gave wrong answers as we couldn't count the gaps correctly. But we couldn't use 8 directions (including diagonals) because it might cross the blocked path and reach the next region. To solve this issue, we use 3x3 matrix so that we could just use 4 directions and cover all the gaps correctly.
6:32 When you see in 2X2 matrix it has less squares around the current square so it cannot travel as diagonal traversal is not applicable in DFS but if we take 3X3 matrix then we get extra squares around so DFS is possible and it counts all the squares as 1 region and not separate regions.
First!
was this the first face reveal video
i should have iq of einstein to solve this problem i would've never thought to
connect this to the no of islands problem
I don't get it why we should use 3*3
6:32 When you see in 2X2 matrix it has less squares around the current square so it cannot travel as diagonal traversal is not applicable in DFS but if we take 3X3 matrix then we get extra squares around so DFS is possible and it counts all the squares as 1 region and not separate regions.
Why !!!
Are they needed
I did come up with this solution but I thought it would TLE so gave up
🤯
do you guys really understand the explanation?
nope. The problem statement is the most confusing I've ever come across. I usually just ignore these kinds of problems since the chances of facing something like this in an interview are low.
Use pen papers to draw out some matrix you will get it, initially it seems overwhelming
@@rambabupatidar3092 Draw matrix how ?
The problem says it's a nxn matrix, but we're instead given a single dimension array of strings.
How does this [" /" , "/ "] translate to a matrix ?
I didn't get it at all , i am here just to know what the crap it wants
Is there anything specific that was confusing?
If you're not familiar with graph traversals, and havent solved a problem like Number of Islands, then I probably wouldn't attempt this problem yet.
Otherwise, this one isnt too bad after the scaling part.
how tf
How can you even come up with that bruhhh ?? anyway java code : class Solution {
public int regionsBySlashes(String[] grid) {
//0 means free 1 means blocked
int rows = grid.length;
int cols = grid[0].length();
int largeRows = rows*3;
int largeCols = cols*3;
int lmx[][] = new int[largeRows][largeCols];
for(int i=0; i
Wtf
Your intro gives me motion sickness
Yes lmao.