Coding Interview PatternsRegions Cut by Slashes
MediumUnion Find
Regions Cut by Slashes
Explanation & Solution
Description
An n x n grid is composed of 1 x 1 squares where each 1 x 1 square consists of a '/', '\', or blank space ' '. These characters divide the square into contiguous regions.
Given the grid grid represented as a string array, return the number of regions.
Note that backslash characters are escaped, so a '\' is represented as "\\" in the input.
Input:grid = [" /","/ "]
0
/
1
/
Output: 2
Explanation: The 2x2 grid with two / characters creates 2 regions.
Constraints
n == grid.length == grid[i].length1 <= n <= 30grid[i][j]is'/','\', or' '
Approach
Union Find pattern
1. Split Each Cell into 4 Triangles
- Divide each 1x1 cell into 4 parts: top (0), right (1), bottom (2), left (3)
- This creates
4 * n * ntotal nodes for Union Find
2. Union Triangles Within Each Cell
- Space `' '`: union all 4 triangles (0↔1↔2↔3) — entire cell is one region
- Slash `'/'`: union top with left (0↔3), union right with bottom (1↔2)
- Backslash `'\\'`: union top with right (0↔1), union bottom with left (2↔3)
3. Union Triangles Between Adjacent Cells
- Connect current cell's top (0) with the cell above's bottom (2)
- Connect current cell's left (3) with the cell to the left's right (1)
- This ensures adjacent cells are properly connected across boundaries
4. Count Connected Components
- Count nodes where
find(i) === i— each is a root of a component - Each component represents one contiguous region
Key Insight
- The key trick is splitting each cell into 4 sub-regions and selectively merging based on the character
- This reduces a geometric problem to a standard Union Find connected-components problem
Time
**O(n² · α(n²))** ≈ **O(n²)**Space
O(n²) for the Union Find arrays