Regions Cut By Slashes - Leetcode 959 - Python

0:00 - Read the problem
0:30 - Drawing Explanation
10:18 - Coding Explanation

leetcode 959

#neetcode #leetcode #python

[StellasAdi]

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.

[BrandonGarciaCode]

5:32 At this point I even do not undertand the problem.

[gmh]

I wish I came up with this solution. I would have jumped out of my window because I could fly

[business_central]

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

[АнасБенМустафа]

Learned a lot from the problem, but it's definitely not a medium :) Thanks for the explanation!

[ashishbhambure]

The space complexity will be 9*n^2 bcoz each cell needs 9 more cells for scaling .

[neelpatel]

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

[fieworjohn]

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.

[anandsrikumar]

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.

[確實-rx]

Crazy and actually a great problem. thanks for video!!

[jamestwosheep]

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.

[anthonya]

Has this channel covered the Grind 75 list ?

[akinhwan]

you're killing it Neet, thanks for the daily consistency you push us to be better daily as well

[samuelrobert]

The visit set is not required as you could set the visited cell to 1 in the dfs function and do dfs for 0s in the loop.

[VipulMadan]

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?

[MadpolygonDEV]

First comment. Remember to take breaks champ ❤ We all owe you our sanity

[ec]

Using disjoint set is the most efficient way to this question, but DFS is more general.

[rajveersingh]

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

[Techky-yf]

I really like your videos, Full support from India

[IK-xkex]

Why don't you store visited cells in scaled array? Mark 1 for visited, -1 - barrier, 0 - not visited. Like optimisation