959. Regions Cut By Slashes - Leetcode Solution

Problem Description

The Regions Cut By Slashes problem asks you to determine how many distinct regions are formed in an n x n grid when each cell may contain a forward slash '/', a backslash '\', or a blank space ' '.
Each slash divides the square cell into two triangles, and regions are defined as groups of connected spaces (sharing an edge, not just a point).
Key constraints:

Input is a list of strings grid, each string representing a row of the grid.
Each cell contains exactly one character: '/', '\', or ' '.
Regions are contiguous areas separated by slashes.
Cells are not reused between regions.

Goal: Return the number of distinct regions formed by the slashes in the grid.

Thought Process

At first glance, it seems like we just need to count how slashes cut the grid. But because slashes can create small triangles within a cell, and regions can snake through the grid, a simple scan won’t work.

The brute-force idea is to try to trace each region by exploring the grid as a whole. But handling the diagonal cuts is tricky: a slash in one cell can block or connect regions in neighboring cells.

To simplify, we can subdivide each cell into smaller parts (e.g., triangles or quadrants) and treat each as a node in a graph. Then, we can use classic graph traversal (like DFS or Union-Find) to count the number of connected components, which correspond to regions.

The challenge is in mapping the slashes to these subdivisions and connecting them correctly.

Solution Approach

The standard, efficient approach is to divide each cell into 4 triangles (top, right, bottom, left) and model their connectivity:

Subdivide the grid:
- Each 1x1 cell is split into 4 triangles, which we label as 0 (top), 1 (right), 2 (bottom), 3 (left).
Map slashes to connections:
- If the cell is '/': connect triangles 0-3 and 1-2 (slash divides from top-right to bottom-left).
- If the cell is '\': connect triangles 0-1 and 2-3 (slash divides from top-left to bottom-right).
- If the cell is ' ': connect all four triangles (no division).
Connect adjacent cells:
- For each cell, connect its triangles to the appropriate triangles of neighboring cells (e.g., top triangle to the bottom triangle of the cell above).
Count regions:
- Use Union-Find (Disjoint Set Union) to merge connected triangles.
- The number of unique parents in the Union-Find structure gives the number of regions.

This approach is efficient, systematic, and handles all edge cases.

Example Walkthrough

Sample Input:

    grid = [
      " /",
      "/ "
    ]

Step-by-step:

Expand each cell:
- Cell (0,0): contains ' ' → all four triangles connected.
- Cell (0,1): contains '/' → connect 0-3, 1-2.
- Cell (1,0): contains '/' → connect 0-3, 1-2.
- Cell (1,1): contains ' ' → all four triangles connected.
Connect triangles across cells:
- For example, right triangle of (0,0) connects to left triangle of (0,1).
- Bottom triangle of (0,0) connects to top triangle of (1,0).
Union-Find:
- After all unions, count the number of unique connected components.
Result:
- There are 2 regions in this example.

Code Implementation

class Solution:
    def regionsBySlashes(self, grid):
        n = len(grid)
        size = n * n * 4
        parent = [i for i in range(size)]

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def union(x, y):
            parent[find(x)] = find(y)

        for i in range(n):
            for j in range(n):
                idx = (i * n + j) * 4
                c = grid[i][j]
                # Internal unions
                if c == ' ':
                    union(idx + 0, idx + 1)
                    union(idx + 1, idx + 2)
                    union(idx + 2, idx + 3)
                elif c == '/':
                    union(idx + 0, idx + 3)
                    union(idx + 1, idx + 2)
                elif c == '\\':
                    union(idx + 0, idx + 1)
                    union(idx + 2, idx + 3)
                # Connect with neighbors
                # Down
                if i + 1 < n:
                    union(idx + 2, ((i + 1) * n + j) * 4 + 0)
                # Right
                if j + 1 < n:
                    union(idx + 1, (i * n + (j + 1)) * 4 + 3)

        regions = sum(find(x) == x for x in range(size))
        return regions

class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        int n = grid.size();
        int size = n * n * 4;
        vector<int> parent(size);
        for (int i = 0; i < size; ++i) parent[i] = i;

        function<int(int)> find = [&](int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        };
        auto unite = [&](int x, int y) {
            parent[find(x)] = find(y);
        };

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int idx = (i * n + j) * 4;
                char c = grid[i][j];
                if (c == ' ') {
                    unite(idx + 0, idx + 1);
                    unite(idx + 1, idx + 2);
                    unite(idx + 2, idx + 3);
                } else if (c == '/') {
                    unite(idx + 0, idx + 3);
                    unite(idx + 1, idx + 2);
                } else if (c == '\\') {
                    unite(idx + 0, idx + 1);
                    unite(idx + 2, idx + 3);
                }
                // Down
                if (i + 1 < n) {
                    unite(idx + 2, ((i + 1) * n + j) * 4 + 0);
                }
                // Right
                if (j + 1 < n) {
                    unite(idx + 1, (i * n + (j + 1)) * 4 + 3);
                }
            }
        }
        int regions = 0;
        for (int i = 0; i < size; ++i)
            if (find(i) == i) ++regions;
        return regions;
    }
};

class Solution {
    public int regionsBySlashes(String[] grid) {
        int n = grid.length;
        int size = n * n * 4;
        int[] parent = new int[size];
        for (int i = 0; i < size; ++i) parent[i] = i;

        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        void union(int x, int y) {
            parent[find(x)] = find(y);
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                int idx = (i * n + j) * 4;
                char c = grid[i].charAt(j);
                if (c == ' ') {
                    union(idx + 0, idx + 1);
                    union(idx + 1, idx + 2);
                    union(idx + 2, idx + 3);
                } else if (c == '/') {
                    union(idx + 0, idx + 3);
                    union(idx + 1, idx + 2);
                } else if (c == '\\') {
                    union(idx + 0, idx + 1);
                    union(idx + 2, idx + 3);
                }
                // Down
                if (i + 1 < n) {
                    union(idx + 2, ((i + 1) * n + j) * 4 + 0);
                }
                // Right
                if (j + 1 < n) {
                    union(idx + 1, (i * n + (j + 1)) * 4 + 3);
                }
            }
        }
        int regions = 0;
        for (int i = 0; i < size; ++i)
            if (find(i) == i) ++regions;
        return regions;
    }
}

var regionsBySlashes = function(grid) {
    const n = grid.length;
    const size = n * n * 4;
    const parent = Array(size).fill(0).map((_, i) => i);

    function find(x) {
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    function union(x, y) {
        parent[find(x)] = find(y);
    }

    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n; ++j) {
            const idx = (i * n + j) * 4;
            const c = grid[i][j];
            if (c === ' ') {
                union(idx + 0, idx + 1);
                union(idx + 1, idx + 2);
                union(idx + 2, idx + 3);
            } else if (c === '/') {
                union(idx + 0, idx + 3);
                union(idx + 1, idx + 2);
            } else if (c === '\\') {
                union(idx + 0, idx + 1);
                union(idx + 2, idx + 3);
            }
            // Down
            if (i + 1 < n) {
                union(idx + 2, ((i + 1) * n + j) * 4 + 0);
            }
            // Right
            if (j + 1 < n) {
                union(idx + 1, (i * n + (j + 1)) * 4 + 3);
            }
        }
    }
    let regions = 0;
    for (let i = 0; i < size; ++i)
        if (find(i) === i) regions++;
    return regions;
};

Time and Space Complexity

Brute-force approach:
- Would require O((n^2)^2) time to trace all possible regions, as we might revisit cells multiple times.
- Space complexity would be O(n^2) for visited markers.
Optimized Union-Find approach:
- Each of the n² cells is split into 4 triangles, so total nodes = 4n².
- Each union/find operation is nearly O(1) (amortized with path compression), so total time is O(n²).
- Space complexity is O(n²), for the parent array.

The Union-Find approach is both time and space efficient for this problem.

Summary

By cleverly subdividing each cell and using Union-Find to track connections, we can efficiently count the number of regions formed by slashes in a grid. This approach transforms a tricky geometric problem into a classic graph connectivity problem, making the solution both elegant and efficient.

AlgoMap.io

Want Help Cracking FAANG?