959. Regions Cut By Slashes


Problem Description

In this problem, we are given an n x n grid where each cell of the grid contains either a forward slash ('/'), a backslash ('\\'), or is left blank (' '). These slashes divide the cell into some non-overlapping regions within the grid. The goal is to calculate the total number of such contiguous regions throughout the entire grid. A backslash is represented by double backslashes in the input due to string escape rules in programming languages.

Intuition

The solution uses Union-Find, also known as the Disjoint Set Union (DSU) algorithm, which is a data structure that keeps track of elements which are split into one or more disjoint sets. Its primary use is to determine whether two elements are in the same subset, and to merge subsets.

The key intuition behind this solution is to break down each grid cell further into four smaller triangular cells. This is done so we can precisely track the divisions within a cell caused by slashes. If a cell has a / or a \\, it splits the cell into two regions. If a cell is empty, it is a single region. We assign these triangular regions indices 0 to 3.

For each cell, we consider its 4 smaller parts:

  • Top (0)
  • Right (1)
  • Bottom (2)
  • Left (3)

By iterating over every cell in the grid, we can identify and union the triangulated parts of the cells based on the presence of a slash or space. A Union-Find data structure (p) is used to manage the groups of connected parts:

  • If there is a forward slash ('/'), then we union the top with the left part (0, 3) and the right with the bottom part (1, 2).
  • If there is a backslash ('\\'), then we union the top with the right part (0, 1) and the left with the bottom part (3, 2).
  • If there is no slash (a blank space), then all four parts belong to the same region and are all unioned together (0, 1, 2, 3).
  • In addition, cells that are directly adjacent vertically and horizontally are also merged if the corresponding sides touch. This includes merging bottom of one cell with top of the cell below it, and right of one cell with the left of the cell to its right. This is done only if the cells are not at the grid's boundary.

In the end, the size variable which is initialized to the total number of parts (which is n * n * 4) will have been decremented each time we successfully union two separate sets. The size will give us the count of disjoint sets or regions.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The solution is implemented via Union-Find, which involves two main operations: find and union.

  • The find function takes an integer x as an input, representing one of the triangular parts of the grid cells. It recursively looks for the root (or the leader) of the set that x belongs to, which is the one that points to itself. If x does not point to itself, it means x is not the root, and thus the function recurses on the parent of x. Path compression is used here; as the search for the root happens, the function compresses the path by setting each node to point directly to the root. This optimization speeds up future find operations.
1def find(x):
2    if p[x] != x:
3        p[x] = find(p[x])
4    return p[x]
  • The union function takes in two integers a and b, representing two parts that we want to connect. It finds the roots of both parts and if they are different, it points the root of the first part to the root of the second part. By doing so, it unifies the sets. When this union operation is done, if the sets were indeed distinct, we decrement the size variable by 1 because we have merged two regions into one.
1def union(a, b):
2    pa, pb = find(a), find(b)
3    if pa != pb:
4        p[pa] = pb
5        nonlocal size
6        size -= 1

The solution iterates over the grid, and we imagine splitting each cell into 4 smaller triangulated parts. For every cell, connections are made as follows:

  1. If the grid cell is at the edge (not the last row or column), union operations are done to merge with adjacent cells.
  2. If a cell contains a slash or a backslash, appropriate union operations are executed to join the diagonally divided parts. Blanks are considered as a single region, so all four parts of a cell are united.

The process of connecting adjacent cells and dealing with slashes/backslashes effectively build the connectivity of all the regions. After iterating through the grid, the accumulated size returns the count of disjoint sets, which is equivalent to the number of contiguous regions in the grid.

Here is the portion of the solution that performs these operations on the grid:

1n = len(grid)
2size = n * n * 4
3p = list(range(size))
4for i, row in enumerate(grid):
5    for j, v in enumerate(row):
6        k = i * n + j
7        if i < n - 1:
8            union(4 * k + 2, (k + n) * 4)
9        if j < n - 1:
10            union(4 * k + 1, (k + 1) * 4 + 3)
11        if v == '/':
12            union(4 * k, 4 * k + 3)
13            union(4 * k + 1, 4 * k + 2)
14        elif v == '\\':
15            union(4 * k, 4 * k + 1)
16            union(4 * k + 2, 4 * k + 3)
17        else:
18            union(4 * k, 4 * k + 1)
19            union(4 * k + 1, 4 * k + 2)
20            union(4 * k + 2, 4 * k + 3)

This approach is efficient because the Union-Find data structure with path compression and union by rank enables us to perform find and union operations almost in constant time. As a result, the overall time complexity of this algorithm is nearly linear in the number of cells, making it highly suitable for solving this problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a 2x2 grid to illustrate the solution approach. Suppose the grid is as follows:

1[
2  " /",
3  "/ "
4]

This grid has a forward slash in the top-right and a backslash in the bottom-left cell.

Initial Setup
  • The grid is 2x2, so we have a total of 16 smaller triangular parts because each cell is divided into 4 parts.
  • Initialize the size variable as 2 * 2 * 4 = 16.
  • Initialize the parent array p which will keep track of the leaders for each part: p = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15].
Iteration and Union Operations
  • Starting from the top-left cell grid[0][0], which is blank, we union all 4 parts (0, 1, 2, 3), reducing size to 13.
  • For the top-right cell grid[0][1] which has a forward slash "/", we union parts (0, 3) and (1, 2), reducing size to 11. Because this is the last column, we don't perform unions with the right cells.
  • Because this cell is not on the bottom row, we also union the bottom of this cell (part 2) with the top of the cell below it, which is part 8, reducing size to 10.
  • For the bottom-left cell grid[1][0] which has a backslash "", we union parts (4, 5) and (7, 6), reducing size to 8. We also union the top of this cell (part 4) with the bottom of the cell above it (part 0), which is already in the same set, so no reduction in size here.
  • For the bottom-right cell grid[1][1] which is blank, we union all 4 parts (8, 9, 10, 11), reducing size to 7.
  • We also union the left of this cell (part 8) with the right of the cell to its left (part 5), and union the top of this cell (part 8) with the bottom of the cell above it (part 1), leaving us with a size of 5, as parts (8) and (5) were already connected.
Result

After completing the iteration and union operations, the size variable tells us that there are 5 contiguous regions within the grid.

This walk-through demonstrates how each cell is split into 4 parts, and union operations are performed based on the presence of a slash and the position of the cell within the grid. The Union-Find data structure efficiently manages the connectivity of parts and ultimately provides the count of distinct regions.

Solution Implementation

1from typing import List
2
3class Solution:
4    def regionsBySlashes(self, grid: List[str]) -> int:
5        # Helper function to find the root of a set
6        def find_set(root_index):
7            if parent[root_index] != root_index:
8                parent[root_index] = find_set(parent[root_index])
9            return parent[root_index]
10
11        # Helper function to merge two sets
12        def union_sets(set_a, set_b):
13            root_a, root_b = find_set(set_a), find_set(set_b)
14            if root_a != root_b:
15                parent[root_a] = root_b
16                nonlocal region_count
17                region_count -= 1
18
19        # The size of the grid
20        n = len(grid)
21        # Initial count of distinct regions
22        region_count = n * n * 4
23        # Initialize parent pointers for each cell * 4 for internal division
24        parent = list(range(region_count))
25
26        # Iterate over each cell in the grid
27        for i, row in enumerate(grid):
28            for j, value in enumerate(row):
29                cell_index = i * n + j
30                # If not in the bottom row, unite bottom and top of adjacent cells
31                if i < n - 1:
32                    union_sets(4 * cell_index + 2, 4 * (cell_index + n))
33                # If not in the rightmost column, unite right and left of adjacent cells
34                if j < n - 1:
35                    union_sets(4 * cell_index + 1, 4 * (cell_index + 1) + 3)
36              
37                # Merge sets based on the presence of slashes
38                if value == '/':
39                    union_sets(4 * cell_index, 4 * cell_index + 3)
40                    union_sets(4 * cell_index + 1, 4 * cell_index + 2)
41                elif value == '\\':
42                    union_sets(4 * cell_index, 4 * cell_index + 1)
43                    union_sets(4 * cell_index + 2, 4 * cell_index + 3)
44                else:
45                    # No slashes means all 4 parts are connected
46                    union_sets(4 * cell_index, 4 * cell_index + 1)
47                    union_sets(4 * cell_index + 1, 4 * cell_index + 2)
48                    union_sets(4 * cell_index + 2, 4 * cell_index + 3)
49      
50        # The number of regions is the number of distinct sets
51        return region_count
52
53# Example of using the refactored function
54# sol = Solution()
55# result = sol.regionsBySlashes([" /", "/ "])
56# print(result)  # Output should be 2 for this example
57
1class Solution {
2    private int[] parent;
3    private int count;
4
5    public int regionsBySlashes(String[] grid) {
6        int n = grid.length;
7        count = n * n * 4;
8        parent = new int[count];
9        for (int i = 0; i < parent.length; ++i) {
10            parent[i] = i;
11        }
12        for (int i = 0; i < n; ++i) {
13            for (int j = 0; j < n; ++j) {
14                int index = i * n + j;
15                if (i < n - 1) {
16                    union(4 * index + 2, (index + n) * 4);
17                }
18                if (j < n - 1) {
19                    union(4 * index + 1, (index + 1) * 4 + 3);
20                }
21                char c = grid[i].charAt(j);
22                if (c == '/') {
23                    union(4 * index, 4 * index + 3);
24                    union(4 * index + 1, 4 * index + 2);
25                } else if (c == '\\') {
26                    union(4 * index, 4 * index + 1);
27                    union(4 * index + 2, 4 * index + 3);
28                } else {
29                    union(4 * index, 4 * index + 1);
30                    union(4 * index + 1, 4 * index + 2);
31                    union(4 * index + 2, 4 * index + 3);
32                }
33            }
34        }
35        return count;
36    }
37
38    // Helper method to find the root of the set that element x belongs to
39    private int find(int x) {
40        if (parent[x] != x) {
41            parent[x] = find(parent[x]);
42        }
43        return parent[x];
44    }
45
46    // Helper method to union two sets
47    private void union(int a, int b) {
48        int rootA = find(a);
49        int rootB = find(b);
50        if (rootA == rootB) {
51            return;
52        }
53        parent[rootA] = rootB;
54        --count; // Decrement the count of regions as two regions merge into one
55    }
56}
57
1#include <vector>
2#include <string>
3using namespace std;
4
5class Solution {
6public:
7    vector<int> parent; // Parents array for Union-Find
8    int regionsCount;   // Counter for the number of regions found
9
10    // Function to calculate the number of regions separated by slashes in the grid
11    int regionsBySlashes(vector<string>& grid) {
12        int n = grid.size();
13        regionsCount = n * n * 4;
14        parent.resize(regionsCount);
15        for (int i = 0; i < regionsCount; ++i) parent[i] = i;
16
17        for (int i = 0; i < n; ++i) {
18            for (int j = 0; j < n; ++j) {
19                int rootIndex = i * n + j;
20                if (i < n - 1) {
21                    merge(rootIndex * 4 + 2, (rootIndex + n) * 4);
22                }
23                if (j < n - 1) {
24                    merge(rootIndex * 4 + 1, (rootIndex + 1) * 4 + 3);
25                }
26                char value = grid[i][j];
27                if (value == '/') {
28                    merge(rootIndex * 4, rootIndex * 4 + 3);
29                    merge(rootIndex * 4 + 1, rootIndex * 4 + 2);
30                } else if (value == '\\') {
31                    merge(rootIndex * 4, rootIndex * 4 + 1);
32                    merge(rootIndex * 4 + 2, rootIndex * 4 + 3);
33                } else {
34                    merge(rootIndex * 4, rootIndex * 4 + 1);
35                    merge(rootIndex * 4 + 1, rootIndex * 4 + 2);
36                    merge(rootIndex * 4 + 2, rootIndex * 4 + 3);
37                }
38            }
39        }
40
41        return regionsCount;
42    }
43
44    // Function to merge two nodes in the Union-Find structure
45    void merge(int nodeA, int nodeB) {
46        int parentA = find(nodeA);
47        int parentB = find(nodeB);
48        if (parentA != parentB) {
49            parent[parentA] = parentB;
50            --regionsCount; // Decrement the regions count only if a merge occurred
51        }
52    }
53
54    // Recursive function to find the root parent of a node in Union-Find
55    int find(int x) {
56        if (parent[x] != x) {
57            parent[x] = find(parent[x]); // Path compression
58        }
59        return parent[x];
60    }
61};
62
1// Importing necessary functionalities
2import { vector, string } from 'vector-string'; // Import statement would need adjustment, vector-string does not exist in TypeScript
3
4// Global variables for Union-Find
5let parent: number[] = [];   // Array to hold the parents in the Union-Find
6let regionsCount: number = 0; // Counter for the number of regions
7
8// Function that calculates the number of regions separated by slashes in a grid
9function regionsBySlashes(grid: string[]): number {
10    const n: number = grid.length;
11    regionsCount = n * n * 4;
12    parent = new Array(regionsCount).fill(0).map((_, index) => index);
13
14    for (let i = 0; i < n; ++i) {
15        for (let j = 0; j < n; ++j) {
16            const rootIndex: number = i * n + j;
17            if (i < n - 1) {
18                merge(rootIndex * 4 + 2, (rootIndex + n) * 4);
19            }
20            if (j < n - 1) {
21                merge(rootIndex * 4 + 1, (rootIndex + 1) * 4 + 3);
22            }
23            const value: string = grid[i][j];
24            if (value === '/') {
25                merge(rootIndex * 4, rootIndex * 4 + 3);
26                merge(rootIndex * 4 + 1, rootIndex * 4 + 2);
27            } else if (value === '\\') {
28                merge(rootIndex * 4, rootIndex * 4 + 1);
29                merge(rootIndex * 4 + 2, rootIndex * 4 + 3);
30            } else {
31                merge(rootIndex * 4, rootIndex * 4 + 1);
32                merge(rootIndex * 4 + 1, rootIndex * 4 + 2);
33                merge(rootIndex * 4 + 2, rootIndex * 4 + 3);
34            }
35        }
36    }
37
38    return regionsCount;
39}
40
41// Function to merge two nodes within the Union-Find structure
42function merge(nodeA: number, nodeB: number) {
43    const parentA: number = find(nodeA);
44    const parentB: number = find(nodeB);
45    if (parentA !== parentB) {
46        parent[parentA] = parentB;
47        regionsCount--; // Decrement the regions count when a merge occurs
48    }
49}
50
51// Function to find the root parent of a node in Union-Find with path compression
52function find(x: number): number {
53    if (parent[x] !== x) {
54        parent[x] = find(parent[x]);
55    }
56    return parent[x];
57}
58

Time and Space Complexity

The time complexity of the algorithm is O(n^2) where n is the length of one side of the grid. This complexity arises because the algorithm iterates through all cells in the grid, and for each cell, it performs union and find operations which are generally considered O(1) due to path compression and union by rank optimizations in the Disjoint Set Union (DSU) data structure.

The space complexity is O(n^2) because of the parent array p that keeps track of the disjoint sets. Since each grid cell is divided into 4 parts for the DSU operations, the space required will be 4 * n^2, which is still O(n^2) when dropping the coefficient.

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄