Solution: Regions Cut by Slashes

Let's solve the Regions Cut By Slashes problem using the Union Find pattern.

We'll cover the following

Statement
Solution
- Time complexity
- Space Complexity

Statement

An $n \times n$ grid is composed of $n$ , $1 \times 1$ squares, where each $1 \times 1$ square consists of a “/”, “\”, or a blank space. These characters divide the square into adjacent regions.

Given the grid represented as a string array, return the number of regions.

Note:

Backslash characters are escaped, so “\” is represented as “\\”.

A $1 \times 1$ square in the grid will be referred to as a box.

Constraints:

The grid consists of only “/”, “\”, or " " characters.
1 $\leq$ grid.length $\leq$ 30

The following demonstration shows how the grid can be visualized:

Press + to interact

Solution

We can combine the smaller regions (represented by 1x1 boxes) into bigger ones to make it easier to determine the count of distinct regions overall. For this, we first divide each 1x1 box into four parts. Then, we start traversing the grid, visiting each box, and see what parts of each box can be merged. This is decided by the character which corresponds to a particular box. If it’s a "/" or a "\", out of the four parts, we merge the two parts above the slash into the same for the two parts below the slash. This results in a box now having only two regions overall (one above the slash and the other below the slash). However, if the character corresponding to the box is " ", we merge all four parts. To achieve this, we use the union find pattern. Merging is done using the union method. It keeps on merging the regions into connected components. Once all the boxes are processed, we return the number of distinct connected components representing the number of regions cut by slashes.

Here’s how the algorithm works:

We create a parent array containing $4×n \times n$ elements where each element equals its corresponding index.
- Every four consecutive elements in this array represent a $1×1$ box in the grid.
- We associate each $1×1$ grid square with four nodes—north, west, east, and south—representing four triangles inside the square. That’s how every one of these four elements inside the parent list represents the north, west, east, and south components of the box, respectively.
- Each element in the array is initially equal to its respective index. For example:
  - The grid[0][0] box will comprise of the elements: 0, 1, 2, and 3.
  - The grid[0][1] box will comprise of the elements: 4, 5, 6, and 7, and so on.
Next, we traverse each character of the grid array:
We use the union method to merge the regions within each box depending on the character it contains:
- If the box contains a "/" character, it will be partitioned into two regions. Therefore, we will merge the north-west and east-south regions to convert the box into two connected components.
- If the box contains a "\" character, it will be partitioned into two regions. Therefore, we will merge the north-east and west-south regions to convert the box into two connected components.
- If the box contains a " " character, it will be converted to a single region. Therefore, we combine all four regions of the box to convert the box into a single connected component.

The illustration below shows how the regions within a box are merged:

Press + to interact

Next, we connect the current box with the neighboring boxes on it’s top, bottom, left, and right:
- The north region of the current box connects with the south region of the box above it.
- The south region of the current box connects with the north region of the box below it.
- The west region of the current box connects with the east region of the box to its left.
- The east region of the current box connects with the west region of the box to its right.
After the grid array has been traversed completely, the number of connected components in parent array are equal to the correct number of regions in the grid. So, we will traverse the parent array to find the number of connected components:
- We maintain a variable, count, initialized to $0$ to count the number of connected components.
- For each element, parents[i], we will use the find(parents[i]) method to check if the current node is a parent of itself, i.e. the current element parents[i] is equal to its respective index, i:
  - If it is, we have found a connected component and increment the count variable.
  - Otherwise, we move forward.
After the parent array has been traversed completely, we return count as it contains the number of regions in the grid.

The slides below illustrate how the algorithm runs:

Press + to interact

main.java

UnionFind.java

class RegionCut {
    public static int regionsBySlashes(String[] grid) {
        
        int N = grid.length;
        UnionFind findUnion = new UnionFind(4 * N * N);
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                int root = 4 * (r * N + c);
                char val = grid[r].charAt(c);
                if ((val == '/') || (val == ' ')) {
                    findUnion.union(root + 0, root + 1);
                    findUnion.union(root + 2, root + 3);
                }
                if ((val == '\\') || (val == ' ')) {
                    findUnion.union(root + 0, root + 2);
                    findUnion.union(root + 1, root + 3);
                }
                if (r + 1 < N)
                    findUnion.union(root + 3, (root + 4 * N) + 0);
                if (r - 1 >= 0)
                    findUnion.union(root + 0, (root - 4 * N) + 3);
                
                if (c + 1 < N)
                    findUnion.union(root + 2, (root + 4) + 1);
                
                if (c - 1 >= 0)
                    findUnion.union(root + 1, (root - 4) + 2);
            }
        }
 
        int count = 0;
        for (int x = 0; x < 4 * N * N; ++x) {
            if (findUnion.find(x) == x)
                count++;
        }
        return count;
    }
    // driver code
    public static void main(String[] args) {
        String[][] inputs = {
            {
                "/\\",
                "\\/"
            },
            {
                " /",
                "  "
            },
            {
                " /",
                "/ "
            },
            {
                " /\\",
                "\\/ ",
                " \\ "
            },
            {
                 " \\/",
                 " /\\",
                  "\\/ "
            }
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.print(i + 1);
            System.out.println(".\tInput list of strings: " + Print.printGrid(inputs[i]));
            System.out.println("\tOutput: " + regionsBySlashes(inputs[i]));
            System.out.println(Print.repeat("-", 100));
        }
    }
}

Regions Cut by Slashes

Time complexity

The time complexity of this solution is $O(n^2)$ , (where $n$ is the length of the grid) and can be calculated as:

The nested loops iterate over each character in the grid, resulting in $O(n^2)$ iterations.
The time complexity of the the union and find functions is $O( \alpha n)$ as both path compression and union find by rank are being used. $\alpha n$ is almost constant time and grows very slowly with the input size, so the time complexity of both these functions can be considered as constant time for practical purposes.
The loop to find the number of connected components traverses the parent array once, resulting in $O(4 \times n \times n)$ iterations.

Therefore, the overall time complexity becomes $O(n^2 \times \alpha n + (4\times n \times n))$ , which simplifies to $O(n^2)$ .

Space Complexity

The space complexity of this solution is $O(n^2)$ and can be calculated as:

Space occupied by the parent array: $O(4 \times n \times n)$ .
Space occupied by the rank array: $O(4 \times n \times n)$ .

Therefore, the overall time complexity is $O(2(4\times n \times n))$ , which simplifies to $O(n^2)$ .

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.

Getting Started

Two Pointers

Fast and Slow Pointers

Sliding Window

Merge Intervals

In-Place Manipulation of a Linked List

Two Heaps

K-way merge

Top K Elements

Modified Binary Search

Subsets

Greedy Techniques

Backtracking

Dynamic Programming

Cyclic Sort

Topological Sort

Sort and Search

Matrices

Stacks

Graphs

Tree Depth-First Search

Tree Breadth-First Search

Trie

Hash Maps

Knowing What to Track

Union Find

Custom Data Structures

Bitwise Manipulation

Challenge Yourself

Conclusion

Solution: Regions Cut by Slashes

Statement

Solution

Time complexity

Space Complexity