Regions Cut By Slashes: Grid Upscaling with Connected Components
You are given an n x n grid where each cell contains one of three characters: ' ' (space), '/', or '\\'. These characters divide the grid into regions. Return the total number of regions.
This is LeetCode 959: Regions Cut By Slashes, and it is one of the most creative grid problems on LeetCode. The trick is not about graph traversal itself, but about transforming the input into a form where standard graph traversal works.
Why this problem is tricky
At first glance, this looks like a standard connected components problem. But slashes create diagonal boundaries, and diagonal lines do not align with the rows and columns of a grid. You cannot represent a / or \\ as a simple wall between two adjacent cells. The boundary cuts through the middle of a cell, splitting it into two triangles.
If you try to run DFS directly on the original grid, you have no clean way to encode "this cell is split in half diagonally." The cells are not neatly divided into blocked and unblocked. You need a different representation.
The key insight: upscale to 3x3
The core idea is to expand each cell into a 3x3 block of smaller cells. In this larger grid, a diagonal slash becomes a line of three wall cells, and the regions on either side of the slash become separate groups of empty cells. Now you have a standard boolean grid (wall vs. empty), and you can count connected components with DFS or BFS, the same technique from Number of Islands.
Here is how each character maps to its 3x3 block:
Space ' ': all 9 cells are empty (0).
Forward slash '/': wall cells at positions (0,2), (1,1), (2,0), going from top-right to bottom-left.
Backslash '\\': wall cells at positions (0,0), (1,1), (2,2), going from top-left to bottom-right.
After upscaling, the n x n character grid becomes a 3n x 3n boolean grid. Every slash is now a wall, and every region is a connected group of empty cells. Count the connected components and you have your answer.
Why 3x3 and not 2x2? A 2x2 block is too coarse to represent a diagonal cleanly. Two wall cells in a 2x2 block would block too many paths and merge regions that should be separate. The 3x3 expansion gives the diagonal enough resolution to separate regions without over-blocking.
The solution
def regionsBySlashes(grid):
n = len(grid)
expanded = [[0] * (n * 3) for _ in range(n * 3)]
for i in range(n):
for j in range(n):
if grid[i][j] == '/':
expanded[i*3][j*3+2] = 1
expanded[i*3+1][j*3+1] = 1
expanded[i*3+2][j*3] = 1
elif grid[i][j] == '\\':
expanded[i*3][j*3] = 1
expanded[i*3+1][j*3+1] = 1
expanded[i*3+2][j*3+2] = 1
def dfs(r, c):
if r < 0 or r >= n*3 or c < 0 or c >= n*3:
return
if expanded[r][c] != 0:
return
expanded[r][c] = 2
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
regions = 0
for i in range(n * 3):
for j in range(n * 3):
if expanded[i][j] == 0:
dfs(i, j)
regions += 1
return regions
Let's break this down.
The expansion loop iterates over every cell in the original grid. For each /, it marks three cells in the expanded grid along the anti-diagonal of the 3x3 block. For each \\, it marks three cells along the main diagonal. Spaces leave all nine cells as 0.
The DFS function is identical to the flood fill from Number of Islands. It checks bounds, checks if the cell is empty (0), marks it as visited (2), and recurses into all four neighbors. Once marked, the cell will not be revisited.
The counting loop scans every cell in the expanded grid. Each time it finds an unvisited empty cell (0), it has found a new region. It calls DFS to mark the entire region, then increments the counter.
We mark visited cells as 2 instead of using a separate visited set. This works because we only care about three states: wall (1), unvisited empty (0), and visited empty (2). The in-place approach saves memory and keeps the code simple.
Step-by-step walkthrough
Let's trace through the grid [" /", "/ "] to see the upscaling and DFS in action.
Step 1: The original 2x2 grid with slash characters.
Grid = [" /", "/ "]. Each cell is a single character: space, /, or \.
Step 2: Upscale each cell to a 3x3 block. Mark slash positions as walls.
Forward slash (/) marks cells at positions (0,2), (1,1), (2,0) within the 3x3 block. Dark cells are walls.
Step 3: Run DFS from the first unvisited empty cell (0,0). This floods the largest region.
DFS spreads through all connected empty cells, wrapping around both sides of the slash diagonal. Region A (blue) found.
Step 4: Continue scanning. Next unvisited empty cell is (1,5). DFS fills region B.
Region B (green) is the small triangle in the top-right, isolated by the slash wall in cell (0,1). regions = 2.
Step 5: Last unvisited cell is (4,2). DFS fills region C. Scan completes. Total: 3 regions.
Region C (yellow) is the bottom-left triangle. All cells visited. Answer = 3.
The two / characters become diagonal walls in the 6x6 expanded grid. DFS finds three connected components: the large region wrapping around both sides, the isolated top-right triangle, and the isolated bottom-left triangle. The answer is 3.
Complexity analysis
| Metric | Value |
|---|---|
| Time | O(n^2) |
| Space | O(n^2) |
Time is O(n^2). The expansion loop processes n^2 cells. The DFS visits each cell in the 3n x 3n grid at most once, which is 9n^2 cells total. Both are O(n^2).
Space is O(n^2) for the expanded grid (3n x 3n = 9n^2 cells) and O(n^2) for the DFS call stack in the worst case (if all cells are empty and connected).
For large grids, the recursive DFS can hit Python's recursion limit. A 30x30 input grid becomes 90x90 expanded, which is 8100 cells. If the grid is entirely spaces, the DFS goes 8100 frames deep. You can increase the recursion limit with sys.setrecursionlimit() or switch to iterative DFS with an explicit stack.
The building blocks
This problem is built on two reusable pieces that CodeBricks drills independently:
1. Grid upscaling (coordinate transformation)
The pattern of expanding a compact representation into a larger boolean grid so that diagonal or complex boundaries become axis-aligned walls:
for i in range(n):
for j in range(n):
if grid[i][j] == '/':
expanded[i*3][j*3+2] = 1
expanded[i*3+1][j*3+1] = 1
expanded[i*3+2][j*3] = 1
The mapping (i, j) to (i*3 + offset, j*3 + offset) is a coordinate transformation. Each original cell occupies a 3x3 region in the expanded grid. This technique appears whenever a problem encodes information in a way that does not map directly to grid cells.
2. Connected component counting (flood fill)
The standard "scan and DFS" pattern from Number of Islands:
regions = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == 0:
dfs(i, j)
regions += 1
Scan every cell. When you find an unvisited empty cell, you have a new component. Flood fill to mark the entire component. Increment the count. This pattern works identically on any boolean grid, regardless of how that grid was constructed.
The magic of this problem is that once you apply building block 1 (upscaling), building block 2 (flood fill) solves it immediately. The hard part is seeing that the upscaling transformation is needed.
The union-find alternative
You can also solve this problem with union-find by dividing each cell into four triangles (top, right, bottom, left) and merging them based on the slash character and adjacency between cells. The union-find approach avoids building the expanded grid and runs in near-linear time with path compression and union by rank.
The upscaling approach is simpler to implement and reason about, but the union-find approach uses less memory for large grids. Both pass on LeetCode.
Edge cases
Before submitting, check these:
- All spaces: no slashes at all. The entire grid is one region. Return 1.
- Single cell with space:
[" "]returns 1. - Single cell with slash:
["/"]returns 2. The slash splits the cell into two triangles. - All forward slashes: each slash splits its cell, creating a checkerboard-like pattern of regions.
- Mixed slashes forming an X:
["\\/", "/\\"]creates four regions (an X in the center separates all four corners). - Large grids: make sure the DFS does not exceed the recursion limit. Use iterative DFS or increase
sys.setrecursionlimit().
From understanding to recall
You now see how upscaling a character grid to a boolean grid turns a tricky geometry problem into a standard connected components problem. The insight, expanding each cell to 3x3 so slashes become walls, is the hard part. The DFS flood fill after that is code you have written before.
But can you reproduce the expansion mapping from scratch under pressure? The positions for / versus \\ in the 3x3 block, the coordinate formula i*3 + offset, and the DFS on the expanded grid are all details that slip away without practice. They are not conceptually difficult. They are recall challenges.
Spaced repetition closes that gap. You practice writing the 3x3 expansion and the flood fill loop from memory at increasing intervals. After a few rounds, the pattern is automatic. You see a "grid with diagonal boundaries" problem, and the upscaling trick flows out without hesitation.
Related posts
- Number of Islands - The foundational connected components pattern that this problem's DFS is built on
- Surrounded Regions - Another grid DFS problem that teaches flood fill and region marking
- Shortest Bridge - Grid traversal with DFS and BFS combined, a good next step after mastering flood fill
CodeBricks breaks Regions Cut By Slashes into its grid-upscaling and connected-component-counting building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid transformation problem shows up in your interview, you do not think about it. You just write it.