LeetCode 959: Regions Cut By Slashes

Problem Restatement

We are given an n x n grid.

Each cell contains one of three characters:

"/"
"\\"
" "

A slash divides a square cell into smaller regions. A blank cell has no internal wall.

We need to return how many connected regions exist in the whole grid.

The official constraints are:

Source: LeetCode problem statement.

Input and Output

Example function shape:

def regionsBySlashes(grid: list[str]) -> int:
    ...

Examples

Example 1:

grid = [" /", "/ "]

Output:

2

The two slashes divide the square into two regions.

Example 2:

grid = [" /", "  "]

Output:

1

The slash does not fully separate the grid into multiple enclosed regions.

Example 3:

grid = ["/\\", "\\/"]

Output:

5

In Python strings, a backslash must be escaped. So "\\/" means the visible row \/, and "/\\" means the visible row /\.

First Thought: Draw the Regions Directly

One possible approach is to expand each cell into a 3 x 3 mini-grid.

A slash marks blocked mini-cells. Then we count connected empty areas with DFS or BFS.

That works, but it creates a larger grid and treats the problem as flood fill.

There is a more direct way: represent each square as smaller pieces and merge pieces that are connected.

Key Insight

Split every 1 x 1 cell into four triangles:

    0
  -----
  \   /
3  \ /  1
    X
2  / \ 
  -----

We can name them:

Each triangle is a small region candidate.

Then we use union find to merge triangles that are connected.

At the end, the number of connected components is the number of regions.

Internal Cell Merging

Each cell has four triangles.

If the cell is blank:

" "

then all four triangles are connected.

So we merge:

0 with 1
1 with 2
2 with 3

If the cell contains a forward slash:

"/"

then the slash separates:

top-left side from bottom-right side

So we merge:

top with left
right with bottom

Using indices:

0 with 3
1 with 2

If the cell contains a backslash:

"\\"

then it separates:

top-right side from bottom-left side

So we merge:

top with right
bottom with left

Using indices:

0 with 1
2 with 3

Neighbor Cell Merging

Triangles also connect across cell borders.

For a cell (r, c):

Its bottom triangle connects to the top triangle of the cell below:

(r, c, bottom) connects to (r + 1, c, top)

Its right triangle connects to the left triangle of the cell to the right:

(r, c, right) connects to (r, c + 1, left)

We only need to merge down and right neighbors to avoid duplicate work.

Algorithm

Let n = len(grid).

Each cell has 4 triangle nodes, so the union find has:

4 * n * n

nodes.

For each cell (r, c):

1. Compute the base id for its four triangles.
2. Merge triangles inside the cell based on its character.
3. Merge its bottom triangle with the top triangle of the cell below, if it exists.
4. Merge its right triangle with the left triangle of the cell to the right, if it exists.

Start with the component count equal to:

4 * n * n

Every successful union reduces the count by 1.

After all merges, return the component count.

Correctness

Each triangle represents one atomic open area inside a cell. Any final region in the grid is made by connecting these atomic areas across cell interiors and cell borders.

Inside a blank cell, no slash blocks movement, so all four triangles belong to the same region. The algorithm merges them.

Inside a / cell, the slash blocks movement between the top-right side and bottom-left side. The only internal connections are top with left, and right with bottom. The algorithm merges exactly those pairs.

Inside a \ cell, the only internal connections are top with right, and bottom with left. The algorithm merges exactly those pairs.

Across neighboring cells, two triangles are connected exactly when they share a cell border: bottom with top below, and right with left beside it. The algorithm merges exactly these border connections.

Therefore, two triangle pieces are in the same union find component exactly when they belong to the same contiguous region. The final number of union find components is exactly the number of regions cut by the slashes.

Complexity

Let n be the grid size.

Here, alpha is the inverse Ackermann function, which is effectively constant for these constraints.

Implementation

class DSU:
    def __init__(self, size: int):
        self.parent = list(range(size))
        self.rank = [0] * size
        self.components = size

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> None:
        root_a = self.find(a)
        root_b = self.find(b)

        if root_a == root_b:
            return

        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a

        self.parent[root_b] = root_a

        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1

        self.components -= 1

class Solution:
    def regionsBySlashes(self, grid: list[str]) -> int:
        n = len(grid)
        dsu = DSU(4 * n * n)

        def tri(row: int, col: int, part: int) -> int:
            return 4 * (row * n + col) + part

        for row in range(n):
            for col in range(n):
                ch = grid[row][col]

                top = tri(row, col, 0)
                right = tri(row, col, 1)
                bottom = tri(row, col, 2)
                left = tri(row, col, 3)

                if ch == " ":
                    dsu.union(top, right)
                    dsu.union(right, bottom)
                    dsu.union(bottom, left)
                elif ch == "/":
                    dsu.union(top, left)
                    dsu.union(right, bottom)
                else:
                    dsu.union(top, right)
                    dsu.union(bottom, left)

                if row + 1 < n:
                    dsu.union(bottom, tri(row + 1, col, 0))

                if col + 1 < n:
                    dsu.union(right, tri(row, col + 1, 3))

        return dsu.components

Code Explanation

We create one union find node for each triangle:

dsu = DSU(4 * n * n)

The helper converts a cell and triangle part into a unique id:

def tri(row: int, col: int, part: int) -> int:
    return 4 * (row * n + col) + part

For a cell, we name its four parts:

top = tri(row, col, 0)
right = tri(row, col, 1)
bottom = tri(row, col, 2)
left = tri(row, col, 3)

For a blank cell, all parts are connected:

dsu.union(top, right)
dsu.union(right, bottom)
dsu.union(bottom, left)

For a forward slash:

dsu.union(top, left)
dsu.union(right, bottom)

For a backslash:

dsu.union(top, right)
dsu.union(bottom, left)

Then we connect neighboring cells.

The bottom of the current cell touches the top of the cell below:

dsu.union(bottom, tri(row + 1, col, 0))

The right side of the current cell touches the left side of the cell to the right:

dsu.union(right, tri(row, col + 1, 3))

The DSU keeps a running component count. Each successful merge reduces it by one.

So the final answer is:

return dsu.components

Testing

def run_tests():
    s = Solution()

    assert s.regionsBySlashes([" /", "/ "]) == 2
    assert s.regionsBySlashes([" /", "  "]) == 1
    assert s.regionsBySlashes(["/\\", "\\/"]) == 5

    assert s.regionsBySlashes([" "]) == 1
    assert s.regionsBySlashes(["/"]) == 2
    assert s.regionsBySlashes(["\\"]) == 2
    assert s.regionsBySlashes(["//", "/ "]) == 3

    print("all tests passed")

run_tests()

Test meaning: